Origine et usages plus larges
Les codes de Reed-Solomon ont été décrits par Irving S. Reed et Gustave Solomon en 1960. Ils travaillent sur des symboles entiers, en général des octets, plutôt que sur des bits isolés, ce qui les rend efficaces contre les dégâts en rafale comme une rayure ou une tache.
La même famille de codes protège les données des CD, DVD et disques Blu-ray, de certaines liaisons de télévision numérique et par satellite, et d’autres codes 2D, dont le Data Matrix ECC 200, l’Aztec Code et le PDF417.
Comment les QR codes l’utilisent
Un QR code traite chaque mot de code de 8 bits comme un élément du corps fini GF(256), construit avec le polynôme primitif x^8 + x^4 + x^3 + x^2 + 1 (hexadécimal 0x11D). Les mots de code de données sont divisés par un polynôme générateur, et le reste devient les mots de code de correction d’erreur qui leur sont ajoutés.
Les codes plus grands répartissent leurs données en plusieurs blocs, chacun avec ses propres mots de code de correction d’erreur. Les blocs sont ensuite entrelacés au moment du placement des mots de code dans la grille, de sorte qu’une seule tache est répartie sur de nombreux blocs au lieu d’en submerger un.
Ce qu’elle peut réparer
Avec n mots de code de correction d’erreur dans un bloc, un décodeur peut corriger jusqu’à n/2 mots de code dont la position est inconnue, ou jusqu’à n mots de code dont la position est connue, appelés effacements. Les cas mixtes suivent la règle selon laquelle chaque erreur compte double et chaque effacement simple.
C’est pourquoi un code dont une zone propre et plane est couverte par un logo peut encore se scanner : un lecteur habile peut traiter la zone couverte comme des effacements, alors que les dégâts aléatoires sont plus difficiles à corriger, car le décodeur doit d’abord les localiser.
- Erreurs inconnues : jusqu’à la moitié du nombre de mots de code EC
- Effacements (positions connues) : jusqu’au nombre de mots de code EC
- Corps : GF(256), polynôme 0x11D
- Les blocs sont entrelacés pour répartir les dégâts en rafale