Code de Reed-Solomon

[remi37000]

Bonjour à tous,
je travaille actuellement sur les Datamatrix (code barre bidimensionnel) qui emploient le code correcteur de Reed-Solomon. Je me suis un peu penché sur ce codage, je connais plus ou moins les méthodes qui permettent de construire le polynôme d'erreur mais j'aimerai avant tout savoir pourquoi ce codage ne peut restituer que t symboles parmi les k qui composent le message. Si quelqu'un est capable de me renseigner précisément sur ce sujet, ça m'aiderait beaucoup!!
Merci d'avance!
-----

[grosbedo]

Bonjour,

Je travaille actuellement sur un encodeur/décodeur Reed-Solomon, donc je vais essayer de répondre, mais je ne suis pas un pro des maths. Mais pour résumer, c'est parce que t c'est la distance minimale entre deux messages possibles dans ton champ de Galois.

Pour détailler: quand tu encodes un message avec Reed-Solomon, ça génère code EC (error-correction) qui fait exactement la longueur t = n-k. Mathématiquement, on "insère" ce code EC au début du polynome EC + message, de sorte à ce que les coefficients qui correspondent au code EC aient les degrés les plus petits (x^0, x^1, x^2, x^3, ... x^(t-1)) et les coefficients pour le message sont de plus haute dimension (x^t, x^t+1, ..., x^n).

Du fait du champ de Galois et de la construction du générateur de façon très précise pour nous arranger, ce code EC permet d'augmenter la distance minimale entre deux codewords (EC+message) différents d'une distance de Hamming d'exactement t. Donc, tant qu'on est en-dessous de cette limite dans le nombre d'erreurs qu'on a, alors on peut corriger car on peut encore définir de manière unique quel est le polynome unique qui correspond à notre message partiel. En-dessous de cette limite, alors on ne peut rien garantir, et on ne peut même pas détecter s'il y a une erreur dans le décodage.

À noter que la limite t = n-k est seulement pour les effacements. Pour les erreurs, c'est floor((n-k)/2), et pour les deux en même temps c'est 2*e + v <= (n-k) avec e le nombre d'erreurs et v le nombre d'effacements. Il y a un article sur Wikiversity qui est pas mal si ça t'intéresse:

https://en.wikiversity.org/wiki/Reed...des_for_coders

Enfin, il y a des nouvelles approches dites "list-decoding" qui permettent de décoder au-delà de la limite de Singleton, en générant tous les polynomes solutions possibles, et ensuite en les filtrant pour ne garder que le plus probable. Cela permet de décoder jusqu'à n - sqrt(n*k) et voire même au-délà (c'est encore en recherche). Voir https://en.wikipedia.org/wiki/List_decoding et "Reed-Solomon Error-correcting Codes - The Deep Hole Problem", by Matt Keti, Nov 2012.

[grosbedo]

PS: pas eu le temps de rajouter: détails à placer juste après "et les coefficients pour le message sont de plus haute dimension (x^t, x^t+1, ..., x^n)."

D'intuition, je dirais que ça permet de s'assurer que le plus gros du polynome est encodé dans le code EC au lieu du message, et ça aide beaucoup car on a un dictionnaire réduit de polynomes possibles (à cause du générateur), donc si on peut définir le plus gros du polynome, on peut le récupérer totalement ensuite (la méthode bruteforce marche par exemple, mais c'est beaucoup plus lent). Il ne faut pas oublier qu'on utilise un champ de Galois, donc un champ discret avec des possibilités finies. Cela ne marcherait pas avec des polynomes réels (car on aurait une infinité de polynomes solutions possibles).

--------

Ah et si tu veux tout savoir sur Reed-Solomon, le meilleur bouquin que j'ai jamais trouvé est celui-ci, tu devrais y trouver toutes les réponses (attention, sur google scholar tu ne trouveras qu'un article extrait d'une ancienne version des travaux de Blahut avant le livre, donc soit emprunte soit achètes une version digitalisée en ligne):

Richard E. Blahut, "Algebraic Codes for Data Transmission", 2003

[grosbedo]

Confirmation de ces explications avec plus de détails ici par des pros:

http://www.dsprelated.com/showthread...sp/62362-1.php

[A voir en vidéo sur Futura]

[remi37000]

Merci beaucoup!
Je comprends un peu mieux!

[grosbedo]

Heureux d'entendre que cela a pu vous aider.

Correction: "En-dessous de cette limite, alors on ne peut rien garantir, et on ne peut même pas détecter s'il y a une erreur dans le décodage." -> bien sûr, il faut lire "Au dessus de cette limite" au lieu de "En-dessous".