[PDF] Codes correcteurs derreur Codes correcteurs d'erreur. Judith

View - Download Codes correcteurs derreur

Previous PDF

Next PDF

Codes correcteurs d"erreur

Judith Louis-Alexandre, Camille Huynh, Dorian Lesbre

Juin 2017

Table des matières

1 Théorie des codes 2

1.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2 Définitions générales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3 Codes correcteurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4 Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

2 Structure de corps finis 6

2.1 Construction des corps finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.1 Corps premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.2 Corps de Galois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2 Propriétés des corps finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3 Codes de Hamming 9

3.1 Théorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2 Encodage : l"exemple du code de Hamming (7,4) . . . . . . . . . . . . . . . . . . . . .

11

4 Codes de Reed-Solomon 13

4.1 Encodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

4.2 Détection d"erreurs et décodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

4.3 Correction d"erreurs par syndrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

4.3.1 Déterminer les polynômeset

. . . . . . . . . . . . . . . . . . . . . . . . .16

4.3.2 Déterminer les positions d"erreurs . . . . . . . . . . . . . . . . . . . . . . . . .

19

4.3.3 Déterminer les valeurs d"erreurs . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4.3.4 Synthèse de la correction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

4.4 Notes d"implémentation : calcul dansF2metF2m[X]. . . . . . . . . . . . . . . . . . .21

5 Comparaisons de codes correcteurs 21

Table des fonctions

1 code : encodage de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2 decode : décodeur de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

3 euclide : résolution de l"équation-clé . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

4 calcul_racines : calcule des racines de. . . . . . . . . . . . . . . . . . . . . . . . .19

5 Forney : calcul des coefficientseik. . . . . . . . . . . . . . . . . . . . . . . . . . . . .20

6 corrige : correcteur du code de Reed-Solomon . . . . . . . . . . . . . . . . . . . . . .

21
1

1 Théorie des codes

1.1 Principe

Un code correcteur sert à assurer une transmission ou un stockage d"information par un canal

ou support qui pourrait la détériorer. Ils sont utilisés notamment lors de l"échange de données sur

internet, sur réseau mobile, ou lors du stockage de données sur un disque DVD. L"idée est de rajouter

judicieusement un certain nombre de redondances afin de pouvoir retrouver le message initial si

celui-ci a été légèrement altéré. Le nombre de redondance dépendant de la fiabilité du support et du

besoin de correction : une sonde spatiale en utilise beaucoup pour transmettre des données, tandis

que le protocole http se contente d"une simple détection d"erreur, préférant redemander le message

au serveur plutôt que de le corriger. Disons que nous voulons transmettre le message suivante : "Le cheval blanc d"Henri 4" Le code le plus simple est celui de répétition, on c"est-à-dire que l"on transmet

Le cheval blanc d"Henri 4

Le cheval blanc d"Henri 4"

Cependant, si une erreur se produit, on est incapable de dire à priori si la première répétition où la

deuxième est la bonne : "Le cheval blanc d"Henri 4

Le cheval blanc d"Henri

5 Ce code ne permet donc pas de corriger d"erreurs. Des codes plus complexes permettent d"obtenir de bien meilleurs résultats (exemple de code de Reed-Solomon) "}|Ö[%&Le cheval blanc d"Henri 4"

Ce code rajoute6symboles de contrôles, et peut corriger jusqu"à5erreurs. Ainsi si le décodeur reçoit

"}|Ö[%&Le chevalrouge d"Henri 4" ou "}êÖ[%&Le4evasblanc d"HenriX "

Il pourra retrouver au message initial. Ce code est donc plus efficace que le précédent : il insère

nettement moins de symboles (6 et non 25) et peut corriger 5 erreurs.

L"objectif de l"étude mathématique des codes correcteurs est de trouver des solutions optimales

(comment corriger un maximum d"erreur) à partir d"une longueur de message à transmettre ou d"un

nombre de symboles ajoutés fixé.

1.2 Définitions générales

Caractéristiques d"un code :afin de formaliser la notion de code correcteur, nous utiliserons les définitions suivantes : -L"alphabetest un ensemble fini de symboles avec lequel sont écrits les mots du code. On prendra pour alphabetFq, un corps fini àqéléments muni des opérations somme et produit.

-Le messageAest une liste deksymboles à transmettre, on l"assimile à un élément deFkq-L"encodeurest un algorithme qui transforme le messageAen un mot du codeCde longueur

ncomportant des redondances. On l"assimile à une fonction injectiveenc:Fkq!Fnq -Le codeest l"ensemble des mots possibles :C=enc(B);B2Fkq -Le mot reçuD2Fnqest une version potentiellement corrompue du message émisD=C+E, avecEles erreurs introduites. 2 -La distance de Hammingentre deux motsC1;C2notéd(C1;C2)est le nombre de symboles distincts entreC1;C2. On appelle poids la distance au mot nul :w(C) = d(C;0) On introduit alors les grandeurs suivantes pour caractériser un code -qle cardinal de l"alphabet (nombre de symboles distincts) -kla dimension d"un code (la longueur du message initial) -ple nombre de symboles de contrôle -n=k+pla longueur d"un mot du code la distance minimale d"un co dedmin= min (c1;c2)2C2 c

16=c2d(c1;c2)

On condensera toutes ces notations en disant queCest un code(n;k;dmin)q. Le décodeur est un algorithme qui retrouveCà partir deD=C+EsiEest de poids assez faible. On l"assimile à un une fonctiondec :Fnq!Fkqvérifiant8A2Fkq;dec(enc(A)) =Aet

8A2Fkq;8E2Fnq; w(E)6dmin12

)decenc(A) +E=A Proposition 1 : (Propriétés de la distance de Hamming) La distance de Hamming est symétrique et vérifie pour tout(c1; c2; c3)2(An)3: d(c1;c2) = d(c1c2;0) =w(c1c2)(1) d(c1;c2) + d(c2;c3)>d(c1;c3)>jd(c1;c2)d(c2;c3)j(2) Démonstration :notonsc1= (1;:::;n),c2= (1;:::;n)etc3= (

1;:::;

n). On a alors d(c1;c2) =nX i=1(1i;i) oùest le symbole de Kronecker. On sait que pour touti2[[1; n]],i;i=i;i=ii;0d"où la symétrie et le premier point.

Soiti2[[1; n]],

Cas 1 :i;

i= 0, alorsi6= idonci6=iou i6=i. donci;i= 0ou i;i= 0. Ce qui donne (1i;i) + (1 i;i)>1etj(1i;i)(1 i;i)j61donc j(1i;i)(1 i;i)j6(1i; i)6(1i;i) + (1 i;i)

Cas 2 :i;

i= 1. On a évidemment(1i; i)6(1i;i) + (1 i;i).

Sii=ialors

i=idoncj(1i;i)(1 i;i)j=j(0)(0)j= 0

Sii6=ialors

i6=idoncj(1i;i)(1 i;i)j=j(1)(1)j= 0 En sommant suri, on obtientjd(c1;c2)d(c2;c3)j6d(c1;c3)6d(c1;c2) + d(c2;c3)1.3 Codes correcteurs Codet-correcteurs :soitt>0, notonsC 2 P(An)un code sur l"alphabetA. Pour chaque mot c2 Cdu code, on définit l"ensemble

E(c;t) =fa2 An=d(c;a)6tg

. C"est une boule de centrecet de rayont(au sens de la distance de Hamming). -Cestt-correcteur si les ensemblesE(c; t) c2Csont disjoints. -Cest parfait si les ensemblesE(c; t) c2Cforment une partition deAn 3 SiCcodet-correcteur, on peut attribuer à chaque élément deAndistant de moins detdu code un unique mot du code le plus proche. SiCest parfait, alors tout élément deAnadmet un unique mot

du code le plus proche.Illustration des ensemblesE(c;t)pour le code1-correcteur parfait Hamming(3;1):enc:8

:F

2!F3207!000

17!111

Proposition 2 :

SoitCun code possédantqkéléments surFnq,tun entier positif etc2 C. On a

1.#E(c; t) = 1 +n(q1) +n

2 (q1)2+:::+n t (q1)t=tX `=0 n (q1)` 2. si Cestt-correcteur alors#E(c;t)6qnk 3. si Cest parfait alors#E=qnk: Démonstration :pour construire un élémentddeE(c;t), de manière unique : 1. on c hoisit`2[[0; t]]la distance de Hamming entredetc: 2. on c hoisitl"emplacemen tde c es`coefficients distincts :n possibilités. 3. on c hoisitla v aleurde c haqueco efficient: (q1)possibilités pour chaque (n"importe quel élément deAdifférent du coefficient correspondant dec), donc(q1)`en tout.

En sommant, on obtient#E(c; t) =tX

`=0 n (q1)`.

Si le code estt-correcteur, alors[

c2CE(c;t) Anest une union disjointe (avec égalité siCest parfait), donc en passant aux cardinaux X c2Ct X `=0 n (q1)`6qn(avec égalité siCest parfait), or #C=qk, on obtient alors :tX `=0 n (q1)`6qnkavec égalité siCest parfait.Proposition 3 :

SoitCun code de distance minimaledmin>1. Alors

Cestdmin12

-correcteur mais n"est pasdmin12 + 1-correcteur. 4

Démonstration :Posonst=dmin12

Soit(c1; c2)2 C2, montrons queE(c1; t)\ E(c2; t) =;. Soith2 E(c1; t). On sait qued(h;c1)6t. D"après l"inégalitéd(h;c2)>d(c2;c1)d(h;c1)on ad(h;c2)>dmindmin12 >dmin12 donch =2 E(c2; t). Les ensembles sont disjoints. Il existe(c1;c2)2 C2tel qued(c1;c2) =dmin. Donc en modifiantt+ 1symboles dec1différents de ceux dec2en symboles dec2, on obtient un mothde distancet+ 1dec1et moins det+ 1de c

2. Donch2 E(c1;t+ 1)\ E(c2;t+ 1). Le code n"est past+ 1correcteur.1.4 Codes linéaires

Code linéaire :un codeCest dit linéaire de longueurnet de dimensionksur l"alphabetAsiC est un sous-espace vectoriel deAnde dimensionk. En pratiqueA=Fqest un corps fini (et doncAn est unFqespace vectoriel de dimension finien). Matrice génératrice :soitG2 Mn;k(Fq). On dit queGest une matrice génératrice du code linéaireClorsque la famille des colonnes deGest un base deC. AinsiGest de rangketx7!Gxest une fonction d"encodage possible. Matrice de contrôle :Fnqest muni du produit scalaire usuel (la somme des produits des coordon- nées). CommeFnqest de dimension finie, il existe un unique sous-espace vectorielC?de dimension nk. NotonsH2 Mn;nk(Fq)une matrice génératrice deC?, appelée matrice de contrôle.

Proposition 4 :

SoitCun code linéaire. Il existe une matrice de contrôleHet une matrice génératriceG. De plus,

pour toute matrice de contrôleHet pour toute matrice génératriceGon a : 1. tHG= 0

2.8x2Fnq; x2 C ,tHx= 0

Démonstration :Cétant un sous-espace vectoriel non-nul deFnq, espace de dimension finie,Cest de dimension finie. Donc il existe une base deC, et donc une matriceG. De même il existe un supplémentaire orthogonal de dimension finie, et donc une base de ce supplémentaire. tHG= 0car les coefficients du produit correspondant au produit scalaire d"une colonne deH, donc d"un vecteur deC?est d"une colonne deG(vecteur deC). Soitx2Fnq. on note(c1; :::; cn)2(Fnq)nkles colonnes deH, c"est une base deC?. On a les

équivalences suivantes :

x2 C ,x2(C?)? , 8c2(C?);hx; ci= 0 , 8i2[[1; nk]];hci; xi= 0 ,Hx= 0Proposition 5 : (Distance minimale d"un code linéaire) SoitCun code linéaire. La distance minimaledminentre deux mots deCvérifie : d min= min c2Cnf0gw(c) 5

Démonstration :on a par définition :

d min= min (c1;c2)2C2 c

16=c2d(c1;c2)or pour tout(a;b)2 A2;d(a;b) = d(ab;0)

= min (c1;c2)2C2 c

16=c2d(c1c2;0) = min

(c1;c2)2C2 c

16=c2w(c1c2)

le code étant linéaire, tout différence de mots du code est un mot du code et tout mot du code peut

s"écrire sous la forme d"un différence :fc1c2;(c1;c2)2 C2=c16=c2g=C n f0g.

On a alorsdmin= minc2Cnf0gw(c)Définition :On définit la borne de Hamming d"un codet-correcteur par :

V t=tX i=0 n i (q1)i avecqle cardinal de l"alphabet, etnla longueur d"un mot du code.

Proposition 6 : (Majoration de Hamming)

Pour tout codeCt-correcteur, on a la majoration suivante : #C6qnV t avecqle nombre de lettres dans l"alphabet du code etVtla borne de Hamming du code. Démonstration :C"est une reformulation de la proposition 2Proposition 7 : Un code est parfait si et seulement si sa borne de Hamming est atteinte. Démonstration :Le sens direct a été montré dans la proposition 2. SoitCun codet-correcteur. Montrons que si sa borne de Hamming est atteinte,Cest un code parfait. SoitB=fa2 An=9c2 C;a2 E(c;t)gl"ensemble des éléments deAnappartenant à une boule de rayontcentrée en un mot du code. Alors on a exactement#B= #C Vt, les boules étant disjointes puisque le code estt-correcteur. On a alors#B=qn= #AnpuisB=An, ce qui montre que le code est parfait.2 Structure de corps finis

2.1 Construction des corps finis

2.1.1 Corps premiers

Construction :soitpun entier naturel non nul. La relation de congruence modulopest une relation d"équivalence qui permet de construire l"ensembleZ=pZ=fCl(x);x2Zg. Cet ensemble est

composé depéléments : les classes des entiers de0àp1notées0;:::;p. On définit les opérations

+etdansZ=pZpar : -8(a;b)2(Z=pZ)2;a+b=a+b -8(a;b)2(Z=pZ)2;ab=ab Ces opérations sont bien définies car, pour(a;b;c;d)2Z4siac[p]etbd[p]alorsa+bc+d[p] etabcd[p] 6

Proposition 8 : (Structure de(Z=pZ;+;))

L"ensemble(Z=pZ;+;)est un anneau commutatif d"élément neutre0pour l"addition et1pour le produit. De plus(Z=pZ;+;)est un corps si et seulement sipest premier.

Démonstration :soit(a;b;c;d)2(Z=pZ)4

Groupe commutatif(Z=pZ;+): elle s"hérite de la structure de groupe commutatif de(Z;+): Associativité :(a+b) +c=a+b+c=a+b+c=a+b+c=a+ (b+c)

Commutativité :a+b=a+b=b+a

Neutre :0 +a=0 +a=aet donca+0 =a

Inversibilité :a+a=a+a=0

Anneau(Z=pZ;+;):

Associativité :(ab)c=abc=abc=abc=a(bc)

Distributivité :(a+b)(c+d) =a+bc+d=(a+b)(c+d) =ac+ad+bc+bd =ac+ad+bc+bd

Neutre :a1 =a1 =aet1a=a

Commutativité :ab=ab=ba

Supposonsppremier eta60[p]. Il existex2[[1; p1]]tel quea=x.x < petpest premier, donc

x^p= 1. D"après le théorème de Bezout, il existe(u;v)2Z2,ux+vp= 1.ux+vp=1, orp= 0etx=a, on a doncav=1etva=av=1

Supposonspnon premier.

Cas 1 :p= 1. Alors01 [p]donc0 =1,00 =1donc02 U(Z=pZ). AlorsZ=pZn"est pas un corps.

Cas 2 :p>2.pest non premier, doncp>3. Il existe(u;v)2[[2; p1]]2tel queuv=p, doncuv=0. SiZ=pZest un corps alorsu

1etv

1existent. On av

1u 1uv=v

1v=1orv

1u 1uv=v 1u

10 =0donc1 =0. On en déduit00 =1, c"est-à-dire01 [p].pj1

etp2Ndonnep= 12.1.2 Corps de Galois Construction :soitpun nombre premier etn2N. On noteraFple corpsZ=pZ. SoitPdeFp[X] de degrén. On définit la relationpar8(A;B)2Fp[X];AB,Pj(AB). C"est une relation

d"équivalence. On pose alorsFp[X]=Pl"ensemble des classe d"équivalences. Il contientpnéléments :

les classes des polynômes deFp;n1[X](qui est unFpespace vectoriel de dimensionn). On noteA la classe deA. Similairement à la congruence sur les entiers, on définit les opérations : -8(A;B)2(Z=pZ)2;A+B=A+B -8(A;B)2(Z=pZ)2;AB=AB Elle sont de même bien définies : pour(A;B;C;D)2Fp[X]4tel queABetCD, on sait que (A+C)(B+D)et(AC)(BD)

Proposition 9 : (Structure de(Fp[X]=P;+;))

L"ensemble(Fp[X]=P;+;)ainsi défini est un anneau commutatif d"élément neutre0pour l"addition

etX

0pour le produit. De plus(Fp[X]=P;+;)est un corps si et seulement siPest irréductible

dansFp[X]. Démonstration :la structure d"anneau commutatif s"hérite de celle deFp[X] SupposonsPirréductible dansFp[X]. SoitA2Fp[X]=Pn0 Il existeC2Fp;n1[X]tel queA=C.degC D"après le théorème de Bezout, il existe(U;C)2Fp[X]2,UC+V P= 1.UC+VP=1, orP= 0etC=A, on a doncAV=1etVA=AV=1

SupposonsPnon irréductible dansFp[X]. Il existe(C;D)2Fp[X]non constant tel queCD=P.

On a alorsCD=0. SiFp[X]=Pest un corps alorsC

1etD

1existent, etD

1C 1CD=1 7 orCD=0doncD 1C

1CD=0. On a1 =0, donc02 U(Fp[X]=P), d"oùFp[X]=Pn"est pas

un corps.Proposition 10 : Soitppremier etn>2entier. Le polynômeXpnX2Fp[X]est égal au produit de tous les polynômes irréductibles unitaires deFp[X]dont le degré divisen.

Démonstration :

SoitP2Fp[X]irréductible de degréddivisantn. Le corpsFpd=Fp[X]=Pexiste. On sait que le groupe multiplicatif d"un corps fini est cyclique d"après la proposition 13. Il existe donc un élémentA2(Fp[X]=P)n f0ggénérateur de(Fp[X]=P)n f0g;.X6= 0donc il existei21; pdtel queX=A i.X pd=A pdi=A i=X. OrpjndoncX pn=X,PdiviseXpnX. SoitPun diviseur irréductible deFp[X]de degréd. Posonsf:Fp[X]=P!Fp[X]=P x7!xp.

Soit(a;b)2(Fp[X]=P)2f(a+b) = (ab)p=a

pb p=f(a)f(b)et f(a+b) = (a+b)p=pX i=0 p ia ib piorppremier doncp p i d"oùp i = 0dansFp, f(a+b) =a p+b p=f(a) +f(b) fest donc un endomorphisme de corps. Supposonsf(a) =f(b),f(ab) =0, siab6=0alorsf((ab)1)f(ab) =f(1) =1quotesdbs_dbs29.pdfusesText_35

[PDF] code bch exemple

[PDF] code bch pdf

[PDF] code en bloc linéaire exercice corrigé

[PDF] code cyclique

[PDF] matrice génératrice code hamming

[PDF] codex seraphinianus français

[PDF] rohonc codex pdf

[PDF] codex seraphinianus français pdf

[PDF] codex seraphinianus alphabet

[PDF] codex seraphinianus pdf

[PDF] codex seraphinianus fnac

[PDF] léonard de vinci et les secrets du codex atlanticus

[PDF] leonard de vinci codex atlanticus

[PDF] codex arundel

[PDF] leonard de vinci biographie pdf