Elaboration du QR code

Introduction :

La création du QR code se fait en 3 étapes:

  1. Créer une chaîne de bits de données à partir du message que l'on veut encoder. Cette chaîne inclut les caractères du message d'origine que l'on veut encoder, ainsi que quelques bits d'information qui disent au décodeur QR quel type de code QR c'est;
  2. Générer le code correcteur d'erreur (redondance). Il s'agit d'un processus complexe, c'est pourquoi le principe de la redondance sera brièvement expliqué;
  3. Choisir la meilleure forme de masque afin d'optimiser la lecture du QR code.

 

Afin d'expliquer le fonctionnement d'un QR code, nous avons pris l'exemple du site http://www.thonky.com/qr-code-tutorial/introduction/  qui explique le processus d'encodage du mot HELLO WORLD. Ainsi la plupart des images ci-dessous sont tirées de ce site car nous n'avons pas le matériel nécessaire pour faire nous-mêmes ces illustrations. 

 

1. Transformation d'un texte en une chaîne binaire

Encodages Préliminaires

Avant d'encoder notre information (HELLO WORLD) il faut tout d'abord commencer la chaîne de bits par une information sur le type de données. Comme ce que l'on veut encoder sont des caractères alphanumériques la chaîne commence par 0010.

Chaîne de Bits Type d'information
0001 Numérique
0010 Alphanumérique
0100 Binaire
1000 Kanji (caractère Japonais)

Il faut ensuite indiquer quelle version de QR code on utilise au moyen de quelques bits supplémentaires. Ainsi la chaîne est: 0010 000001011

Encodage des données sources

Afin d'encoder notre message il faut le diviser par paires : HE / LL / O  / WO / RL / D.
Pour chaque paire on prend la valeur ASCII de la première lettre puis on multiplie cette valeur par 45. On ajoute ensuite à cette multiplication la valeur ASCII de la deuxième lettre. La valeur obtenue est par la suite transformée en une chaîne binaire de 11 bits. Pour la lettre qui est toute seule on prend tout simplement la valeur ASCII de celle-ci que l'on transforme en une chaîne binaire de 6 bits.

          HE               LL                O(espace)           WO              RL              D

       (17x45)+14   (21x45)+25      (24x45)+36       (32x45)+24    (27x45)+21    13

        779              966                 1116                1464              1236            13

 01100001011   01111000110  10001011100   10110111000  10011010100  001101

La chaîne binaire est donc après cette opération  0010 000001011 01100001011 01111000110 10001011100 10110111000 10011010100 001101. Comme celle ci est trop courte on rajoute quatre zéros. Il faut ensuite délimiter des groupes de huit (octets), le dernier groupe est complété par des zéros si cela ne fait pas huit.
Le QR code que l'on veut faire est de version 1, faite pour coder 104 bits. Or notre chaîne de bits fait 10 octets et 104/8=13 donc il faut encore ajouter 3 octets. Il existe pour cela deux octets spécifiques 11101100 et 00010001 que l'on ajoute alternativement jusqu'à ce qu'on arrive à 104 bits.

Notre chaîne, avant de subir la redondance, est donc 00100000 01011011 00001011 01111000 11010001 01110010 11011100 01001101 01000011 01000000 11101100 00010001 11101100

2. La redondance

Principe

La redondance est utilisée afin de reconstituer l'intégralité de l'information codée dans le QR code même si celui-ci subit une altération (déchirure, tâche, froissure, ...).
Ainsi l'information est répétée de façon à pouvoir, au moyen d'un code correcteur, retranscrire l'information.

La redondance est visible sur un QR code dans sa structure. En effet plus un QR code a un taux de redondance
élevé plus sa structure sera complexe.


     H (30% de récupération de données)            Q (25% de récupération de données)

      M (15% de récupération de données)              L (7% de récupération de données)


Pour désigner les différents types de taux de redondance, des lettres sont utilisées (H;Q;M;L). Le pourcentage de
récupération des données indique la part du QR code qui peut être endommagée sans répercussion sur la lecture
du code barre.

En observant de près le QR code il est possible de savoir le taux de redondance de celui-ci. En effet deux carrés situés en bas à gauche de chaque QR code montrent quel taux est utilisé:

 

Le code de Reed-Solomon

Le code de Reed-Solomon est un code correcteur utilisé afin d'effectuer une redondance dans l'information du QR code.

Il permet de corriger deux types d'erreurs:

  • les modifications de données (par exemple si un carré blanc est remplacé par un noir);
  • les pertes de données (par exemple si le QR code est déchiré). 

C'est un code efficace mais son algorithme est très complexe :
l'information originale du QR code est convertie en un polynôme et des points le caractérisant sont ajoutés à l'information de façon à pouvoir retrouver le polynôme même si certaines informations sont perdues ou endommagées.

Voici un exemple très simplifié de ce que peut être la redondance de l'information:

Détection et Correction d'erreurs



3. Le choix du masque

Maintenant que l'information a été encodée il ne reste plus qu'à choisir le meilleur type de masque.
Ce dernier modifie certains bits afin de rendre l'information plus lisible.
Il exite 8 types de masques :

QR Code Mask Patterns.svg
                                                                        NB: le % signifie "modulo" 

Selon le type de masque on peut donc créer 8 QR codes différents, il faut donc choisir le plus facile à lire.
Un QR code peut avoir certaines caractéristiques qui font que sa lecture peut s'avérer difficile (par exemple si des
pixels de mêmes couleurs sont situés côte à côte).

Ainsi on génère les huits QR codes puis un "score" est attribué à chacun pour sélectionner le meilleur.

Le "remplissage" du QR code

Cependant avant de savoir quel masque mettre, il faut auparavant remplir le QR code en remplissant les différentes matrices.
Tout QR code a en commun certaines caractéristiques que l'on peut voir sur cette image ci-dessous:

 qr-code-structure.jpg

 

L'information sur le type de redondance et de masque est encodée en plusieurs bandes disposées aux côtés des motifs de positions.

Le tableau ci-dessous montre quels bits correspondent aux différents types de masques et redondance:

ECC LevelMask PatternType Information Bits
L 0 111011111000100
L 1 111001011110011
L 2 111110110101010
L 3 111100010011101
L 4 110011000101111
L 5 110001100011000
L 6 110110001000001
L 7 110100101110110
M 0 101010000010010
M 1 101000100100101
M 2 101111001111100
M 3 101101101001011
M 4 100010111111001
M 5 100000011001110
M 6 100111110010111
M 7 100101010100000
Q 0 011010101011111
Q 1 011000001101000
Q 2 011111100110001
Q 3 011101000000110
Q 4 010010010110100
Q 5 010000110000011
Q 6 010111011011010
Q 7 010101111101101
H 0 001011010001001
H 1 001001110111110
H 2 001110011100111
H 3 001100111010000
H 4 000011101100010
H 5 000001001010101
H 6 000110100001100
H 7 000100000111011

QR Code Type Information

Dans notre exemple avec HELLO WORLD, le meilleur masque est le 0 (ce sera expliqué plus bas). Le taux de redondance choisi est le Q donc l'information qui doit être codée est  011010101011111. Comme on peut le voir sur l'image ci-dessus cette information est codée deux fois.

Après avoir mis cette information, il faut également coder l'information sur la version du QR code. Ceci est valable seulement pour les versions 7 et plus. Cette information est stockée près des motifs de position comme on peut le voir sur l'image ci-dessous:

Version information bits

 

 

 

 

L'information source

La mise en place de l'information que l'on veut encoder se fait dans un ordre prédéfini en commencant par le pixel en bas à droite du QR code.

Ainsi le premier pixel correspondant au premier bit de la chaîne est ajouté dans le coin en bas à gauche. Ce pixel sera noir s'il correspond au bit 0 ou blanc s'il correspond à 1 en faisant attention au masque. Ainsi on voit ci-dessous que le début de la chaîne de bits qui devrait être codée est 00100000. Or les deux premiers pixels mis sont blanc puis noir ce qui correspond à 10 et non 00. 
Ici le masque qui est mis est le 6 de formule ((ixj)mod 3 + ixj)mod 2 . On l'applique au premier pixel qui a pour coordonées (20;20)
Donc cela fait ((20x20)mod 3 + 20x20)mod 2.       Ainsi, même si le bit est 0 le pixel est blanc car on met le masque. 
                   = (1+400)mod 2
                   = 1

Cela marche aussi pour le deuxième pixel de coordonnée (19;20) car ((19x20)mod 3 + 19x20)mod 2 donc comme c'est la même chose que la donnée source on garde le 0.
                                                                                                     =(2+380) mod 2
                                                                                                     =0 

remplissage-qr-code.jpg

 

Le choix du masque

Afin de choisir le meilleur masque on essaye les 8 masques différents et on accorde un score à chacun d'eux pour sélectionner celui qui a le score le plus faible.
Il y a 4 principaux critères qui accordent les points de pénalités:

  • l'existence de groupe de 5 ou plus pixels de la même couleur sur la même ligne ou colonne;

 

Horizontal step of QR mask pattern penalty rule 1Vertical step of QR mask pattern penalty rule 1

  • s'il y a des endroits où les pixels sont rassemblés en carré de la même couleur

Illustration of penalty rule 2 for QR mask pattern

  • si certains motifs ressemblent à ces trois motifs qui gènent à la lecture
    penalty-qr-code.jpg 

  • si plus de la moitié des pixels sont noirs ou blancs

Il n'y a plus qu'à choisir le QR code qui a le score le plus faible,ici celui avec le masque 0. Cet image permet aussi de montrer les 8 QR codes différents que l'on peut créer avec la même  information source et le même taux de redondance.
Il ne faut pas oublier que cela va permettre de choisir le QR code qui est le plus lisible, ce qui est important dans l'application marketing puisque le QR code sera moins efficace si les utilisateurs ont du mal à le flasher. 

Summary of HELLO WORLD QR code mask pattern results and penalties

 

Créer un site internet avec e-monsite - Signaler un contenu illicite sur ce site