Correction d'erreur Reed-Solomon dans les codes QR
Comment fonctionnent les codes Reed-Solomon dans les codes QR : arithmétique en corps de Galois, polynômes générateurs et entrelacement des mots de code.
Correction d'erreur Reed-Solomon dans les codes QR
La correction d'erreur est ce qui rend les codes QR remarquablement résilients. Le moteur mathématique derrière cette résilience est la correction d'erreur Reed-Solomon (RS), un code en bloc basé sur l'arithmétique en corps finis.
Ce que fait Reed-Solomon
Les codes RS ajoutent des mots de code redondants à vos données. Si certains mots de code sont corrompus — par la saleté, les rayures, la décoloration ou un placement de logo intentionnel — le décodeur peut localiser les positions corrompues et reconstituer les données originales. Un code RS ajoutant 2t mots de code de correction d'erreur peut corriger jusqu'à t mots de code corrompus.
Arithmétique en corps de Galois
Les codes RS des codes QR opèrent sur GF(256) — le corps de Galois à 256 éléments. Chaque élément correspond à un octet (0-255), et le corps définit des opérations spéciales d'addition (XOR) et de multiplication (à l'aide d'un polynôme primitif). Le polynôme primitif pour les codes QR est :
x^8 + x^4 + x^3 + x^2 + 1 (décimal 285)
Toute l'arithmétique des mots de code — codage, calcul de syndrome et correction d'erreur — utilise les opérations GF(256).
Polynômes générateurs
L'encodeur crée un polynôme générateur dont les racines sont des puissances consécutives de l'élément primitif. Pour n mots de code de correction d'erreur, le polynôme générateur a un degré n. Le polynôme de données est divisé par le polynôme générateur, et le reste devient les mots de code de correction d'erreur.
Entrelacement des mots de code
Les grands codes QR divisent les données en plusieurs blocs, chacun avec sa propre correction d'erreur RS. Les mots de code des différents blocs sont ensuite entrelacés dans le flux de bits final. Cela répartit l'impact des dommages localisés sur plusieurs blocs, améliorant la récupération face à de grandes zones de dommages contiguës.
Le côté décodage
Lors du décodage, le scanner :
- Calcule les syndromes — si tous les syndromes sont nuls, aucune erreur n'existe
- Utilise l'algorithme de Berlekamp-Massey pour trouver le polynôme localisateur d'erreur
- Applique la recherche de Chien pour trouver les positions d'erreur
- Utilise l'algorithme de Forney pour calculer les amplitudes d'erreur
- Corrige les mots de code erronés
Implications pratiques
| Niveau EC | Mots de code EC (%) | Mots de code corrigibles (%) |
|---|---|---|
| L | ~20 % | ~7 % |
| M | ~38 % | ~15 % |
| Q | ~55 % | ~25 % |
| H | ~65 % | ~30 % |
Le pourcentage « corrigible » représente environ la moitié du pourcentage de mots de code EC, car chaque erreur nécessite deux mots de code EC pour être localisée et corrigée. Si les positions d'erreur sont déjà connues (effacements), un seul mot de code EC par position suffit.
Points clés
- Les codes Reed-Solomon ajoutent des mots de code redondants pour la détection et la correction d'erreur
- L'arithmétique opère en GF(256) à l'aide du polynôme primitif x^8+x^4+x^3+x^2+1
- Chaque erreur corrigible consomme deux mots de code EC
- L'entrelacement entre blocs répartit les dommages localisés
- Le décodage RS utilise les syndromes, l'algorithme de Berlekamp-Massey, la recherche de Chien et l'algorithme de Forney