code BCH

Une suite de 0 et de 1 traverse un canal de transmission. Si plusieurs bits changent en route, le récepteur doit retrouver le message sans savoir d'avance quelles positions ont été touchées.

Un code BCH ajoute avant l'envoi une redondance calculée. Les mots autorisés sont assez éloignés les uns des autres pour que plusieurs changements restent réparables. Plus on veut corriger d'erreurs dans un même mot, plus il faut réserver de place aux symboles de contrôle.

Un code BCH, nommé d'après Bose, Chaudhuri et Hocquenghem, est une famille de codes correcteurs cycliques construits à l'aide de polynômes sur un corps fini. Un bloc d'information est transformé en un mot de code plus long. Le mot obtenu appartient à un ensemble stable par addition et par décalage cyclique : faire passer le dernier symbole en tête produit encore un mot autorisé.

Un code est décrit par sa longueur n, son nombre k de symboles d'information et sa distance minimale d, c'est-à-dire le plus petit nombre de positions séparant deux mots de code distincts. Il corrige avec certitude jusqu'à t erreurs par mot lorsque $2t+1\le d2t+1\backslash leq\; d$. Dans une construction BCH, on choisit un polynôme générateur sur le corps de base ayant pour racines une suite de puissances consécutives d'un élément d'un corps d'extension. Ce choix fixe une distance conçue δ telle que $d\ge \delta d\backslash geq\backslash delta$, d'où le rayon garanti $t_{\mathrm{g}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{n}\mathrm{t}\mathrm{i}}=\lfloor (\delta -1)\mathrm{/}2\rfloor t\_\{\backslash mathrm\{garanti\}\}=\backslash left\backslash lfloor(\backslash delta-1)/2\backslash right\backslash rfloor$. La distance réelle peut être supérieure à la valeur conçue, et la capacité réelle $\lfloor (d-1)\mathrm{/}2\rfloor \backslash left\backslash lfloor(d-1)/2\backslash right\backslash rfloor$ peut donc dépasser ce rayon garanti.

Les codes BCH existent en plusieurs longueurs et sur différents corps finis. Les codes binaires traitent des bits ; d'autres variantes traitent des symboles plus riches. La cyclicité fournit une organisation algébrique commode, tandis que la distance minimale porte la garantie de correction multiple.

Prenons le code BCH binaire (15,7,5) : ses mots ont 15 bits, dont 7 bits d'information, et sa distance minimale vaut 5. Son polynôme générateur est $g(x)=x^8+x^7+x^6+x^4+1g(x)=x^8+x^7+x^6+x^4+1$. On choisit le message polynomial réduit à 1.

1. L'encodage multiplie le message par le polynôme générateur. Ici, $c(x)=1\times g(x)=g(x)c(x)=1\backslash times\; g(x)=g(x)$. En lisant les coefficients de x¹⁴ à x⁰, le mot envoyé est 000000111010001.

2. Pendant la transmission, les bits des positions 7 et 11 passent de 1 à 0. Le mot reçu devient 000000011000001. Il diffère donc du mot envoyé en exactement deux positions.

3. Comme la distance minimale vaut 5, les zones de rayon 2 autour de deux mots de code ne se recouvrent pas. Le mot envoyé est donc l'unique mot de code situé à deux erreurs ou moins du mot reçu. Le décodeur peut restituer 000000111010001.

4. Le contrôle se refait en comptant les différences : la distance entre le mot reçu et le mot corrigé vaut 2. Le mot de code nul 000000000000000 est à distance 3 du mot reçu ; tout mot de code distinct du mot envoyé est également à distance au moins 3, par la distance minimale 5.

Dans une transmission binaire, l'émetteur encode chaque bloc et le récepteur calcule des syndromes à partir du mot reçu. Un BCH convient lorsque le cahier des charges exige la correction de plusieurs bits erronés dans un même bloc.

Pour une mémoire ou un support de stockage, la redondance accompagne les données. Le nombre d'erreurs à corriger et la taille des blocs guident le choix des paramètres ; un code de Hamming suffit souvent si une seule erreur par mot doit être corrigée.

Si l'objectif est seulement de détecter une altération et de demander une nouvelle transmission, un code CRC est une solution distincte. Le BCH devient pertinent lorsque la réparation locale est nécessaire malgré plusieurs erreurs simultanées.

Code de Hamming. Un code de Hamming classique corrige une erreur isolée par mot. Un BCH peut être paramétré pour en corriger plusieurs : dans l'exemple (15,7,5), deux bits altérés restent dans la garantie.

Code CRC. Un CRC sert principalement à détecter qu'un bloc a été modifié ; il ne fournit pas, à lui seul, une garantie de correction. Si le récepteur doit réparer les deux erreurs de l'exemple sans retransmission, il faut un code correcteur tel que le BCH choisi.

Au-delà du rayon garanti. Le BCH (15,7,5) corrige jusqu'à deux erreurs par mot. Avec trois bits altérés, le mot reçu peut être plus proche d'un autre mot de code ; il faut alors signaler l'échec, demander une retransmission ou choisir un code plus robuste.

Distance conçue et distance réelle. Le paramètre δ garantit une borne inférieure, pas toujours la valeur exacte de la distance minimale. Déduire une capacité supérieure exige de connaître d, et non de supposer que la borne est atteinte.

Paramètres incomplets. Dire seulement « code BCH » ne fixe ni la longueur, ni la dimension, ni le nombre d'erreurs corrigibles. Il faut préciser le corps, la longueur et le choix du générateur ou des racines ; les notations peuvent aussi varier selon la convention retenue.

Erreurs groupées. Une garantie portant sur t positions compte les symboles erronés, quelle que soit leur proximité. Un long paquet d'erreurs peut dépasser rapidement ce seuil ; un entrelacement ou un code adapté aux erreurs en rafale devient alors préférable.

La fiche distance de Hamming précise la mesure qui sépare deux mots et fonde le rayon de correction utilisé dans l'exemple.

La fiche code de Hamming présente le cas classique de la correction d'une seule erreur et rend la comparaison des garanties concrète.

L'article Codes correcteurs : garder les erreurs à distance replace l'espacement des mots de code dans une vue d'ensemble de la correction d'erreurs.