Code de Reed-Solomon
La correction d'erreur Reed-Solomon est un code de correction d'erreur directe. Il fonctionne par suréchantillonnage d'un polynôme construit à partir des données. Le polynôme est évalué en plusieurs points, et ces valeurs sont envoyées ou enregistrées. L'échantillonnage du polynôme plus souvent que nécessaire rend le polynôme surdéterminé. Tant qu'il reçoit "beaucoup" de points correctement, le récepteur peut récupérer le polynôme original même en présence de "quelques" mauvais points.
Les codes Reed-Solomon sont utilisés dans de nombreux types d'applications commerciales, par exemple dans les CD, DVD et disques Blu-ray, dans les technologies de transmission de données telles que DSL & WiMAX, et dans les systèmes de diffusion tels que DVB et ATSC.
Vue d'ensemble
Les codes Reed-Solomon sont des codes de bloc. Cela signifie qu'un bloc fixe de données d'entrée est transformé en un bloc fixe de données de sortie. Dans le cas du code R-S le plus couramment utilisé (255, 223) - 223 symboles d'entrée Reed-Solomon (chacun de huit bits de long) sont codés en 255 symboles de sortie.
- La plupart des programmes de R-S ECC sont systématiques. Cela signifie qu'une partie du mot de code de sortie contient les données d'entrée sous leur forme originale.
- Une taille de symbole Reed-Solomon de huit bits a été choisie parce que les décodeurs pour des tailles de symbole plus importantes seraient difficiles à mettre en œuvre avec la technologie actuelle. Ce choix de conception oblige la plus grande longueur de mot de code à être de 255 symboles.
- Le code Reed-Solomon standard (255, 223) est capable de corriger jusqu'à 16 erreurs de symbole Reed-Solomon dans chaque mot de code. Comme chaque symbole est en fait constitué de huit bits, cela signifie que le code peut corriger jusqu'à 16 courtes salves d'erreurs dues au décodeur convolutif interne.
Le code Reed-Solomon, comme le code convolutif, est un code transparent. Cela signifie que si les symboles des canaux ont été inversés quelque part le long de la ligne, les décodeurs fonctionneront toujours. Le résultat sera le complément des données d'origine. Cependant, le code Reed-Solomon perd sa transparence si le remplissage virtuel est à zéro. Pour cette raison, il est obligatoire que le sens des données (c'est-à-dire, vraies ou complétées) soit résolu avant le décodage Reed-Solomon.
Dans le cas du programme Voyager, les codes R-S atteignent une performance presque optimale lorsqu'ils sont concaténés avec le code interne (7, 1/2) convolutif (Viterbi). Comme deux symboles de contrôle sont nécessaires pour chaque erreur à corriger, cela donne un total de 32 symboles de contrôle et 223 symboles d'information par mot de code.
En outre, les mots codés Reed-Solomon peuvent être entrelacés par symbole avant d'être codés par convolution. Comme cela permet de séparer les symboles dans un mot de code, il est moins probable qu'une rafale du décodeur de Viterbi perturbe plus d'un symbole Reed-Solomon dans un mot de code.
Idée de base
L'idée clé derrière un code Reed-Solomon est que les données codées sont d'abord visualisées sous forme de polynôme. Le code s'appuie sur un théorème de l'algèbre qui stipule que tout point distinct k détermine uniquement un polynôme de degré au maximum k-1.
L'expéditeur détermine un
polynôme de degré k - 1, sur un champ fini, qui représente les k points de 
données. Le polynôme est ensuite "encodé" par son évaluation en différents points, et ces valeurs sont ce qui est réellement envoyé. Pendant la transmission, certaines de ces valeurs peuvent être corrompues. Par conséquent, plus de k points sont effectivement envoyés. Tant que suffisamment de valeurs sont reçues correctement, le récepteur peut déduire ce qu'était le polynôme original, et décoder les données originales.
De la même manière que l'on peut corriger une courbe en interpolant au-delà d'un écart, un code de Reed-Solomon peut combler une série d'erreurs dans un bloc de données pour récupérer les coefficients du polynôme qui a tracé la courbe originale.
Histoire
Le code a été inventé en 1960 par Irving S. Reed et Gustave Solomon, qui étaient alors membres du laboratoire Lincoln du MIT. Leur article fondateur s'intitulait "Polynomial Codes over Certain Finite Fields". À l'époque où il a été écrit, la technologie numérique n'était pas assez avancée pour mettre en œuvre le concept. La première application, en 1982, des codes RS dans des produits de masse a été le disque compact, où deux codes RS entrelacés sont utilisés. Un algorithme de décodage efficace pour les codes RS à grande distance a été développé par Elwyn Berlekamp et James Massey en 1969. Aujourd'hui, les codes RS sont utilisés dans les protocoles de disque dur, de DVD, de télécommunication et de diffusion numérique.
