[PDF] Codes correcteurs derreurs muni de la distance de

View - Download Codes correcteurs derreurs

Previous PDF

Next PDF

Codes correcteurs d'erreurs

Christophe Ritzenthaler

Sources.Le cours Codes correcteurs de Coste, Paugam et Quarez disponible sur le web a l'adressehttp://agreg-maths.univ-rennes1.fr/documentation/docs/codes.pdf. Les livres `An introduction to error correcting codes with applications' de Vanstone et van Oorschot et `Error-correcting codes and nite elds' de Pretzel. Les codes correcteurs ont ete introduits pour corriger les erreurs de transmission ou de lecture de donnees numeriques, ou les erreurs survenant au cours de leur inscription sur un support physique (bande, CD) ou encore lorsque les donnees subissent une alteration sur le support de stockage. Voici quelques domaines ou ils sont appliques : | transmissions spatiales; | minitel; | codes barres; | disque compact et DVD; | communications par internet.

1 Codes et distance de Hamming

Les messages transmis sont supposes decoupes en blocs (ou mots) de longueurnecrits avec l'alphabetf0;1g. Uncode(binaire) est un sous-ensembleCde l'ensemblef0;1gnde tous les mots possibles. On dit quenest la longueur deC. Ladistance de Hammingentre deux motsx= (x1;:::;xn) ety= (y1;:::;yn), que l'on notera d(x;y), est le nombre d'indicesitels quexi6=yi. C'est bien une distance surf0;1gn. La distance minimumdu codeCest le minimum desd(x;y) pourxetydes mots dierents de C(on suppose queCa au moins 2 mots!). On la notera toujoursd.

Exemple 1.ConsidereC=fc0;c1;c2;c3gavec

c

0= (00000); c1= (10110); c2= (01011); c3= (11101):

C'est un code de longueur5et de distanced= 3.

Le motc2Cest emis et, apres d'eventuelles erreurs de transmission, le motr2 f0;1gn est recu. On decode le motrselon le principe du maximum de vraisemblance, c.-a-d. qu'on le decode comme un mot deCa distance minimum der. On dit queCestt-correcteur (ou corrigeterreurs) quand toute erreur portant sur au plustbits est corrigee correctement. On voit donc que le codeCestt-correcteur si et seulement si les boules fermees (dansf0;1gn muni de la distance de Hamming) de centres les elements deCet de rayontsont disjointes, ou encore si et seulement si la distance minimumddeCveried2t+ 1. Il est souvent dicile de calculer la distance minimale et plus encore de decoder un mot sans structure additionnel c'est pourquoi on prefere travailler avec des codes lineaires. 1 Remarque 1.Supposons que#C= 2k. Le rapportk=ns'appelle le taux de transmission du code. Soit

C(p) = 1 +plog2p+ (1p)log2(1p):

Un theoreme de Shannon montre que pour une probabilite d'erreurp < :5a chaque bit, il existe un code dont le taux de transfert est inferieur mais arbitrairement proche deC(p)qui peut corriger tout message avec une probabilite arbitrairement proche de1. Par exemple si p=:001, on aC(p) =:986donc en ajoutant a peine15bits pour1000bits transmis on peut arriver a une correction arbitrairement proche de1. Bien s^ur le theoreme de Shannon ne dit pas comment construire de tels codes.

2 Codes lineaires

2.1 Denitions

On noteF2le corps a deux elements 0 et 1. Les mots de longueursnsont les elements de F n2, que l'on ecrira comme des vecteurs lignes. Un code lineaire de longueurnest un sous- espace vectorielCFn2. La lettrekdesignera toujours la dimension deC(comme espace vectoriel). Le nombre de mots du codeCest 2k. Lepoidsd'un motx= (x1;::::;xn)2Fn2, notew(x), est le nombre d'indicesitels quexi6= 0. Commed(x;y) =w(xy), la distance minimumdd'un code lineaireCest le minimum des poidsw(x) pourx2Cnon nul. (On suppose queCn'est pas le code nul.) On regroupe les trois parametresn;ketdd'un code lineaireCen disant queCest de type (n;k;d). Lemme 2.1([Dem, Prop.9.1],[Pre, 18.4]).On a toujoursd+kn+1(borne de Singleton). Demonstration.SoitVle sous espace deFn2engendre par les vecteurs donc lesd1 premieres coordonnees sont nulles. Considerons le codeC\V. Sa longueur estnd+1. Montrons que sa dimension est toujoursk. En eet sinon, cela veut dire qu'il existe une relation lineaire entre leskvecteurs engendrantCa valeur dans un supplementaire deV. Mais ceci veut dire qu'il existe un element deCde poidsd1, ce qui est exclu. Ainsi on aknd+ 1, ce

qu'on voulait.La borne de Singleton quantie le fait qu'on ne peut pas avoir a la fois le beurre (une capa-

cite de correction importante) et l'argent du beurre (un nombre de mots de code important), pour une longueurnxee. Remarque 2.Il existe d'autres bornes. Par exemple la borne de Hamming. SiBest la boule de centre0et de rayonrdansFn2, elle contientR=Pr k=0 n kmots. Ainsi siCest un code de longueurnet de distance minimaled= 2r+ 1alorsCa au plus2n=Rmots de code. Lemme 2.2.SiCest un code lineaire de type(n;k;d), on denit le code etendu~Ccomme le code forme des mots(x1;:::;xn+1)2Fn+12tels que(x1;:::;xn)2CetPn+1 i=1xi= 0. Le type de ~Cest(n+ 1;k;d+ 1)sidest impair et(n+ 1;k;d)sidest pair. Demonstration.Le seul parametre a determine est la distance minimale. Soitxun mot de poidsddeC. Sidest pair alorsy= (x;0)2~Cetw(y) =d. Sidest impair alorsy= (x;1)2~C etw(y) =d+ 1.2

2.2 Matrice generatrice

On peut se donner un sous-espace vectoriel (et donc un code) par une base. SoitCun code lineaire. Unematrice generatricedeCest une matrice dont les lignes forment une base deC. Une matrice generatriceGest donc de tailleknet de rangk. Simest un vecteur ligne deFk2, le produitmGest un mot du codeCet l'applicationm7!mGest un isomorphisme deFk2surC(que l'on peut voir comme une operation de codage). Si la matriceGest de la forme (I;P), on dit que le codage estsystematique. Leskpremiers bits d'un mot de code portent l'information (on y recopie le vecteur deFk2), lesnksuivants sont de la redondance.

Exemple 2.La matrice2

41 0 0 0 0

1 1 0 1 0

1 1 1 0 13

5 est une matrice generatrice pour le code On dit que deux codes lineaires de m^eme longueur sontequivalentssi l'un s'obtient a partir de l'autre par une permutation des coordonnees. On peut verier que deux codes equivalents ont m^eme type. De plus tout code est equivalent a un code donne par un codage systematique.

Exemple 3.SoitGla matrice generatrice

2

40 0 1 1

0 1 1 0

1 0 1 13

5 On additionne la ligne1aux lignes2et3(ceci correspond a un changement de base). On obtient 2

40 0 1 1

0 1 0 1

1 0 0 03

5 Il ne reste plus qu'a permuter les trois premieres colonnes.

2.3 Matrice de contr^ole

On peut ausi se donner un sous-espace vectoriel par un systeme d'equations independantes. SoitCun code lineaire. Unematrice de contr^oledeCest la matrice d'un systeme d'equations lineaires homogenes independantes dont l'espace des solutions estC. Autrement dit, une ma- trice de contr^oleHest de taille (nk)net de rangnk, etC=fx2Fn2;Htx= 0g. SiCest donne sous forme systematique par la matrice generatriceG= (Ik;P), alors on peut prendre comme matrice de contr^oleH= (tP;Ink) (le signeest super u en caracteristique 2). Supposons quec2Cest le mot du code envoye etr2Fn2le mot recu. La dierencee=rc est le vecteur d'erreur. Son poidsw(e) est le nombre de bits errones dans le mot recu. Soit Hune matrice de contr^ole de C. Lesyndromedu mot recurest le vecteurs2Fnk2deni par ts=Htr=Hte. Le syndrome est nul si et seulement sir2C. Le syndrome denit un isomorphisme du quotientFn2=CsurFnk2. Si le syndrome est non nul, on corrige le mot recuren appliquant le principe du maximum de vraisemblance : on soustrait arun mot de poids minimum dans sa classe moduloC, c.-a-d. un mot de poids minimum parmi ceux 3 ayant m^eme syndrome quer. Dans le cas ouw(e) est strictement inferieur ad=2, alorseest l'unique mot de poids minimum dans la classe dermoduloCet on recupere bien le mot de code emis. Remarque 3.La matrice de contr^ole peut ^etre vue comme la matrice generatrice du code dual C ?=fy2Fn2;8c2C;y:c= 0g ou:est le produit scalaire usuel. Proposition 2.1.SoitHune matrice de contr^ole du codeC. La distance minimumddeC est caracterisee par les proprietes suivantes : |d1colonnes deHsont toujours lineairement independantes. | Il y a un systeme dedcolonnes deHqui est lie. Demonstration.Supposons qued1 colonnes deHsont toujours lineairement independantes. Soitc= (c1;:::;cn) un mot de code. On aHtc= 0. Siw(c)< dalors on a relation entre moins dedcolonnes deH. Inversement un motcde poidsddonne une relation entred colonnes deH.Exemple 4.Donnons un exemple de decodage par syndrome. SoitCle code donne par la matrice de contr^ole H=2

41 1 0 1 0 0

1 0 1 0 1 0

0 1 1 0 0 13

5 On calcule tout d'abord des representants de poids minimal (appeleleader) pour chacune des classesF62=Cainsi que le syndrome associe.

LeaderSyndrome

000000000

100000110

010000101

001000011

000100100

000010010

000001001

100001111

Supposons queu= 100011est recu. Son syndrome estHtu= 101. Pour decoderuil faut donc lui soustraire010000.

3 Quelques codes lineaires

3.1 Code de Hamming

voir TD. 4

3.2 Codes cycliques

Un code lineaireCFn2est ditcycliquequand il est stable par l'automorphisme de decalage cyclique

T:Fn2!Fn2

(x1;:::;xn)7!(x2;:::;xn;x1)

On identieFn2a l'algebreF2[X]=(Xn1) par

(x1;:::;xn)7!x1Xn1++xn1X+xn: On designe ici par la m^eme lettre l'indetermineeXet son image dans le quotient. L'endo- morphismeT, modulo cette identication, est l'endomorphisme de multiplication parX. Par denition, un code cyclique est un sous-espace vectoriel stable par multiplication parX, et donc par n'importe quel polyn^ome enX. Donc, un code lineaireCde longueurnest cyclique si et seulement siCest un ideal deF2[X]=(Xn1). L'homorphisme de passage au quotient induit une bijection entre l'ensemble des ideaux de F

2[X]=(Xn1) et l'ensemble des ideaux deF2[X] qui contiennent (Xn1). PuisqueF2[X]

est principal, ce sont exactement les ideaux engendres par les diviseurs (que l'on prend uni- taires pour assurer l'unicite) deXn1 dansF2[X]. Le diviseur unitairegdeXn1 ainsi associe a un code cycliqueCs'appelle lepolyn^ome generateurdeC. Sig6=Xn1 (dans le cas contraireCest nul), le codeCest engendre (comme espace vectoriel surF2) par g;Xg;:::;X n1deg(g)g. La dimension deCest dans tous les cask=ndeg(g). Le procede de codage systematiqueFk2!Cd'un code cyclique de polyn^ome generateurgest donne par la division euclidienne par g : le vecteur (x1;:::;xk)2Fk2est code par le polyn^ome c=cIcR, oucI=x1Xn1+:::+xkXnk, etcR(de degre< nk) est le reste de la division euclidienne decIparg. (Le polyn^omecIporte l'information, etcRla redondance). On suppose a partir de maintenant quenest premier avec la caracteristique deF2, c.-a-d. impair. Cette hypothese entra^ne que le polyn^omeXn1 anracines distinctes dans son corps de decomposition surF2. NotonsKce corps de decomposition, c'est-a-dire le corps en- gendre par les racinesn-iemes de l'unite surF2. On fait le choix d'une racine primitiven-ieme de l'unite dansK, que nous noterons. Le polyn^ome minimalPdesurF2a pour degre l'ordrerde 2 dans le groupe multiplicatif (Z=nZ), et ses racines sont;2;4;:::;2r1. On aK=F2[] =F2[X]=P=Fr2. Le polyn^ome cyclotomiquenfactorise surF2en produit de facteurs irreductibles de degrer(par exemple15=X8X7+X5X4+X3X+ 1 se factorise en (X4+X+1)(X4+X3+1) surF2), etPest un de ces facteurs. Le polyn^ome generateurgva ^etre determine par ses racines dansK, qui forment un sous-ensemble de l'ensemblef1;;2;:::;n1gdes racinesn-iemes de l'unite (les zeros du code). Soit un sous-ensemble deZ=nZ. Le polyn^omeg=Q i2(Xi) est un diviseur deXn1 a coe- cients dansF2si et seulement si est stable par multiplication par 2 (se souvenir queF2est l'ensemble des elements deKlaisses xes par l'elevation au carre). En conclusion, on a une bijection entre les codes cycliques de longueurnet les sous-ensembles deZ=nZstables par multiplication par 2. La conguration des racines du polyn^ome generateur nous renseigne sur la distance minimale du code cyclique. Proposition 3.1([Dem, Prop.9.4]).Sicontientsentiers consecutifsa+1;a+2;:::;a+ smodulon, alors le code cyclique de polyn^ome generateurgest nul ou a une distance minimum superieure ou egale as+ 1. La demonstration est une application des proprietes du determinant de Vandermonde. 5

3.3 Codes BCH

Les codes BCH (Bose-Chaudhuri-Hocquenghem) sont des codes cycliques particuliers. La famille des codes BCH contient les codes de Reed-Solomon qui servent pour la lecture des CD (voir [Dem, p.238]). Nous ne considererons ici que des codes BCH binaires primitifs. Leur longueurnest de la formen= 2r1. Alorsrest l'ordre de 2 dans le groupe multiplicatif (Z=nZ), et le corpsKengendre par les racinesn-iemes de l'unite surF2estFr2. Tous les calculs de decodage vont se faire sur ce corpsK. Choisissons une racine primitiven-ieme de l'unitedansK. Concretement, on se donnepar son polyn^ome minimalPsurF2. Tout element du groupe multiplicatifKs'ecrit de maniere unique sous la formeiavec 0i < n, et il s'ecrit aussi de maniere unique comme combinaison lineaire a coecients dansF2de

1;;:::;r1. On peut voir la table de correspondance entre ces deux representations pour

K=F16, avecveriant4++ 1 = 0 dans [Dem, p.213].

On appellecode BCHde longueurn= 2r1 et de distance prescrite(entier tel que

0< n) le code cyclique de polyn^ome generateurg, ou est le plus petit sous-ensemble de

Z=nZcontenant 1;2;:::;1 et stable par multiplication par 2. Autrement dit, un polyn^ome c=x1Xn1++xn2F2[X] appartient a ce code si et seulement si c() =c(2) =:::=c(1) = 0: On peut trouver des exemples de codes BCH explicites pourn= 15 dans [Dem, p.240].

References

[Dem] M. Demazure, Cours d'algebre, Cassini 1997. [Pre] O. Pretzel, Error-correcting codes and nite elds, Clarendon Press, 1992. 6quotesdbs_dbs30.pdfusesText_36

[PDF] prix code d delta voile

[PDF] delta voiles occasion

[PDF] code d occasion

[PDF] definition voile code 0

[PDF] idéal chevaleresque définition

[PDF] les règles de la chevalerie au moyen age

[PDF] loi 49-15 maroc

[PDF] loi 32-10 maroc

[PDF] spaco diesel

[PDF] code correction production d'écrit cycle 3

[PDF] grille de correction

[PDF] orange roya fiche technique

[PDF] orange rise 31 mode d'emploi

[PDF] orange roya alcatel

[PDF] orange tecno n9 fiche technique