Code de Reed-Solomon

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

Le code de Reed-Solomon est un code correcteur basé sur les corps de galois dont le principe est de construire un polynôme à 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 recepteur du message encodé de reconstruire le polynôme même s'il y a eu des erreurs pendant la transmission.


Sommaire

[modifier] Histoire

Ce code est dû à Irving S. Reed et Gustave Solomon.

[modifier] Principe intuitif du codage Reed-Solomon

Imaginons un bloc de 3 octets de long et que l'on transmet: 02. 09. 12.

On ajoute deux octets de redondance. Le premier est la somme des trois octets (=23) Le deuxième est la somme pondérée des 3 octets : chaque octet est multiplié par son rang : 2*1 + 09*2 + 12*3 soit 56. A la sortie du codeur le bloc devient 02. 09. 12. 23. 56.

Suite à une perturbation , le récepteur reçoit le bloc : 02. 13. 12. 23. 56.

Le décodeur fait la somme simple 02+13+12=27 et la somme pondérée 2*1 + 13*2 + 12*3=64. La différence des sommes simples (27-23) donne la valeur de l'erreur (=4) et la différence des sommes pondérées divisée par l'erreur est égale à au rang de l'erreur ((64-56)/4=2). Il faut donc retirer 4 à l'octet de rang 2

Sans erreur ajoutée, la différence des sommes simples et sommes pondérées est nulle dans les 2 cas

[modifier] Propriétés du codage Reed-Solomon

La longueur maximale d’un code de Reed – Solomon est définie comme :

n=k+2t

n = 2m − 1

Avec : m : nombre de bits par symbole

k : nombre de symboles d’information, appelé charge utile

n: nombre de symboles transmis (charge utile et correction d'erreur)

2t : nombre de symboles de contrôle;

Si la localisation des erreurs n'est pas connue à l'avance - et c'est le cas en pratique -le principe du codage Reed-Solomon fait qu'il sait corriger (n-k)/2 erreurs


En général, un symbole sera un octet et donc S=8 (car un octet = 8 bits)

n étant souvent trop important (255) pour l'application utilisée, une partie des informations peut être remplacée par des zéros avant encodage 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)

Souvent, on a T = 8, n = 255 (au max), k = 239 (max)

On note un codage RS par RS (n,k) ou RS (n,k,t)

[modifier] Applications

  • Stockage de données

pour le CD, on utilise 2 codage de Reed-Solomon, on code une premiere fois avec un code C1 = RS (28, 24) puis on entrelace (ceci permet de répartir l'information afin de mieux résister au bouffés d'erreurs que peut provoquer une rayure qui détruit beaucoup d'octet localement) ensuite on code a nouveau les données entrelacé avec un code C2 = RS (32, 28). L'idée est que le premier code permet d'éliminer le bruit ambiant mais si il ne peut corriger (si il y a une bouffée d'erreur) il efface le bloc (car ont peut corriger deux fois plus d'effacement que de caractères faux) et ensuite le code est desentrelacer ainsi la perte d'information est dilué sur une grande plage de données ce qui permet au code de corriger ces effacement.

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, le codage est souvent RS (240,224,t=8) ou encore RS (255,239,t=8), dans l'[ADSL 2+|ADSL 2]] c'est un Turbo code qui est utilisé.

[modifier] Exemple de Reed-Solomon

pour le DVB, le codage sera renseigné RS (204, 188) ou encore RS (204, 188, 8)

Pour 188 (=k) octets en entrée, on ajoute 16(=2t) 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

[modifier] Faiblesse du codage Reed-Solomon

Suite au 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, néons, clôture électrique.

- pour le stockage de données (CD, DVD), le bruit impulsif peut être dû à une griffe sur le support.


[modifier] Utilisation pratique du codage Reed-Solomon dans un modem avec codeur convolutif

Image:Synoptique_de_modem_avec_reed-solomon.png


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

[modifier] Lien externe