Code cyclique - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
En mathématiques et en informatique, un code cyclique est un code correcteur linéaire. Ce type de code possède non seulement la capacité de détecter les erreurs, mais aussi de les corriger sous réserve d'altérations modérées. Les mathématiques sous-jacentes se fondent sur la théorie des corps finis, et en particulier les extensions de Galois ainsi que les polynômes. Les codes cycliques, encore appelés contrôles de redondance cyclique (CRC), correspondent à une large famille de codes, on peut citer par exemple le code de Hamming, les codes BCH ou le code de Reed-Solomon.
Contexte
Généralités
L'objectif du code cyclique est la correction automatique de certaines altérations de message. La technique utilisée consiste à plonger le message dans un espace plus vaste pour disposer d'une redondance.
La figure de droite illustre cette approche. Le code de la partie gauche ne dispose pas de redondance (un mot de code est un message codé, c'est une chaîne de lettre d'un alphabet ici égal aux éléments d'un corps fini. Un code est l'ensemble des mots de code n'ayant pas subi d'altération durant la transmission. La longueur du code, une constante, est le nombre de lettres contenu dans un mot de code.) Le code de la figure correspond aux intersection du quadrillage, le mot de code à transmettre est symbolisé par le point vert. Une altération pendant la transmission déplace le message vers un autre mot de code en rouge. Pour le récepteur, le code reçu est licite, il n'existe aucune information permettant de corriger l'erreur.
Si un code correcteur est utilisé, la figure de droite illustre le mécanisme. L'émetteur plonge son message dans un espace plus vaste, le mot de code correspond à un point vert. L'espace dispose maintenant du quadrillage supplémentaire orange. Si la transmission engendre une unique erreur, alors le message reçu devient un point rouge, si l'altération n'est pas plus grande que le déplacement sur un segment du quadrillage. Le récepteur reçoit alors un message rouge, qui n'est pas un mot de code (car le code correspond aux points verts). Sachant qu'un mot de code a été envoyé et sachant que la transmission ne produit qu'une erreur (c’est-à-dire un unique déplacement sur le quadrillage) il existe un moyen de corriger la transmission.
La mesure de la gravité de l'altération est donnée par la distance de Hamming. Elle correspond au nombre de lettres ayant été modifiées. Les points noirs correspondent aux redondances inutiles. Le code de la figure est capable de corriger les altérations uniques. Un point noir, à une distance de deux du code entre dans la zone non interprétable assurément, il représente une redondance inutile. L'objectif d'un bon code correcteur est d'emplir l'espace avec des boules de même rayon qui ne s'intersectent jamais, ici illustrées par les losanges verts. Si une telle configuration est atteinte, le code est dit parfait.
Code linéaire
Un code linéaire dispose d'une structure algébrique plus riche que celle du cadre général des codes correcteurs.
Les alphabets A et A' sont identifiés et munis d'une structure de corps fini. Le cas le plus fréquent consiste à choisir le corps F2 ou l'une de ses extensions finies, on parle alors d'alphabet binaire.
Les ensembles E et F sont naturellement munis d'une structure d'espace vectoriel de dimension respectives k et n. Si Fd désigne le corps fini (cf l'article corps fini) de cardinal d où d est une puissance d'un nombre premier p, alors l'espace vectoriel F est généralement identifié à Fdn.
F est muni d'une distance qui dérive du poids de Hamming. La distance entre deux points de F correspond au nombre de coordonnées non nulles de la différence entre les deux points, dans la base canonique. Un code se décrit par trois paramètres, noté [n, k, δ], n est la dimension du code, k la longueur du code et δ la distance minimale entre deux mots du code. Ces notations sont utilisées dans le reste de l'article.
Enfin, l'application d'encodage φ est choisie linéaire, le code est donc un sous-espace vectoriel.
Corps fini
Si la théorie des codes linéaires apporte une solution élégante avec des exemples parfaits, on peut néanmoins remarquer deux manques. D'une part, elle ne propose pas de méthode pour trouver des codes optimaux, et d'autre part, elle propose un cadre algorithmique faible. Il existe bien une addition naturelle. En revanche le produit externe est souvent pauvre. Le corps le plus usité est F2 ne contenant que deux éléments, 0 qui annule tous les vecteurs et 1 qui les laisse à l'identique. Il ne reste donc que le calcul matriciel.
L'enrichissement algébrique le plus naturel associe à Fd, le corps de l'espace vectoriel, l'extension de dimension m. Ce corps de cardinal d m est une extension de Galois, donc disposant de tout l'arsenal de théorèmes de la théorie associée. Une autre structure naturelle est Fd[X] l'ensemble des polynômes à coefficients dans Fd. Cet anneau est de dimension infinie, en revanche, tout élément non nul de l'extension est racine du polynôme suivant:
![\forall x \in \mathbb F_{d^m}^* \quad P[x]=0 \quad si \; P[X]=X^{d^m -1}-1](https://static.techno-science.net/illustrationWebp/Definitions/autres/e/e162db0ead8b710b13a05a461c82f397_8c1ff35b666fc80c8fbbf8d2fb400343.png)
Une division euclidienne d'un polynôme quelconque par P[X] possède donc pour reste un polynôme de degré strictement inférieur à d m - 1 et ayant même image pour tout élément de l'extension. Sous réserve de choisir comme longueur du code une puissance du cardinal du corps, la structure Fd[X]/P[X], quotient de l'anneau des polynômes par l'idéal engendré par P[X], hérite donc de toutes propriétés nécessaires à l'application de la théorie de Galois.
Dans l'anneau Fd[X]/P[X], la multiplication possède une implémentation logicielle d'exécution particulièrement rapide. Elle correspond à la multiplication des entiers, mais sans retenue et avec la règle Xn-1.X = 1. L'univers algébrique utilisé pour les codes cycliques est celui là.
Les sous-structures compatibles avec les anneaux sont les idéaux. Ce sont, dans le cas de Fd[X]/P[X], des sous-espaces vectoriels. Pour bénéficier de la structure, il est intéressant de se focaliser sur ces idéaux. Ils correspondent aux sous-espaces vectoriels stables par multiplication par le monôme unitaire X. Un idéal I de l'anneau vérifie donc la propriété:
![\forall Q[X] \in \mathbb I \quad X.Q[X] \in \mathbb I](https://static.techno-science.net/illustrationWebp/Definitions/autres/2/206218df595c3ca17b4f7b1a20e44ff0_3babcc7ad1fd4e5f6ce3822ca040ed30.png)
Remarque: par souci de simplicité, X est identifié avec sa classe dans le quotient Fd[X]/P[X]. Cette identification est utilisée dans tout l'article.
Si une notation plus classique est utilisée, Q[X] est noté x comme un mot de code avec les coordonnées (xi) et I est noté C pour code, la propriété devient:
Le terme code cyclique provient de cette condition nécessaire et suffisante pour qu'un espace vectoriel soit un idéal.
Un résultat de la théorie des anneaux affirme que, dans ce contexte, les idéaux sont engendrés par les diviseurs du polynôme P[X]. Or, la théorie des corps finis montre que les diviseurs de P[X] sont exactement la liste des polynômes irréductibles avec un ordre de multiplicité 1 et possédant toutes ses racines dans l'extension de dimension m (à l'exception du polynôme X non représenté). Un idéal est donc engendré par un produit de polynômes irréductibles, scindés dans l'extension, tous différents entre eux et différents de X.
