Code de Reed-Solomon

Soit un message A constitué de k symboles éléments du corps fini ${\displaystyle \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 ${\displaystyle \alpha }$ ayant la propriété suivante :

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

Ainsi, les éléments non nuls de ${\displaystyle \mathbb {F} _{2^{m}}}$ peuvent s'écrire comme combinaisons linéaires de ${\displaystyle (1,\alpha ,\alpha ^{2},...,\alpha ^{m-1})}$ à coefficients dans {0,1}, mais aussi comme une puissance de ${\displaystyle \alpha }$, entre 0 et ${\displaystyle 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 ${\displaystyle \mathbb {F} _{2^{m}}[X]}$. Ce polynôme est l'information à transmettre et sera encore noté ${\displaystyle A}$.

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

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

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

On définit le polynôme de contrôle ${\displaystyle B}$ comme étant le reste de la division euclidienne de ${\displaystyle A\times X^{2t}}$ par ${\displaystyle 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 ${\displaystyle C=A\times X^{2t}+B}$. Ce polynôme est de degré inférieur ou égal à ${\displaystyle k-1+2t=n-1}$. Il possède la propriété de s'annuler en ${\displaystyle \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)

Les coefficients du polynôme ${\displaystyle 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 ${\displaystyle D}$.

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

Si au moins l'un des ${\displaystyle 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.

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

${\displaystyle E=\sum _{r=1}^{\nu }e_{i_{r}}X^{i_{r}}}$, ${\displaystyle y_{r}=e_{i_{r}}}$ et ${\displaystyle x_{r}=\alpha ^{i_{r}}}$, les ${\displaystyle i_{r}}$ étant des indices distincts pouvant varier entre 0 et n-1.

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

Le nombre d'erreurs ${\displaystyle \nu }$,

les rangs ${\displaystyle i_{r}}$ où sont situées ces erreurs,

les valeurs ${\displaystyle y_{r}}$ de ces erreurs.

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

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

${\displaystyle 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 ${\displaystyle x_{r}}$ et ${\displaystyle 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 ${\displaystyle \Lambda (X)=\prod _{r=1}^{\nu }(1-x_{r}X)}$ dont les racines sont les inverses des ${\displaystyle x_{r}}$. Ce polynôme se développe sous la forme ${\displaystyle \Lambda (X)=1+\lambda _{1}X+\lambda _{2}X^{2}+\dots +\lambda _{\nu }X^{\nu }}$. On peut vérifier que les ${\displaystyle \nu }$ coefficients ${\displaystyle \lambda _{r}}$, inconnus du destinataire, satisfont un système linéaire de ${\displaystyle \nu }$ équations, la j-ème équation étant, pour j variant de 1 à ${\displaystyle \nu }$ :

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

en effet : ${\displaystyle \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 ${\displaystyle \nu }$ inférieure ou égal à t pour laquelle le déterminant de ce système est non nul est précisément le nombre ${\displaystyle \nu }$ égal au nombre d'erreurs transmises. On part donc de ${\displaystyle \nu =t}$, et si le déterminant est nul, on décrémente ${\displaystyle \nu }$ jusqu'à obtenir un déterminant non nul.

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

4) Détermination de la valeur des erreurs : Les ${\displaystyle x_{r}}$ étant désormais connus, on peut résoudre le système dont l'équation générale est ${\displaystyle S_{j}=\sum _{r=1}^{\nu }y_{r}x_{r}^{j}}$ et dont les inconnues sont les ${\displaystyle 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 ${\displaystyle i_{r}}$ et les ${\displaystyle y_{r}}$, on connaît le polynôme ${\displaystyle E,}$ et donc le message initial ${\displaystyle C=D+E}$

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 ${\displaystyle x_{r}}$ sont connues, que les inconnues sont les seules valeurs ${\displaystyle y_{r}}$ et qu'on dispose de 2t équations, on peut corriger l'effacement de ${\displaystyle \nu =2t}$ symboles.

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)

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

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