Un code-barres 2D                                                                                   

Un QR Code a la capacité de stocker ses informations horizontalement et verticalement.

En effet, la lecture se fera sur 2 axes, un QR Code peut être représenté par une matrice(x,y).

Le passage de 1 dimension à 2 dimensions a permis également d'augmenter la capacité de stockage des code-barres tout en réduisant la taille de l'image.

Il est ainsi possible de traduire une information de plusieurs dizaines de caractères en un seul QR Code de 2 cm de côté !

Le principal atout du QR Code est donc sa haute capacité de stockage :

• 7089 caractères numériques (0-9)
• 4296 caractères alphanumériques (ASCII)
• 2953 octets (binaires 8-bit)
• 1817 kanji (caractères japonais)

Le QR Code a l'atout de pouvoir être placé dans des espaces réduits, mais il faut faire attention pour permettre une lecture aisée. En effet, plus il y a de points dans la matrice, plus il y a de l'information stockée dans le QR Code. Il faut donc faire un compromis entre la taille et la lisibilité du QR Code sous peine d'avoir des difficultés à le décoder.

Le Qr Code a également la capacité de pouvoir être lu dans tous les sens (360°) de manière très rapide grâce à des repères dans la matrice facilement détectables.

Enfin, l'atout majeur du QR Code comparé au code-barres traditionnel reste sa résistance à presque tout. En effet, le QR Code tolère d'être abîmé (déchirures, salissures, etc.) car ce dernier contient un code correcteur et de redondance de l'information. En résumé, la force du QR Code est d'intégrer un taux de correction d'erreur qui définit la quantité d'informations répétées, et donc une tolérance plus ou moins importante aux dégradations. Plus le taux de correction d'erreurs est élevé, plus le QR Code sera complexe à la lecture.

Il est important de noter que le QR Code reste lisible avec jusqu'à 30% de son code détruit ou manquant.

Pour terminer cette description, il faut surtout savoir que le QR Code a été inventé par les japonais dans le but de pouvoir bénéficier d'un support qui permette de stocker leurs propres caractères. Et donc, le QR Code est unique dans le sens où il peut stocker et encoder des caractères exotiques comme les kanji (caractères japonais) ou autres...

Il existe de nombreux code-barres à 2 dimensions mais seul le QR Code sort du lot avec les meilleures performances. Le QR Code a un haut pouvoir de stockage, prend peu d'espace et est très rapide à la lecture.

Matrice de comparaison des code-barres à 2 dimensions :

Pour avoir de plus amples informations sur les autres codes à 2 dimensions, vous pouvez cliquer ici.

Structure du QR Code                                                                              

Structure générale du QR Code :

Comme on peut le remarquer, un QR Code est composé de carrés noirs et blancs qui s'appellent modules. Chaque module représente une valeur binaire :

• NOIR -> 1
• BLANC -> 0

La zone silencieuse est composée de 4 modules de largeur pour délimiter le QR Code. Cette dernière est non obligatoire mais recommandée. Cette zone facilite fortement la lecture du QR Code.

Les patterns (motifs) de détection de position (toujours au nombre de 3 positionnés en haut à gauche, en haut à droite et en bas à gauche) sont très importants et seront détaillés un peu plus tard.

Les séparateurs permettent de séparer les patterns de détection de position du reste du code.

Les timing Patterns (patterns de synchronisation) permettent de densifier le QR Code (par l'alternance de modules blancs/noirs);  de déterminer la version du QR Code; et de fournir des positions de référence pour le calcul des coordonnées de chaque module

Les patterns d'alignement sont composés de 3 carrés concentriques superposés et de taille 5x5 modules pour le premier noir, 3x3 modules pour le blanc et un seul module central noir. Le nombre de ces patterns d'alignement dépend de la version de QR Code généré.

La région du code contient toutes les données encodées, avec le code de correction d'erreur, les informations de version et de format.

Il existe dans le code 2 principales régions. Le code contenant les données à stocker et le code correcteur. Le code correcteur permettra, en cas de perte des données stockées, à corriger celles-ci et récupérer les informations détruites.

Les patterns de détection de position sont très ressemblants aux patterns d'alignement, à la différence près qu'ils sont plus gros et qu'ils sont toujours présents au nombre de 3 dans le motif du QR Code. Comme on peut le voir dans la figure suivante, ils sont composés d'un premier carré noir de taille 7x7 modules, d'un second carré blanc de 5x5 modules et enfin d'un carré noir central de 3x3 modules. Ce symbole est codé de telle sorte qu'il existe une très faible probabilité de retrouver ce symbole dans tout le symbole du QR Code.

Ces patterns de détection permettent de définir clairement l'emplacement et l'orientation du symbole dans l'espace.

Selon la quantité de données stockées, le QR Code sera plus ou moins complexe. Ainsi, il existe 40 versions de QR Code différentes définies dans les spécifications.

Chacune de ces versions ont une capacité de stockage maximale et telle ou telle version sera utilisée en fonction de la quantité d'informations que l'on veut stocker dans le QR Code. Toutefois, il est important de noter que plus un QR Code a une version élevée, plus il sera difficile à décoder. Ainsi, pour permettre une meilleur lecture, le nombre de patterns de détection de position augmentera en fonction de la version utilisée. De plus, on remarquera que pour un QR Code très simple (version 1), il n'y a pas besoin de pattern d'alignement.

Néanmoins, il faut savoir que tout ce qui fait la force du QR Code vient du fait de l'utilisation du code correcteur et de la redondance d'information.

                    Fonctionnement                    

Redondance : la clé du succès                                                                 

Le principe du QR Code, qui en fait son principal atout, est d'utiliser la redondance d'informations.

Quand nous reprenons la définition de redondance par Wikipédia :

La redondance se rapporte à la qualité ou à l'état d'être en sur-nombre, par rapport à la normale ou à la logique. Ce qui peut avoir la connotation négative de superflu, mais aussi un sens positif quand cette redondance est voulue afin de prévenir un dysfonctionnement.

En effet, la redondance est employée dans le QR Code de manière à prévenir toute altération du motif et ainsi fournir au lecteur l'information codée originale sans problèmes. C'est le code correcteur d'erreurs du QR Code qui créé la redondance afin d'accroître la fiabilité de l'information. Le code de Hamming est un exemple de code correcteur.

L'objectif d'un code correcteur est la détection ou la correction d'erreurs après la transmission d'un message. Cette correction est permise grâce à l'ajout d'informations redondantes. Le message est plongé dans un ensemble plus grand, la différence de taille contient la redondance, l'image du message par le plongement est transmise. En cas d'altération du message, la redondance est conçue pour détecter ou corriger les erreurs. Le code de Hamming permet la détection et la correction automatique de ces erreurs. La détection d'une erreur se fait par le calcul de la distance de Hamming entre deux mots du code.

La distance minimale du code correcteur est la plus petite distance de Hamming entre deux mots du code

Je vous envoie consulter le cours de Réseaux locaux dispensé en IR1 par Etienne Duris, à partir du slide 45, où est très bien expliqué le principe de code correcteur et code de Hamming.
Il vous suffit juste de cliquer ici pour accéder au cours, ou bien ici pour aller sur la page des cours et TD de réseaux locaux en IR1.

Le QR Code a donc cette capacité de fournir l'information même s'il est abîmé. Et ce, grâce au code correcteur particulier qu'il contient : Le code de Reed-Solomon.

Code de Reed-Solomon                                                                            

Le code de Reed-Solomon est un code correcteur, dit "code parfait" inventé par les mathématiciens Irving S.Reed et Gustave Solomon, qui est très utilisé et permet de corriger des erreurs dûes à la transition imparfaite d'un message.

Ce code de Reed-Solomon est basé sur un principe mathématique qui a pour objectif de construire un polynôme à partir des symboles à transmettre (information source) et de le suréchantillonner. C'est à dire d'apporter beaucoup plus d'informations à ce polynôme. Le résultat est alors envoyé, au lieu des symboles originaux. La redondance de ce suréchantillonnage permet au récepteur du message encodé de reconstruire le polynôme source même s'il y a eu des erreurs pendant la transmission.

Ci-dessous, voici une illustration de code non correcteur suivie d'illustrations de code correcteur (type code de Hamming) et de code parfait (type code de Reed-Solomon).

Tous les codes correcteurs subissent une contrainte du même ordre. Si le message contient une information altérée, une information supplémentaire est nécessaire pour, soit détecter l'erreur, soit la corriger.
Le message transmis, appelé code est plongé dans un espace plus vaste, comme illustré dans la figure du milieu. Le cas d'un code sans redondance est illustré à gauche.

Chaque point du code diffère des autres points du code par au moins d coordonnées. Les points du code sont figurés en vert, la modification d'une coordonnée est symbolisée par un segment du quadrillage.

Si un message en vert subit, lors de sa transmission, une altération, alors un nouveau message en rouge est transmis. Aucune information ne laisse supposer qu'une erreur a été commise. Pour pallier cet état, l'objectif est d'entourer les messages licites, correspondant aux intersections des quadrillages sur les figures, par des messages connus pour contenir des erreurs, et de réaliser la transmission après. Ces redondances sont illustrées sur la figure du milieu par les intersections du quadrillage orange. Si une unique erreur se produit, alors le message transmis correspond à un point rouge. Si la redondance a été habilement construite, alors il n'existe qu'un point licite en vert proche du point rouge reçu.
En résumé, on remarque sur la figure du milieu que les points du code diffèrent tous par au moins d=3 coordonnées. Si, par exemple, l'altération porte sur une unique coordonnée, la transmission correspond à un point rouge. Le récepteur peut alors corriger l'erreur, car il n'existe qu'un seul point du code (en vert) à une distance égale à 1 du message reçu. La distance de Hamming correspond sur la figure au plus petit nombre de segments du quadrillage à traverser pour joindre deux points, on a d=3.

Un code correcteur propose une géométrie où les messages licites sont le plus possible éloignés les uns des autres. Les boules centrées sur les bons codes, si elles ne s'intersectent pas, permettent de retrouver le bon message, correspondant à son centre. Une perturbation, tant qu'elle reste suffisamment petite pour ne pas faire sortir le code de sa boule, est corrigible.
Dans la figure du milieu, les points noirs ne sont d'aucune utilité. Il est nécessaire de parcourir 2 segments du quadrillage pour relier un point noir d'un point licite. Le code correcteur illustré dans la figure du milieu engendre alors une ambiguïté. En effet, tous les points rouges sont à une distance de 2 segments de 2 points verts, une double erreur n'est donc généralement pas corrigible. Les points noirs ne servent à rien et ils prennent de la place. Ils présentent donc une redondance inutile.
C'est donc un problème puisque ces redondances inutiles sont à une distance égale à 2 des points du code, or une telle distance n'est pas traitable ici.

Dans la figure de droite, les points du code en vert sont espacés d'une distance de 5 entre eux. Si la transmission ne produit jamais plus de 2 altérations, alors les erreurs sont toutes corrigibles. De plus, il n'existe pas de points en dehors des boules fermées de centre correspondant aux points du code et de rayon 2, c'est-à-dire de redondance inutile (aucun point noir). Les points à une distance de 1 du code sont en bleu et ceux à une distance de 2 en rouge. En résumé, l'espace est intégralement rempli par les boules fermées de rayon 2 et de centre correspondant aux points du code, de plus elles ont une intersection vide entre elles.

Comment ça marche ?                                                                             

Pour illustrer le fonctionnement du code correcteur, voici un petit exemple très simplifié qui illustre le processus de reconnaissance et de correction d'erreur.

Le codeur va ajouter à l'information source (3 nombres) des nombres de redondance d'information.
Le premier nombre de redondance correspond à la somme des 3 nombres. Le second nombre de redondance est la somme pondérée des 3 nombres, chacun est multiplié par son rang.

Si le message transmis est altéré, c'est au rôle du décodeur de détecter l'erreur et de la corriger. Il va s'aider des nombres de redondance d'information ajoutés par le codeur.
Un recalcul de la somme des nombres devrait permettre de retomber sur le même premier nombre de redondance d'information. Or ici, le décodeur trouve 45 au lieu de 41. Il sait donc détecter qu'il y a eu une erreur lors de la transmission du message. Il note de côté la différence entre le nouveau nombre trouvé et celui qu'il a en mémoire. Cette différence trouvée correspond à la valeur de l'erreur. Maintenant, pour corriger l'erreur, il doit trouver où se situe celle-ci parmi les informations reçues.
Pour le second nombre de redondance, il trouve une différence. Cette différence divisée par la valeur de l'erreur donnera la position de l'erreur. Il faut donc retirer 4 au nombre du rang 2.
Le décodeur a donc pu détecter et corriger l'erreur simplement pour fournir le bloc original, et ce malgré l'altération du message.
Il faut noter que lors d'une transmission sans perturbation, les différences des sommes simples et des sommes pondérées sont nulles.

Conclusion                                                                                               

Les QR Codes ne sont pas simplement des code-barres au sens tel que nous les connaissions jusqu'à aujourd'hui. En effet, ces codes ont un net avantage par rapport à leurs aînés (les codes-barres classiques unidimensionnels) : proposer un support de stockage d'informations sur un espace très réduit et surtout proposer une multitude de services. On l'aura bien compris, le Qr Code est bien la renaissance du code-barres, c'est le code-barres du 21ème siècle. Les entreprises de marketing l'ont bien compris elles aussi.

Toutefois, il faut se méfier car comme dans toute technologie à la mode et qui attire du monde, il existe des risques. En effet, les QR Codes peuvent être détournés à des mauvaises fins comme forcer l'utilisateur à envoyer un sms surtaxé en scannant un code ou bien télécharger à son insu sur son smartphone un virus compromettant ainsi toutes les données personnelles.

Il faut donc, avant de scanner tout QR Code, savoir à qui on a affaire. Et pour les adeptes des complots, j'ajouterais cette citation bien connue d'X-Files (série télévisée américano-canadienne de science fiction) :

Don't trust anyone...