Code de Reed-Solomon

Le code de Reed-Solomon est un code correcteur basé sur les corps finis dont le principe est de construire un polynôme formel à partir des symboles à transmettre et de le suréchantillonner. Le résultat est alors envoyé, au lieu des symboles originaux. La redondance de ce suréchantillonnage permet au récepteur du message codé de reconstruire le polynôme même s'il y a eu des erreurs pendant la transmission.

Histoire

Ce code est dû à Irving S. Reed et Gustave Solomon^[1]. Il a notamment été utilisé pour le codage des CDs^[2].

Vue d'ensemble

Image de La Joconde, transmise au Lunar Reconnaissance Orbiter^[3]. L'image à gauche, captée par la NASA. À droite, le Code de Reed–Solomon remet de l'ordre dans l'image.

Soient m, n, k, t des nombres entiers strictement positifs tels que $n=2^{m}-1=k+2t$ . Généralement, on prend m = 8 (parfois m = 16), n = 255, k = 239, t = 8. Les codes Reed-Solomon sont des codes par bloc. En effet ils prennent en entrée un bloc de données de taille fixée k, chaque donnée étant un symbole élément du corps fini possédant $2^{m}$ éléments. On ajoute à ce bloc 2t symboles de contrôle, formant ainsi un bloc de sortie de taille fixée égale à n. Ainsi, on a :

m : nombre de bits par symbole. Dans le cas où m = 8, les symboles sont des octets.
k : nombre de symboles d’information, appelé charge utile ;
2t : nombre de symboles de contrôle ou de redondance ;
n: nombre de symboles transmis (charge utile et contrôle).

Grâce à l'ajout des symboles de contrôle, ces codes permettent de corriger deux types d'erreurs :

les erreurs induisant une modification des données, où certains bits passent de la valeur 0 à la valeur 1 et vice versa comme sur le canal binaire symétrique ;
les erreurs provoquant des pertes d'informations aussi appelées effacements, lorsque des paquets d'informations sont perdus ou effacés comme sur le canal binaire à effacement.

On note un codage de Reed-Solomon $RS(n,k)$ ou $RS(n,k,t)$ .

Si la localisation des erreurs n'est pas connue à l'avance — ce qui est le cas en pratique — le codage Reed-Solomon sait corriger t erreurs.

n étant souvent trop important en pratique, une partie des informations peut être remplacée par des zéros avant codage et ne sera pas transmise, mais devra être ajoutée avant décodage. On parle dans ce cas de code Reed-Solomon raccourci (« shortened Reed-Solomon codes »).

On peut également concevoir des codes de Reed-Solomon sur des corps finis quelconques.

Un exemple de code de Reed-Solomon

Il existe plusieurs variantes^[4]^,^[5]^,^[6] du code de Reed-Solomon, développées au cours des dernières décennies dans le but de rendre de plus en plus rapides les procédés de codage et de décodage. Une des variantes possibles est présentée ici.

L'information à transmettre

Soit un message A constitué de k symboles éléments du corps fini $\mathbb {F} _{2^{m}}$ . Ce corps est de caractéristique 2, ce qui signifie qu'il satisfait à la règle de calcul 1 + 1 = 0, ou encore 1 = -1, ou encore qu'il n'y a pas de distinction entre somme et différence. Il possède par ailleurs un élément dit primitif $\alpha$ ayant la propriété suivante :

Les éléments $(1,\alpha ,\alpha ^{2},...,\alpha ^{m-1})$ forment une base de $\mathbb {F} _{2^{m}}$ en tant qu'espace vectoriel de dimension m sur le corps $\mathbb {F} _{2}$ .
$\alpha$ engendre le groupe multiplicatif de $\mathbb {F} _{2^{m}}$

Ainsi, les éléments non nuls de $\mathbb {F} _{2^{m}}$ peuvent s'écrire comme combinaisons linéaires de $(1,\alpha ,\alpha ^{2},...,\alpha ^{m-1})$ à coefficients dans {0,1}, mais aussi comme une puissance de $\alpha$ , entre 0 et $2^{m}-2$ .

Les k symboles constituant le message A sont considérés comme les coefficients d'un polynôme de degré inférieur ou égal à k-1, i.e. un élément de $\mathbb {F} _{2^{m}}[X]$ . Ce polynôme est l'information à transmettre et sera encore noté $A$ .

Le codage

On appelle polynôme générateur le polynôme $G$ de degré 2t défini de la façon suivante :

G(X)=(X+\alpha )(X+\alpha ^{2})\dots (X+\alpha ^{2t})

Ce polynôme admet pour racines les $\alpha ^{i},1\leq i\leq 2t$ .

On définit le polynôme de contrôle $B$ comme étant le reste de la division euclidienne de $A\times X^{2t}$ par $G.$ Ce polynôme est de degré strictement inférieur à 2t. Les coefficients de ce polynôme forment le code de contrôle de l'information A.

On définit alors le polynôme $C=A\times X^{2t}+B$ . Ce polynôme est de degré inférieur ou égal à $k-1+2t=n-1$ . Il possède la propriété de s'annuler en $\alpha ^{i},1\leq i\leq 2t$ . (rappel : on est toujours dans un corps de caractéristique 2, donc + et - ont le même effet)

La transmission du message

Les coefficients du polynôme $C$ sont transmis au destinataire. Au cours de cette transmission, des erreurs portant sur certains coefficients peuvent se produire, et le destinataire reçoit des coefficients formant un polynôme $D$ .

Le destinataire teste alors si, pour tout i entre 1 et 2t, on a bien $D(\alpha ^{i})=0$ . Si c'est le cas, il considère qu'il n'y a eu aucune erreur de transmission et que $D=C$ . Il retrouve l'information A dans les k-1 coefficients des termes de degrés les plus élevés du polynôme $D$ .

Si au moins l'un des $D(\alpha ^{i})$ est non nul, il y a eu erreur de transmission sur au moins l'un des coefficients. Cependant, le destinataire considère que le nombre de coefficients affectés est inférieur ou égal à t. Sous cette hypothèse, il va être capable de reconstituer le message C initial.

La correction des erreurs

Si $D$ est différent de $C$ , soit $E=D+C$ , polynôme de degré inférieur ou égal à n-1, et comportant un nombre $\nu$ de coefficients non nuls. Par hypothèse, on suppose que $\nu$ est inférieur ou égal à t. Posons :

E=\sum _{r=1}^{\nu }e_{i_{r}}X^{i_{r}}

,

y_{r}=e_{i_{r}}

et

x_{r}=\alpha ^{i_{r}}

, les

i_{r}

étant des indices distincts pouvant varier entre 0 et n-1.

$E$ est pour le moment inconnu du destinataire. Il s'agit pour celui-ci de déterminer :

Le nombre d'erreurs

\nu

,

les rangs

i_{r}

où sont situées ces erreurs,

les valeurs

y_{r}

de ces erreurs.

Une fois ces informations reconstituées, le destinataire sera en mesure de déterminer le polynôme $E$ et de reconstituer le message initial $C=D+E$ . Pour cela, on suit les cinq étapes suivantes.

1) Calcul des syndromes : On calcule les 2t quantités $S_{j}=D(\alpha ^{j}),1\leq j\leq 2t$ , appelées syndromes. Comme $E=D+C$ et que les $C(\alpha ^{j})$ sont nuls, on a également :

S_{j}=E(\alpha ^{j})=\sum _{r=1}^{\nu }e_{i_{r}}\alpha ^{ji_{r}}=\sum _{r=1}^{\nu }y_{r}x_{r}^{j}

On dispose ainsi de 2t équations dont les inconnues $x_{r}$ et $y_{r}$ sont au plus au nombre de 2t. Cependant, le système n'est pas linéaire et sa résolution est technique.

2) Détermination du nombre d'erreurs : On considère le polynôme $\Lambda (X)=\prod _{r=1}^{\nu }(1-x_{r}X)$ dont les racines sont les inverses des $x_{r}$ . Ce polynôme se développe sous la forme $\Lambda (X)=1+\lambda _{1}X+\lambda _{2}X^{2}+\dots +\lambda _{\nu }X^{\nu }$ . On peut vérifier que les $\nu$ coefficients $\lambda _{r}$ , inconnus du destinataire, satisfont un système linéaire de $\nu$ équations, la j-ème équation étant, pour j variant de 1 à $\nu$ :

S_{\nu +j-1}\lambda _{1}+S_{\nu +j-2}\lambda _{2}+\dots +S_{j}\lambda _{\nu }=-S_{\nu +j}

en effet : $\left(\sum _{i=1}^{\nu }S_{\nu +j-i}\lambda _{i}=\sum _{r=1}^{\nu }y_{r}(\sum _{i=1}^{\nu }x_{r}^{\nu +j-i}\lambda _{i})=\sum _{r=1}^{\nu }y_{r}x_{r}^{\nu +j}(\Lambda (x_{r}^{-1})-1)=-S_{\nu +j}\right)$

De plus, la plus grande valeur $\nu$ inférieure ou égal à t pour laquelle le déterminant de ce système est non nul est précisément le nombre $\nu$ égal au nombre d'erreurs transmises. On part donc de $\nu =t$ , et si le déterminant est nul, on décrémente $\nu$ jusqu'à obtenir un déterminant non nul.

3) Détermination de l'emplacement des erreurs : Une fois $\nu$ ainsi déterminé, on résout le système, ce qui définit le polynôme $\Lambda$ . On cherche les racines de ce polynôme, dont les inverses donnent les valeurs des $x_{r}$ . Pour chaque r entre 1 et $\nu$ , on cherche la puissance $i_{r}$ de $\alpha$ telle que $x_{r}=\alpha ^{i_{r}}$ . On a ainsi déterminé les rangs $i_{r}$ des erreurs transmises.

4) Détermination de la valeur des erreurs : Les $x_{r}$ étant désormais connus, on peut résoudre le système dont l'équation générale est $S_{j}=\sum _{r=1}^{\nu }y_{r}x_{r}^{j}$ et dont les inconnues sont les $y_{r}$ , permettant de déterminer les valeurs de ces inconnues. Ce sont les valeurs des erreurs commises.

5) Correction du message reçu : Connaissant les $i_{r}$ et les $y_{r}$ , on connaît le polynôme $E,$ et donc le message initial $C=D+E$

Les erreurs d'effacement

Si l'information est inscrite sur un support comme un CD ou un DVD, il peut se produire des erreurs d'effacement. L'erreur est précisément localisée mais on ne peut lire aucune information à cet endroit. On peut cependant reconstituer les symboles effacés en s'aidant là aussi des équations données par les syndromes. Comme les localisations $x_{r}$ sont connues, que les inconnues sont les seules valeurs $y_{r}$ et qu'on dispose de 2t équations, on peut corriger l'effacement de $\nu =2t$ symboles.

Applications

Stockage de données

Pour le CD, on utilise 2 codages de Reed-Solomon (code CIRC pour Cross Interleaved Reed-Solomon Code). On code une première fois avec un code C1 = RS(28, 24), puis on entrelace (ceci permet de répartir l'information afin de mieux résister aux trains d'erreurs consécutives que peut provoquer une rayure qui détruit beaucoup d'octets localement), ensuite on code à nouveau les données entrelacées avec un code C2 = RS(32, 28). L'idée est que le premier code permet d'éliminer le bruit ambiant mais s'il ne peut corriger (par exemple, s'il y a une salve d'erreurs), il efface le bloc (car on peut corriger deux fois plus d'effacements que de caractères faux) et ensuite le code est désentrelacé. Ainsi la perte d'information est diluée sur une grande plage de données ce qui permet au code de corriger ces effacements.

Pour le DVD le principe est le même que pour les CD, on a un code PI= RS(182, 172) et un code PO = RS(208, 192)

Transmission par satellite

Pour le DVB, le codage est RS(204, 188, t=8)

Transmission de données

En ADSL/ADSL2/ADSL2plus, le codage est souvent RS(240, 224, t=8) ou encore RS(255, 239, t=8).

Code QR

Le code Reed-Solomon est utilisé dans les QR code, la correction d'erreur permettant de lire le QR code même si celui-ci est sali ou abimé^[7].

Exemple

pour le DVB, le codage est RS(204, 188, t=8)

Pour 188 (=k) octets en entrée, on ajoute 16(=2 t) octets de correction d'erreur, ce qui donne 204 en sortie du codeur.

8 octets (=t) sur 204 peuvent être corrigés.

Si plus de 8 octets sont détectés comme erronés, le bloc de données utiles est marqué comme défectueux. Aucune erreur n'est alors corrigée

Faiblesse

En raison du faible nombre de symboles que le codage Reed-Solomon peut corriger, ce codage est très mauvais en cas de bruit impulsif de longue durée, ou de bruit aléatoire régulier.

Pour la transmission de données (ADSL, DVB-T), le bruit impulsif peut être dû à des moteurs, relais, lampes à décharge ou tubes d'éclairage, clôture électrique...
Pour le stockage de données (CD, DVD), le bruit impulsif peut être dû à une rayure sur le support.

Utilisation dans un modem avec codeur convolutif

En général, en émission, dans un modem (ADSL, modem satellite IDR/SMS, DVB-S, etc ), le codage Reed-Solomon, renforcé par un entrelaceur est accompagné d'un codeur convolutif. En réception, les erreurs résiduelles non corrigées par le décodeur de Viterbi seront alors désentrelacées dans les blocs d'origines et corrigées par le décodeur Reed-Solomon dans la mesure de son pouvoir correcteur.

Le but du désentrelaceur est de remplacer en réception, une salve d'erreurs regroupées et souvent non corrigeables (bruit impulsif) par une multitude d'erreurs réparties et souvent corrigeables pour le décodeur de Reed-Solomon.

Liens externes

Code Reed-Solomon Principes et programmation du code Reed-Solomon en Java.
William Geisel, Tutorial on Reed–Solomon Error Correction Coding, NASA, Technical Memorandum (1990)

Références

↑ (en) I. S. Reed, G. Solomon, « Polynomial codes over certain finite fields », J. Soc. Indus. Appl. Math., n^o 8,‎ 1960, p. 300-304
↑ Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 8.4 (« Codes BCH »), p. 560-562.
↑ (en) « NASA Beams Mona Lisa to Lunar Reconnaissance Orbiter at the Moon », sur nasa.gov
↑ (en) D. Gorenstein, N. Ziegler, « D class of error-correcting codes in $p^{m}$ symbols », J. Soc. Indus. Math. Appl., n^o 9,‎ 1961, p. 207-2014
↑ (en) W. W. Peterson, « Encoding and error-correction procedures for the Bose-Chaudhuri codes », IRE Trans. Inform. Theory, n^o IT-6,‎ 1960, p. 459-470
↑ (en) Maria Bras-Amoros, « A decoding approach to Reed-Solomon codes from their definition », Amer. Math. Monthly, vol. 125, n^o 4,‎ avril 2018, p. 320-338
↑ Sumit Tiwari, « An Introduction to QR Code Technology », 2016 International Conference on Information Technology, IEEE,‎ décembre 2016, p. 39–44 (ISBN 978-1-5090-3584-7, DOI 10.1109/ICIT.2016.021, lire en ligne, consulté le 28 octobre 2024)

[1] (en) I. S. Reed, G. Solomon, « Polynomial codes over certain finite fields », J. Soc. Indus. Appl. Math., n^o 8,‎ 1960, p. 300-304

[boyer-2] Pascal Boyer, Petit compagnon des nombres et de leurs applications, Calvage et Mounet, 2019, 648 p. (ISBN 978-2-916352-75-6), VI. Cryptographie, chap. 8.4 (« Codes BCH »), p. 560-562.

[3] (en) « NASA Beams Mona Lisa to Lunar Reconnaissance Orbiter at the Moon », sur nasa.gov

[4] (en) D. Gorenstein, N. Ziegler, « D class of error-correcting codes in $p^{m}$ symbols », J. Soc. Indus. Math. Appl., n^o 9,‎ 1961, p. 207-2014

[5] (en) W. W. Peterson, « Encoding and error-correction procedures for the Bose-Chaudhuri codes », IRE Trans. Inform. Theory, n^o IT-6,‎ 1960, p. 459-470

[6] (en) Maria Bras-Amoros, « A decoding approach to Reed-Solomon codes from their definition », Amer. Math. Monthly, vol. 125, n^o 4,‎ avril 2018, p. 320-338

[7] Sumit Tiwari, « An Introduction to QR Code Technology », 2016 International Conference on Information Technology, IEEE,‎ décembre 2016, p. 39–44 (ISBN 978-1-5090-3584-7, DOI 10.1109/ICIT.2016.021, lire en ligne, consulté le 28 octobre 2024)

[1]

[2]

[3]

[4]

[5]

[6]

[7]