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. Ce code est dû à Irving S. Reed et Gustave Solomon. Il a notamment été utilisé pour le codage des CDs. vignette|droite|Image de La Joconde, transmis au Lunar Reconnaissance Orbiter. 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 . 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 é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 symbôles 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 ou . 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.