QR Code©  Le code-barres version 2D

Fonctionnement

Pouvez-vous répéter ? Pouvez-vous répéter ? Pouvez-vous répéter ? Pouvez-vous répéter ? ...

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.

Distance de Hamming entre 2 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).

Les codes correcteurs

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.

Détection et Correction d'erreurs

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.



Revenir en haut de page ˆˆˆ

QR Code en action >>>