Catégories
Tech

Comment est construit un QR code ?

Nous les utilisons de plus en plus souvent mais techniquement, comment un QR code fonctionne-t-il ?

Nous les utilisons de plus en plus souvent, mais techniquement, comment un QR Code fonctionne-t-il ?

C’est la question que je me suis posée et personnellement je trouve passionnant de comprendre les techniques utilisées pour les générer.

Si cela vous intéresse, j’ai récemment développé une librairie qui permet de créer des QR codes avec Godot Engine.

Avant d’entrer dans le vif du sujet, petit retour sur leurs origines.

Les QR codes ont été inventés au japon au milieu des années 90 pour les besoins des usines de production Toyota. L’entreprise qui les a créés, Denso-Wave, a eu la bonne idée de rendre le code open source. Ce qui a contribué à leur popularisation avec l’arrivée des smartphones.

Il s’agit d’un type de code-barres en deux dimensions composé de carrés noirs et blancs qui vont permettre d’encoder une chaine de caractère. Cela peut être n’importe quoi, un nombre, un texte, des données formatées en JSON, une URL, etc.

En plus des données, le QR Code va être composé de plusieurs motifs qui vont permettre au lecteur de comprendre son orientation et le format dans lequel les données sont enregistrées.

Type d’encodage et conversion en binaire

Pour dessiner notre motif, la chaine de caractères que nous allons utiliser doit d’abord être convertie en binaire, c’est-à-dire en 0 et 1. Dans notre QR Code, 0 représentera un carré blanc et 1 un carré noir.

Mais avant ça, nous allons devoir définir son type d’encodage. La norme QR propose quatre types d’encodage :

  • Le format numérique qui permet d’encoder des nombres
  • Alphanumérique : qui permet d’encoder les nombres, des lettres majuscules et quelques signes de ponctuation.
  • Le format Byte qui supporte l’ensemble des caractères de la norme UTF-8.
  • Et le format Kanji qui est spécialement conçu pour encoder les signes asiatiques.

Je vais surtout vous expliquer l’encodage au format Byte qui fonctionne pour tous les types de contenu, mais qui ne sera pas le plus optimisé pour les valeurs numérique, alphanumérique et kanji. Le mode Byte convertit chaque caractère de notre chaine en une suite de 8 bits (0 et 1) en fonction de sa valeur Unicode. Par exemple si j’encode la chaine « Greaby » en mode Byte cela donne :

CaractèresValeurs hexadécimalesBits
G4701000111
r7201110010
e6501100101
a6101100001
b6201100010
y7901111001
010001110111001001100101011000010110001001111001

Taille d’un QR code

Il existe différentes tailles de QR code allant de la version 1 qui peut stocker 19 bytes de donnée à la version 40 qui peut stocker 2956 bytes. Dans l’exemple ci-dessus, notre texte est composé de 6 bytes, nous pouvons donc utiliser la taille 1.

Correction d’erreurs

Je ne l’ai pas mentionné plus haut, mais la place maximum disponible varie un peu en fonction du niveau de correction d’erreur. Comme le QR code peut être affiché sur différent support physique (papier, textile, etc.), celui-ci risque d’être détérioré. C’est pour cela qu’on utilise un algorithme de correction d’erreurs.

L’algorithme s’appelle le code de Reed-Solomon. On l’utilise couramment dans les disques durs et les CD. C’est ce qui vous permet de continuer à lire un CD malgré quelques rayures.

Comment cela fonctionne ?

Je simplifie parce qu’en vrai, c’est un peu plus complexe que ça.

Concrètement, nous allons prendre une donnée et la subdivisé en 2 parties, ensuite à l’aide de l’algorithme, nous allons générer une 3ème partie. Il nous suffira de posséder 2 des 3 valeurs pour pouvoir retrouver la donnée.

Cette technique prendra plus d’espace de stockage, mais permettra de lire les données même avec une partie du paterne dégradé. Quatre formats de correction existent et permettent d’avoir un taux d’erreur allant de 7 à 30 %.

Marqueur de position

Le marqueur de position (position pattern en anglais) est certainement le motif le plus reconnaissable d’un QR Code. Cette structure est composée de trois carrés situés sur les coins supérieurs et en bas à gauche. Elle permet au lecteur de comprendre l’orientation du code et de le tourner pour pouvoir le lire correctement.

Qr Code - Marqueur de position

Motif de synchronisation

La sixième ligne et la sixième colonne constituent le timing pattern. Il s’agit de séquences alternées de motifs noirs et blancs, disposés horizontalement et verticalement. Elles permettent au logiciel de numérisation de comprendre la largeur des cellules de données lorsque le symbole est déformé.

Qr Code - Motif de synchronisation

Paterne d’alignement

Le paterne d’alignement est utilisé dans les plus grands QR codes et se compose de carrés plus petits que le marqueur de position. Comme pour le timing pattern, ces marqueurs aident au positionnement en cas de lecture déformée ou avec un angle de vue.

Qr Code - Paterne d'alignement

Écriture des données en zigzag

Honnêtement, je ne sais pas pourquoi l’écriture des données se fait de cette manière. Peut-être pour éviter qu’un bloc de donnée ne soit trop espacé et faciliter la lecture.

L’écriture de la suite de 0 et de 1 générée se fait en partant du coin en bas à droite. On commence à écrire les données en formant un zigzag vers le haut. Une fois en haut, on se décale d’une case à gauche et on reproduit le même paterne vers le bas. J’avoue que cette partie n’est pas simple à expliquer et le mieux est que je l’illustre avec une image.

Qr Code - Écriture des données

Paterne de masquage

Imaginez maintenant que vous inscriviez les valeurs 0000000000000… dans votre QR Code. Les cases seront uniquement composées de blanc, ce qui risque de rendre la lecture difficile. C’est pourquoi nous appliquons un paterne de masquage aux données. Il s’agit d’un paterne qui se présente sous la forme d’un damier et qui inversera la couleur de la valeur si la case du damier est noire.

Qr Code - Paterne de masquage

Il existe au total huit différents paternes de masquage. Un emplacement dans le QR code est réservé pour savoir quel paterne nous utilisons.

Lorsque nous générons un QR Code, nous allons calculer avec quel paterne celui-ci est le plus facilement lisible en comptant le nombre de cases adjacentes de la même couleur pour chacun des motifs.

Conclusion

Et voilà ! Nous avons là toutes les briques qui nous permettent de créer un QR code. Si vous voulez approfondir le sujet, je vous invite à aller lire des articles plus techniques. Par exemple, ce projet très détaillé qui m’a beaucoup aidé pour comprendre leur fonctionnement !

Et je suis même fière d’avoir pu générer un Qr Code par moi-même grâce à la librairie que j’ai créée sur Godot Engine ! Je vous invite à le tester, il est parfaitement fonctionnel 🙂

0101010001100011011010000110000101101111