Les Codes Correcteurs d'Erreurs BCH
Mon projet info de première année a consisté à implanter le codage et le décodage des codes BCH (Bose-Chaudhuri-Hocquenghem). Cela en C, et en utilisant la librairie gfq (consituée de programmes traitant les corps finis), en cours d'élaboration par Florent Chabaud et Reynald Lercier.
Comme tout code correcteur d'erreur, ce procédé permet de coder un message de manière à pouvoir corriger les erreurs qu'il pourrait subir lors d'une transmission.
La manière de procéder est la suivante: on considère un mot à coder, de longueur k bits (la dimension du code, dans l'exemple que je vais suivre: 268). On lui rajoute des bits (le mot du code ainsi créé atteint N=511 bits, la longueur du code), ce qui est l'objet d'un code correcteur d'erreurs, de sorte qu'il apparaisse une certaine redondance.
Du point de vue théorique, les codes BCH sont aussi et surtout des codes linéaires, c'est à dire que les éléments du code (les mots de 511 bits "corrects" (ie qui proviennent d'un mot initial)) forment un sous-espace vectoriel de GF(2)^N, de dimension k. Cette propriété permet d'avoir des algorithmes de codage, et surtout de décodage performants, ainsi qu'une étude théorique "plus facile". En particulier, on dispose de deux matrices (en fait deux classes, mais dont on considère deux représentants sympathiques): une matrice de contrôle, ou de parité (notée H), dont le noyau est constitué des éléments du code, et une matrice génératrice du noyau de H (notée G). Le minimum des distances (de Hamming) séparant deux éléments du code est appelée distance minimale du code.
Les codes BCH sont basés sur les propriétés des corps finis (dans le cadre de mon projet, je manipule GF(2) et GF(2^M)). Ils sont paramétrables en longueur (dans l'exemple: N=511). Les codes BCH sont également paramétrables par une distance construite "delta" (dans l'exemple: delta=59), qui minore bien cette distance minimale. On voit tout de suite qu'un tel code est capable de détecter au moins d-1 erreurs, et qu'il est E[ (d-1)/2 ] correcteur.
Dans le cas des codes BCH, la matrice de contrôle s'obtient facilement à partir d'une racine primitive alpha de GF(2^M): le coefficient générique de H vaut alpha^(i*j) (0 < i < delta, 0<=j<=N), et elle est de dimension (delta-1)*N. On en déduit facilement la matrice génératrice en calculant son noyau, ce qui nous donne par la même occasion la dimension du code. La partie codage est donc ainsi terminée.
Une fois le mot initial codé, on peut lui faire subir des erreurs, jusqu´à 29 (dans l'exemple) erreurs sont ainsi corrigées. Le processus de décodage se déroule en deux phases: la première consiste à calculer le syndrôme, c'est à dire s=H.c^t, où c est le mot reçu. Si ce syndrôme est nul, c est bien un mot du code. Sinon, en considérant le syndrôme comme un polynôme à coefficients dans GF(2^M), et en appliquant par exemple l'algorithme d'Euclide étendu, à s et à z^delta, on obtient la solution de "l'équation de clé", c'est à dire deux polynômes sigma (polynôme localisateur) et omega (polynôme évaluateur). Dans un deuxième temps, la résolution de sigma nous donne ses racines, qui mises sous la forme alpha^r, nous fournit les bits numérotés r, qui ont été modifiés. On peut ainsi reconstituer le mot du code, et en utilisant G, retrouver le mot initial.
J'ai fait trois programmes: l'un permet d'initialiser un système de codage (à partir de M et delta, il fournit des fichiers qui contiennent entre autres les matrices G et H), qui sera utilisé par les deux autres programmes, qui permettent de coder et décoder, en introduisant un nombre d'erreurs spécifié, à placement aléatoire.
Pour finir, une référence: Les Codes Correcteurs d'Erreurs, de Poli et Huguet.
Retour à ma page principale.
Dernière modification effectuée le 31 Octobre 1996.