Code cyclique 1317411 28944425 2008-04-24T11:20:21Z Jean-Luc W 53231 /* Références */ catégorie En [[mathématiques]] et en [[informatique]], un '''code cyclique''' est un [[code correcteur]] [[code linéaire|linéaire]]. Ce type de code possède non seulement la capacité de détecter les erreurs, mais aussi de les corriger sous reserve d'altérations modérée. Les mathématiques sous-jacentes se fondent sur la théorie des [[corps fini|corps finis]], et en particulier les [[extension de Galois|extensions de Galois]] ainsi que les [[polynôme]]s. Les codes cycliques, encore appelés contrôles de redondance cyclique (CRC), correspondent à une large famille de code, on peut citer par exemple le [[code de Hamming]], les [[code BCH|codes BCH]] ou le [[code de Reed-Solomon]]. ==Contexte== ===Généralités=== {{Article détaillé|Code correcteur}} 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. [[Image:Code correcteur.jpg|thumb|right|500px|Illustration d'un code non correcteur et d'un code correcteur]] 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 subit 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 recepteur, 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'alteration n'est pas plus grande que le déplacement sur un segment du quadrillage. Le recepteur 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 [[boule (mathématiques)|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 [[code parfait|parfait]]. ===Code linéaire=== {{Article détaillé|code linéaire}} Un code linéaire dispose d'une [[structure (mathématiques)|structure]] [[structure algébrique|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 ''F''<sub>2</sub> ou l'une de ses [[extension finie|extensions finies]], on parle alors d'alphabet [[système binaire|binaire]]. Les ensembles ''E'' et ''F'' sont naturellement munis d'une structure d'espace vectoriel de dimension respectives ''k'' et ''n''. Si ''F''<sub>d</sub> 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é à ''F''<sub>d</sub><sup>n</sup>. ''F'' est muni d'une [[distance (mathématiques)|distance]] qui dérive du [[poids de Hamming]]. La distance entre deux points de ''F'' correspond au nombres 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 [[application linéaire|linéaire]], le code est donc un [[sous-espace vectoriel]]. ===Corps fini=== {{Article détaillé|Corps fini}} Si la théorie des codes linéaires apportent 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 ''F''<sub>2</sub> 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 à ''F''<sub>d</sub>, le corps de l'espace vectoriel, l'[[extension algébrique|extension]] de dimension ''m''. Ce corps de cardinal ''d'' <sup>m</sup> est une [[extension de Galois]], donc disposant de tout l'arsenal de théorèmes de la [[théorie de Galois|théorie]] associée. Une autre structure naturelle est ''F''<sub>d</sub>[''X''] l'ensemble des polynômes à coefficients dans ''F''<sub>d</sub>. Cet anneau est de dimension infinie, en revanche, tout élément non nul de l'extension est racine du polynôme suivant: <center><math>\forall x \in \mathbb F_{d^m}^* \quad P[x]=0 \quad si \; P[X]=X^{d^m -1}-1</math></center> 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'' <sup>m</sup> - 1 et ayant même image pour tout élément de l'extension. Sous reserve de choisir comme longueur du code une puissance du cardinal du corps, la structure ''F''<sub>d</sub>[''X'']/''P''[''X''], quotient de l'[[anneau (mathématiques)|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 ''F''<sub>d</sub>[''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 ''X''<sup>n-1</sup>.''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 ''F''<sub>d</sub>[''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é: <center><math>\forall Q[X] \in \mathbb I \quad X.Q[X] \in \mathbb I </math></center> Remarque: ''par souci de simplicité, ''X'' est identifié avec sa classe dans le quotient ''F''<sub>d</sub>[''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 (''x''<sub>i</sub>) et I est noté ''C'' pour code, la propriété devient: <center><math>\forall (x_{n-1}, x_{n-2},\cdots,x_1, x_0) \in C \quad (x_{n-2}, x_{n-3},\cdots,x_0,x_{n-1}) \in C </math></center> 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 ideal 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''. ==Définition== :* Un code linéaire sur ''F''<sub>d</sub> et de paramètres [''n'', ''k'', δ] est dit '''cyclique''' si l'[[espace vectoriel]] est muni de la structure d'[[anneau_(mathématiques)|anneau]] ''F''<sub>d</sub>/''P''[''X''], avec ''P''[''X''] = ''X''<sup>n</sup> - 1, et si le code ''C'' est un [[idéal]] de dimension ''k'' de distance minimale δ. Dire que le code est un idéal revient à dire qu'il est cyclique, c’est-à-dire qu'il vérifie la propriété suivante : <center><math>\forall (x_{n-1}, x_{n-2},\cdots,x_1, x_0) \in C \quad (x_{n-2}, x_{n-3},\cdots,x_0,x_{n-1}) \in C </math></center> Dans ce cas, la longueur du code est toujours une puissance du cardinal du corps de base moins un. Dans la pratique, la longueur du code est une puissance du cardinal du corps, souvent égal à deux et le dernier bit est un [[bit de parité]]. On suppose dorénavant que ''C'' est un code cyclique de paramètres [''n'', ''k'', δ] sur le corps ''F''<sub>d</sub> et qu'il existe ''m'' tel que ''d'' <sup>m</sup> - 1 est égal à ''n'', α désigne une racine primitive de l'extension ''F''<sub>n + 1</sub> de ''F''<sub>d</sub>. ==Code cyclique et code parfait== ===Distance minimale et code binaire=== {{Article détaillé|polynôme cyclotomique}} [[Image:Minitel1.jpg|thumb|right|250px|Le Minitel 1, sorti en 1982]] Dans le cas des [[code binaire|codes binaires]], les polynômes cyclotomiques d'indice ''n'' à coefficients dans ''F''<sub>2</sub> engendrent des codes cycliques ''parfaits'', de distance minimale égale à trois. Ce type de code est adapté pour les petites perturbations relativement fréquentes. Chaque mot peut comporter une unique erreur, elle sera corrigée. Un code de cette nature est, par exemple utilisé pour le [[minitel]]<ref>P. Arnoult ''Minitel, codage de l'information et corps finis'' Pour la science N°125 Mars 1988</ref>, c'est un [[code BCH]] sur 17 [[octet]]s. La théorie de Galois assure que l'extension ''F''<sub>n</sub> de ''F''<sub>2</sub> possède un [[théorème de l'élément primitif|élément primitif]] α, et donc ''F''<sub>n</sub> est égal à ''F''<sub>2</sub>[α]. L'élément α est générateur du groupe multiplicatif, son polynôme minimal est donc un polynôme cyclotomique Φ<sub>n</sub>[X] d'indice ''n'' sur ''F''<sub>d</sub>. Son degré est égal à ''m'' car α est un élément primitif. Ce polynôme remplit les conditions d'optimalité. :* L'idéal ''C'' engendré par Φ<sub>n</sub>[X] est un code cyclique. De plus : :* L'idéal ''C'' engendré par Φ<sub>n</sub>[X] possède les paramètres suivant [2<sup>m</sup> - 1, 2<sup>m</sup> - ''m'' - 1, 3]. Le code associé est donc un code binaire de [[Hamming]]. Ce résultat est vrai uniquement parce que le code est binaire. Considérons par exemple ''F''<sub>27</sub> = ''F''<sub>3</sub>[α] où α est un générateur primitif de l'extension. L'ordre de α est égal à 26, donc α<sup>13</sup> est une [[racine carrée]] de l'unité, différente de 1. α<sup>13</sup> est donc égal à -1. Le polynôme ''X''<sup>13</sup> - 1 admet α pour racine, c'est donc un multiple de son polynôme cyclotomique et il est élément du code. Pourtant son poids est égal à deux. Ce sont donc les spécificités de la caractéristique 2 qui assurent la véracité de la proposition. :* L'idéal ''C'' engendré par Φ<sub>n</sub>[X] est code ''parfait''. Dans le cas général, la ''borne du singleton'' (cf [[code linéaire]]) n'est pas atteinte. Considérons en effet, le cas où ''m'' est égal à 7. La longueur ''n'' du code est égale à 127, la dimension ''k'' du code à 120 et la distance minimale δ à trois. On en déduit: <center><math>n - k = 7 \neq \delta + 1 = 4\;</math></center> {{boîte déroulante|align=left|titre=Démonstrations|contenu= :* '''L'idéal ''C'' engendré par Φ<sub>n</sub>[X] est un code cyclique.''' Les polynômes cyclotomiques, pour les corps de [[caractéristique d'un anneau|caractéristique]] finis, ne sont pas toujours les mêmes que ceux du même indice sur les [[nombre rationnel|nombres rationnels]]. Par exemple, pour sur ''F''<sub>2</sub>, le polynôme cyclotomique d'indice 127 possède comme [[corps de décomposition]] le corps ''F''<sub>128</sub> de dimension 7 sur ''F''<sub>2</sub>. Tout polynôme cyclotomique d'indice 127 est donc de degré sept. Sur les nombres rationnels, comme 127 est premier, le polynôme cyclotomique est de degré 126. Sur ''F''<sub>2</sub> il en existe 18, tous de degré 7 et dont le produit s'identifie au polynôme cyclotomique de même indice à coefficients sur les entiers. Montrer que ''C'' est un code cyclique revient à montrer que Φ<sub>n</sub>[X] est un diviseur de ''X''<sup>n</sup> - 1. Si (α<sub>i</sub>) est un représentant de chaque classe de conjugaison (cf le paragraphe [[Endomorphisme de Frobenius#Polynôme minimal et corps fini|Polynôme minimal et corps fini]] de l'article [[Endomorphisme de Frobenius]]) à ''m'' éléments, l'égalité suivante montre la relation de divisibilité recherchée: <center><math>X^n-1=(X-1).\prod_{\alpha_i} \phi_{\alpha_i}[X]</math></center> Ce qui achève la démonstration. :* '''La distance minimale δ de l'idéal ''C'' engendré par Φ<sub>n</sub>[X] est au moins égale à 3, si le code est binaire.''' Considérons un polynôme ''Q''[''X''] de ''F''<sub>d</sub>[''X''] ayant exactement deux monômes à coefficients non nuls et ayant α pour racine: <center><math>Q[X]=X^{h+k}+X^k=X^h.(X^k + 1) \quad h \in \mathbb N \; k\in \mathbb N^*</math></center> Comme α est racine du polynôme ''Q''[''X''], l'égalité α<sup>k</sup> = 1 est vérifiée. Comme α est un élément primitif du [[groupe cyclique]] ''F''<sub>n</sub><sup>*</sup> ''k'' est un multiple de ''d'' <sup>m</sup> - 1. En conséquence, l'image du polynôme ''Q''[''X''] dans l'espace vectoriel est nulle. Cela signifie que l'espace vectoriel ne contient aucun mot de code ayant un poids égal à deux. De plus, les seuls monômes ayant α pour racine sont ceux ayant une puissance multiple de son [[ordre multiplicatif]] égal à ''n'' - 1, leurs images dans l'espace vectoriel sont donc encore nulles. :* '''L'idéal ''C'' engendré par Φ<sub>n</sub>[X] est code ''parfait'' si le code est binaire.''' Soit ''P'' le [[Sous-espace supplémentaire|suplémentaire]] du code composé par tous les polynômes de degré strictement inférieur à ''m'', ''S'' la boule de centre le vecteur nul et de rayon 1 et φ l'[[Fonction (mathématiques)|application]] de ''S'' dans ''P'' qui à un polynôme associe son reste par la [[division euclidienne]] par le polynôme Φ<sub>n</sub>[''X'']. L'application est linéaire, elle est [[injective]] car si deux polynômes ont même image par φ leur différence est un mot de code ayant un poids égal à deux ou à 0. Comme aucun mot de code n'a de poids égal à deux d'après le paragraphe précédent, leur différence est nécessairement nulle. ''P'' et ''S'' ont même cardinaux, égal à ''n'' + 1 c’est-à-dire 2<sup>m</sup>. En effet ''S'' contient ''n'' monômes et le polynôme nul, et ''P'' est un espace vectoriel de dimension ''m''. L'application φ est donc une [[bijection]]. Considérons l'ensemble des boules de rayon 1 pour la distance de Hamming. Le paragraphe précédent montre qu'elles sont toutes disjointes. Il suffit alors de démontrer que tout polynôme est élément d'une de ces boules. Soit ''Q''[''X''] un polynôme quelconque et ''R''[''X''] le reste de sa division euclidienne par Φ<sub>n</sub>[''X'']. ''R''[''X''] est élément de ''P'', il existe un élément ''M''[''X''] de ''S'', c’est-à-dire un polynôme de poids égal à 0 où à 1, tel que φ(''R''[''X'']) = ''M''[''X'']. En effet, φ est une bijection de ''S'' dans ''P''. Le polynôme ''Q''[''X''] - ''M''[''X''] est un mot de code, car ses deux facteurs ont même reste par la division euclidienne par Φ<sub>n</sub>[''X'']. Comme le poids de ''M''[''X''] est inférieur ou égal à un, on a montré que ''Q''[''X''] est à une distance inférieure ou égale à 1 d'un mot de code. ''Q''[''X''] est donc dans une boule de centre un élément du code et de rayon 1. Ce qui achève la démonstration. :* '''La distance minimale δ de l'idéal ''C'' engendré par Φ<sub>n</sub>[X] est au moins plus égal à 3, si le code est binaire.''' Si le paramètre δ est plus grand que trois, alors il existe au moins un élément qui n'est dans aucune boule de centre un mot du code et de rayon 1. Or la proposition précédente démontre que l'ensemble de ces boules forme une partition de l'espace vectoriel. Ce qui prouve l'impossibilité et achève la démonstration. }} ===Code BCH=== {{Article détaillé|Code BCH}} Si le contexte précédent possède de nombreuses applications industrielles, il présente néanmoins des limitations justifiant l'utilisation d'autres méthodes. La solution précédente s'appuie sur les propriétés de la caractéristique 2. Il peut être utile d'utiliser d'autres corps finis que ceux multiple de deux. Cette contrainte est d'importance relativement faible dans l'industrie, les codes binaires sont en effet largement répandus. En revanche, une telle approche ne permet que la résolution d'une unique erreur dans un mot. Cette limitation n'est pas compatible avec, par exemple, le cahier des charges des [[disque compact|disques compacts]]. Un disque compact peut subir des rayures ou être localement recouvert d'une poussière. Une suite de lettres erronées peut posséder une longueur égale à 4.096. La théorie des corps finis permet néanmoins de proposer une solution ''MSD'' c’est-à-dire qui atteint la [[Code MDS|borne du singleton]]. Elle se fonde sur un calcul réalisé la première fois par le mathématicien [[Alexandre-Théophile Vandermonde|Vandermonde]] <small>([[1735 en science|1735]] - [[1796 en science|1796]])</small> pour résoudre l'équation cyclotomique<ref>[[Alexandre-Théophile Vandermonde|Vandermonde]] ''Mémoire sur la résolution des équations'' (1771)</ref> dans le cas de la caractéristique zéro. Ce calcul reste d'actualité pour les corps finis. Dans la suite du paragraphe Δ désigne un entier tel que 1 < Δ < n + 1 et β désigne un élément de ''F''<sub>n+1</sub> tel que ses Δ premières puissances soit toutes distinctes :* Un polynôme à coefficients dans ''F''<sub>d</sub> dont Δ puissances successives et distinctes de β sont racines et sans racine multiple, engendre un code cyclique ''C'' dont la distance minimale δ est supérieure ou égale à Δ + 1. Remarque:''La propriété du paragraphe précédent est une conséquence de cette proposition. En effet, les propriétés de l'[[automorphisme de Frobenius]] démontre que si α est racine du polynôme cyclotomique, alors α<sup>2</sup> l'est aussi dans le cas des corps binaires.'' Cette proposition est à la base d'une famille de codes dit [[code BCH]] ''(pour Bose, Ray-Chaudhuri, Hocquenghem)'' :* Un '''Code BCH''' de '''longueur prescrite Δ''' est un code cyclique à coefficients dans ''F''<sub>d</sub> et de longueur ''n'' tel qu'il existe un entier ''b'' et dont le polynôme générateur ''G'' vérifie l'égalité suivante. Si ''b'' est égal à un 1 le code est dit '''BCH au sens strict'''. <center><math>G[X]=ppcm(\Phi_b[X], \Phi_{b+1}[X],\cdots ,\Phi_{b+\Delta-2}[X])\;</math></center> Ici Φ<sub>i</sub>[''X''] désigne le polynôme cyclotomique ayant α<sup>i</sup> pour racine. Un code BCH ne permet pas, en général, la génération de codes ''parfaits''. Considérons l'extension binaire de dimension 7 et le code BCH au sens strict de longueur prescrite 5. Son polynôme générateur est le produit de deux polynômes de degré 7, celui ayant α comme racine (et donc aussi α<sup>2</sup> et α<sup>4</sup>) et celui ayant α<sup>3</sup>. Il corrige effectivement deux erreurs, mais la boule de centre 0 et de rayon 2 contient 1 + 127 + (127*126)/2 soit 8 129 points, alors qu'un supplémentaire du code est isomorphe à l'espace des polynômes de degré strictement inférieur à 14 soit 16 384. Les redondances sont plus de deux fois plus vastes que la boule de rayon deux. Certains code BCH sont néanmoins parfaits. Considérons par exemple l'[[extension quadratique]] de ''F''<sub>3</sub>. Sa boule unité contient 1 + 26 éléments soit 27. Le polynôme cyclotomique de racine α contient α<sup>3</sup> comme deuxième racine, celui contenant α<sup>2</sup> contient α<sup>6</sup> comme deuxième racine et le produit des deux polynômes engendre un code de distance minimale 4 et peut donc corriger une unique erreur. Un supplémentaire est isomorphe à l'espace des polynômes de degré inférieur ou égal à 3, et contient donc 27 éléments, autant que la boule unité, le code est donc ''parfait''. {{boîte déroulante|align=left|titre=Démonstration|contenu= :* '''Un polynôme à coefficients dans ''F''<sub>d</sub> dont Δ puissances successives distinctes de β sont racines et sans racine multiple, engendre un code cyclique ''C'' dont la distance minimale δ est supérieure ou égale à Δ + 1.''' Considérons un polynôme ''P''[''X''] de poids de hamming inférieur ou égal à Δ et élément du code. <center><math>P[X]=a_{\Delta -1}.X^{p_{\Delta -1}} +a_{\Delta - 2}.X^{p_{\Delta -2}}+\cdots + a_1.X^{p_1}+a_0.X^{p_0}</math></center> Soit β<sup>b</sup>, β<sup>b+1</sup>, ...,β<sup>b+Δ-1</sup> la suite des Δ racines successives du polynôme générateurs. Puisque ''P''[''X''] est un mot de code, il possède les éléments de la suite comme racine. Si l'on utilise les notations suivantes: <center><math>\forall i \in [0 ,\Delta -1] \quad \alpha_i=a_i.\beta^{bp_i}\quad et \quad \zeta_i=\beta^{p_i} </math></center> Les égalités ''P''[β<sup>b+i</sup>] = 0 deviennent: <center><math>\forall i \in [0 ,\Delta -1] \quad \sum_{j=0}^{\Delta -1}\alpha_j.\zeta_j^i = 0</math></center> Si ''A'' est le vecteur colonne de coefficients α<sub>i</sub> et si ''B'' est la matrice de coefficients ζ<sub>j</sub><sup>i</sup>. Les égalités précédentes s'écrivent sous forme matricielles: ''B''.''A'' = 0. Or ''B'' est la [[Matrice transposée|transposée]] d'une [[matrice de Vandermonde]]. Comme tous les ζ<sub>j</sub> sont distincts, la matrice est inversible. Ceci démontre que ''A'' et le vecteur colonne nul, et donc les coefficients ''a'' <sub>i</sub> sont tous nuls. En conclusion, l'unique mot du code ''P''[''X''] de poids inférieur ou égal à Δ est le polynôme nul. La proposition est donc démontrée. }} ===Code de Reed-Solomon=== {{Article détaillé|code de Reed-Solomon}} [[Image:CD autolev crop.jpg|200px|thumb|right|Les ''CD'' utilisent un code de Reed-Solomon capable de corriger jusqu'à 4.096 [[bit]]s erronés consécutifs]] Si la propriété précédente ne permet pas d'obtenir assurément des codes MDS, l'approche BCH peut être enrichie pour pallier cette difficulté. Considérons par exemple le corps ''F''<sub>64</sub>. Il peut être vu comme l'extension quadratique de ''F''<sub>8</sub>. Alors ''d'' est égal à 8 et ''m'' à 2. L'espace vectoriel associé est un espace de dimension ''d'' <sup>m</sup> égal 63 sur ''F''<sub>8</sub>, soit une longueur de 189 en code binaire. Si α désigne un élément primitif du corps ''F''<sub>8</sub>, alors le polynôme ''G''[''X''], défini par : <center><math>G[X]=X^8-1=(X-\alpha).(X-\alpha^2).(X-\alpha^3).(X-\alpha^4).(X-\alpha^5).(X-\alpha^6).(X-\alpha^7).(X-1)\;</math></center> est un diviseur de ''X''<sup>63</sup> - 1. L'idéal associé est donc un code cyclique ''C''. Le théorème précédent montre que ce code possède une distance minimale de 9. Il admet comme paramètres [63, 55, 9]. C'est un code satisfaisant l'égalité de la ''borne du singleton'' (cf le paragraphe [[Code linéaire#Borne du singleton et code MDS|Borne du singleton et code MDS]] de l'article [[Code linéaire]]). Considéré comme un code binaire, il corrige jusqu'à 12 erreurs consécutives sur un code de dimension 189 et de longueur 175. Cette idée est à la base du '''code de Reed-Solomon'''. :* Un '''Code de Reed-Solomon de distance construite Δ''' avec 1 < Δ < ''n'' est un code BCH sur un corps ''F''<sub>n+1</sub> de dimension ''n'' généré par un polynôme ''G''[''X''] défini par: <center><math>G[X]=(X-\alpha^b).(X-\alpha^{b+1}).\cdots .(X-\alpha^{b+\Delta-2})\quad avec \; b\in \mathbb N^*\;</math></center> La proposition du paragraphe précédent montre que : :* Un Code de Reed-Solomon de distance construite Δ sur ''F''<sub>n+1</sub> possède pour paramètres [''n'', ''n'' - Δ + 1, Δ]. Un tel code est ''MDS''. Le code est ''MDS'' pour ''Minimum Distance Séparable'' si et seulement si la [[borne du singleton]] est atteinte. Pour permettre de larges redondances avec une bonne optimalité, trois autres méthodes peuvent être ajoutées, le code raccourci, le code démultiplié et l'entrelacement. Le ''Code CIRC''<ref>J.P. Zanotti ''Codage d'un signal audionumérique sur un support à lecture optique, erreurs au décodage et codes M.S.D'' Mémoire de D.E.A. Université d'Aix Marseille, 1992</ref> utilisé pour le [[disque compact]] est un code de Reed-Solomon sur le corps ''F''<sub>256</sub> utilisant ces trois outils. ==Implémentation== ===Matrice génératrice=== {{Article détaillé|Matrice génératrice}} ===Contrôle=== ==Exemple== ==Notes et références== {{Code correcteur}} ===Notes=== <references /> ===Liens externes=== * {{fr}} [http://zanotti.univ-tln.fr/enseignement/divers/chapter3.html Code correcteur C.I.R.C] par J.P. Zanotti * {{fr}} [http://www.univ-lille1.fr/bustl-grisemine/pdf/articles/A1998-14.pdf L'algèbre et la correction des erreurs] par Dany-Jack Mercier Université Antilles-Guyane * {{fr}} [http://www.math.u-bordeaux.fr/~zemor/codes06.pdf Code Linéaire] Université de Bordeaux * {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/code.pdf Cours de code] par Christine Bachoc Université de Bordeaux * {{fr}} [http://agreg-maths.univ-rennes1.fr/documentation/docs/codes.pdf Code correcteur] par M. Coste, A. Paugam, R. Quarez Université de Lille ===Références=== * FJ MacWilliams & JJA ''Sloane The Theory of Error-Correcting Codes'' North-Holland, 1977 * A Spataru ''Fondements de la Théorie de l'Information'' Presses Polytechniques Romandes, 1991 * M. Demazure ''Cours d'algèbre'' Cassini, 1997 {{Portail|mathématiques|informatique|sécurité informatique}} [[Catégorie:Détection et correction d'erreur]] [[Catégorie:Corps fini]] [[de:Zyklischer Code]] [[en:Cyclic code]] [[ja:巡回符号]] [[ru:Циклический код]]