[PDF] Codes correcteurs Le code de Hamming de

View - Download Codes correcteurs

Previous PDF

Next PDF

Codes correcteurs

DelphineBoucher

Master?de mathématiques fondamentales·Université de Rennes? Notes prises par TéofilAdamski(version du?avril????) ?Généralités sur les codes correcteurs? ?.?Généralités. . . . . . . . . . . . . . . . . . . . . ? ?.?Codes linéaires. . . . . . . . . . . . . . . . . . ? ?.?Décodage par tableau standard et syndrome? ?.?Codes de Hamming. . . . . . . . . . . . . . . ? ?.?Code de Goley binaire étendu. . . . . . . . . ? ?Codes de Reeed-Solomon généralisés et codes de Reed-Muller?? ?.?Code GRS. . . . . . . . . . . . . . . . . . . . . ?? ?.?Codes de Reed-Muller. . . . . . . . . . . . . . ?? ?Codes cycliques?? ?.?Codes cycliques, générateurs. . . . . . . . . . ?? ?.?Matrice génératrice. . . . . . . . . . . . . . . ??

?.?Matrice de contrôle. . . . . . . . . . . . . . . ???.?Polynômes minimaux et factorisation de

Xn-1surFq.. . . . . . . . . . . . . . . . . . . . . ?? ?Codes BCH?? ?.?Une famille de codes?-correcteurs d"erreurs?? ?.?Définition et propriétés. . . . . . . . . . . . . ?? ?.?Algorithme de décodage des codes BCH. . . ?? ?Codes de Goppa?? ?.?Définition et matrice de contrôle. . . . . . . ?? ?.?Distance minimale et dimension. . . . . . . ?? ?.?Algorithme de décodage. . . . . . . . . . . . ?? ?Cryptosystème de McEliece?? ?.?Cryptosystème à clef publique. . . . . . . . . ?? ?.?Cryptosystème de McEliece. . . . . . . . . . ?? ?.?Exemple. . . . . . . . . . . . . . . . . . . . . . ??

Chapitre?

Généralités sur les codes correcteurs

?.?Généralités. . . . . . . . . . . . . . . . . . . . . . ? ?.?Codes linéaires. . . . . . . . . . . . . . . . . . . . ? ?.?Décodage par tableau standard et syndrome. . ? ?.?.?Tableau standard. . . . . . . . . . . . . . . . ?

?.?.?Tableau standard simplifié. . . . . . . . . . ??.?Codes de Hamming. . . . . . . . . . . . . . . . . ?

?.?.?Définition. . . . . . . . . . . . . . . . . . . . . ? ?.?.?Décodage/correction. . . . . . . . . . . . . . ? ?.?Code de Goley binaire étendu. . . . . . . . . . . ? ?.?.?Distance minimale et auto-dualité. . . . . . ? ?.?.?Algorithme de décodage. . . . . . . . . . . . ?

?.?GénéralitésL"objectif initial des codes correcteurs est de parer les interférences dans un canal de transmission.

On considère un expéditeur et un destinataire communiquant par un canal. L"expéditeur envoie

un motm?Aksur un alphabetA. Cependant, il se peut se le destinataire reçoive un message différentm?. On va donc associer au motm, de manière injective, un codec?Anavecn>k. Le destinataire lui recevra une codec?et le surplus desn-kinformations va permettre de retrouver le message initialm. Exemple.On considère un canal de transmission d"informations binaires qui fait au plus une

erreur sur un chiffre. Par exemple, l"expéditeur envoie le nombre1101, mais le destinataire reçoit le

nombre1001. Un bon code correcteur associé au nombre envoyé est donc ce nombre répété trois

fois. Avec ce code, on peut savoir si le nombre à l"arrivé est bon. Définition?.?.SoitAun ensemble de cardinalq?N?. UncodesurAde longueurn?Nest un sous-ensemble deAn. Lelog-cardinald"un codeCsurAest la quantiték:= logq|C|et sontaux d"informationest la quantiték/n. Dans toute la suite, on fixe un ensemble finiA, appelée unalphabet. Soitn?N?un entier non nul.Définition?.?.Lepoids de Hammingd"un élémentx:= (x1,...,xn)?Anest l"entier w

H(x):=?{i?J1,nK|xi?= 0}.

Ladistance de Hammingd"un élémentx?Anà un élémenty?Anest l"entier d

H(x,y):=wH(x-y).Proposition?.?.L"applicationdH:An×An-→Nest bien une distance surAn.Définition?.?.Ladistance minimaled"un codeC?Ande longueurnest l"entier

d := minx,y?C x?=yd

H(x,y).

Proposition?.?.SoitC?Anun code de longueurnet de distance minimaled?N. Soity?An.

Alors l"ensemble

{c?C|dH(y,c)6t}avect:=›d-12 est soit vide soit un singleton.

Preuve

On distingue deux cas. Si tout motc?Cest à distance supérieure strict àt, alors cet ensemble est vide. On suppose maintenant qu"il existe un motc?Ctel quedH(y,c)6t. Soitc??C

un autre tel mot. Alors l"inégalité triangulaire assuredH(c,c?)62t < dce qui forcec=c?.Proposition?.?.Soientc?Cety?Antels quedH(y,c)6d-1. Alorsy=couy /?C.

Généralités sur les codes correcteurs -Chapitre??

?.?. CODES LINÉAIRESL"objectif est de construire des codes de longueurn, de log-cardinalk?R+et de distance

minimaled?Ntel que les quantitésk/netd/nsoient grandes. De plus, on souhaite avoir un algorithme de correction/décodage qui est efficace,i. e.se fait en temps polynomial. Théorème?.?(borne de Singleton).SoitC?Anun code de longueurn, de cardinalM?Net de distance minimaled?N. Soitk:= logqM. Alors d6n-k+ 1.

Preuve

On considère l"applicationf:C-→A?k?-1de projection sur les?k? -1premières coordonnées. Si elle était injective, alors?C=?f(C)6q?k?-1, donck6?k? -1ce qui est impossible. On peut donc trouver deux mots distinctsc,c??Ctels quef(c) =f(c?). On obtient w

H(c-c?)6n-(?k? -1)6n-k+ 1

ce qui assure la conclusion. ?Exemples.•Code de répétition.On considère l"application F

2-→Fn2,

m?-→(m,...,m) et le codeC:=?(F2). Il est de longueurn, de cardinal2et de log-cardinal1. •Code de parité.On considère le codeCdéfini comme l"image deFn-12par l"application F n-12-→Fn2, Il est de longueurnet de cardinal2n-1. Trouvons sa distance minimale. Soientc,c??C. Alors un simple calcul donnedH(c,c?) =wH(c-c?)?2N, donc sa distance minimaled?Nvérified>2. ?.?Codes linéaires

À un code, on va associer une matrice génératrice et une matrice de contrôle. Cette dernière

va nous servir à calculer la distance minimale, à détecter et corriger les erreursviadifférents

algorithmes. Dans la suite, on considère une puissanceq?Nd"un nombre premier et on se place dans le corpsFq. Définition?.?.Soientk,n?Ndes entiers tels quek6n?= 0. Uncode linéairede longueurnet de dimensionkest un sous-espace vectoriel deFnqde dimensionk. Remarque.SoitC?Fnqun code linéaire de longueurn?N?et de dimensionk6n. Alors il existe une application linéaire injective?:Fkq-→Fnqtelle queC=?(Fkq). SoitM?Mn,k(Fq) la matrice de?dans les bases canoniques. Sa transposéeG:=tM?Mk,n(Fq)est lamatrice génératricedeC. Le codeCest ainsi caractérisé par l"égalité

C={nG|n?Fkq}.

Définition?.?.La matrice génératriceGdeCest sous formesystématiquelorsqu"elle est de la forme C=IkAavecA?Mk,n-k(Fq).Proposition?.??.La distance minimale d"un code linéaireCest d= min0?=c?CwH(c). Notation.On note[n,k,d]ql"ensemble des codes de longueurn?N?, de dimensionk6net de distance minimaled?NsurFq. ?Généralités sur les codes correcteurs -Chapitre?

?.?. CODES LINÉAIRESDéfinition?.??.Leduald"un codeCde[n,k,d]qde matrice génératriceGest l"orthogonal

C

?:={x?Fnq| ?c?C,?x,c?= 0}pour le produit scalaire canonique?,?surFnq. Unematrice de contrôledeCest une matrice

génératrice deC?. On dit que le codeCestauto-dualsiC?=C.Proposition?.??.SoitCun code[n,k,d]qde matrice de contrôleH. Alors

C :={x?Fnq|Htx= 0}. PreuveSoitGsa matrice génératrice. À partir des définitions, on obtient C ?={x?Fnq|Gtx= 0}, doncdimC?=n-kpuisquek= rgG. Comme la matriceHgénèreC?, on argH=n-k. Il suffit alors de montrer qu"une inclusion. Soitc?C. Alors pour touty?C?, on a?c,y?= 0ce qui impliqueHtc= 0et conclut. ?Remarque.On obtient alorsGtH=HtG= 0.

Exemples.•Codes de répétition et de parité.On reprend l"exemple de code de répétition,i. e.

l"image par l"application F

2-→Fn2,

m?-→(m,...,m).

Sa matrice génératrice estG:= (1···1)et sa matrice de contrôle estH:= (1n-1In-1). Pour

le code de parité, sa matrice génératrice estG?:= (In-11n-1)et sa matrice de contrôle estG.

Ces deux problèmes sont duaux l"un de l"autre.

•Code de Hamming de longueur?.On considère l"imageC?F72par l"applicationF

42-→F72,

Ses matrices génératrice et de contrôle valent G

1 0 0 0 0 1 1

0 1 0 0 1 0 1

0 0 1 0 1 1 0

0 0 0 1 1 1 1

etH:="

0 1 1 1 1 0 0

1 0 1 1 0 1 0

1 1 0 1 0 0 1Ž

Il est de longueur?et de dimension?. Pour connaître sa distance minimale, on peut faire la liste des mots ou utiliser la matriceHpuisqueC={x?F72|Htx= 0}. Un mot de poids?implique une colonne deHnulle ce qui est impossible. Un mot de poids?implique deux mêmes colonnes dansHce qui est aussi impossible. On noteHi?F32les colonnes deH. CommeH1+H2+H3= 0,

on obtient(1,1,1,0,...,0)?C, donc la distance minimale vautd:= 3.Théorème?.??.SoientCun code[n,k,d]qetHune matrice de contrôle deC. Soit

D={j?J1,nK|tout ensemble dej-1colonnes deHest linéairement indépendant}.

Alors la distance minimale deCvautD:= maxD.

Preuve

On suppose qu"il existec?C\{0}tel quewH(c)< D. AlorsHtc= 0etw:=wH(c)6D-1.

On peut écrirec= (0,...,0,λ1,...,λw,0,...,0)pour des élémentsλj?Fqnon tous nuls. En

considérant lesλj-ièmes colonnes, il existeD-1colonnes deHlinéairement dépendantes ce qui

est impossible. DoncwH(c)>Dpour toutc?C. CommeD+ 1/?D, il existeDcolonnesHi1, ...,HiDdeHlinéairement dépendantes. De plus, tout ensemble deD-1colonnes est libre. Par conséquent, il existeλ1,...,λD?F?qtels que

1Hi1+···+λDHiD= 0.

Le motc:= (0,...,0,λ1,...,λD,0,...,0)où chaque élémentλjest en positionijvérifiewH(c) =D.

Ceci termine la preuve.

Généralités sur les codes correcteurs -Chapitre?? ?.?. DÉCODAGE PAR TABLEAU STANDARD ET SYNDROME

?.?Décodage par tableau standard et syndromeOn considère un codeCdu type[n,k,d]q. Étant donné un moty?Fnq, on souhaite trouver un

motc?Cqui réalise l"infimumminx?CdH(y,x). Cela revient à trouver un mote?Fnqde poids minimum tel quey-e?C. ?.?.?Tableau standard On définit une relation d"équivalenceRsurFnqen décrétantxRysi et seulement six-y?C pour tous motsx,y?Fnq. La classe d"équivalence d"un motx?Fnqest notéx+Cet est appelée uncoset. Uncoset leaderest un mot de plus petit poids dans le coset. On peut remarquer qu"il existeqn-kcosets de tailleqk=|C|. On peut construire le tableau contenant tous les cosets leadercen ligne, les colonnes correspon- dant aux autres mots de la classe,i. e.les motsc+cioù les motsciaveci?J1,|C| -1Kforment

une base deC. La tout première case contient donc le mot0et les autres cases de la première ligne

contiennent les motsci. Ce tableau est letableau standard. Soity?Fnqun mot. On cherche la ligne

du tableau où ce motyapparaît. On lit un coser leadere?Fnqsur la première colonne et il est de

poids minimal et vérifiey-e?C. ?Exemple.On considère le code surF2de matrice génératrice G

0 1 0 1 1‹

Pour construire son tableau standard, on énumère tous les mots de poids?, on recommence avec les

mots de poids?, ... jusqu"à retomber sur un mot déjà obtenu. Son tableau standard est

Si on considère le emoty:= 01101qui est présent sur la deuxième ligne du tableau, alors il suffit

de prendree:= 10000etc:= 11101. ?.?.?Tableau standard simplifié SoitHune matrice de contrôle deC. Alors pour tous motsx,y?Fnq, on a xRy??Htx=Hty

où la quantitéHtxest appelée lesyndromedex. Letableau standard simplifiéest le tableau des

syndromes. Soity?Fnqun mot. Pour répondre au problème posé, on cherche dans le tableau un mote?Fnqtel queHte=S:=Hty. On en déduit que le poids deeest minimal et on ay-e?C. ?Exemple.Reprenons l"exemple précédent. Une matrice de contrôle est H

1 0 1 0 0

1 1 0 1 0

0 1 0 0 1Ž

Alors le tableau standard simplifié est

?Généralités sur les codes correcteurs -Chapitre? ?.?. CODES DE HAMMING

????? ???Si on considère le moty:= 01101, alors son syndrome vautS:= (1,1,0)et ce dernier se situe dans

la deuxième ligne, donc on prende:= 10000qui répond au problème. ?.?Codes de Hamming Le but est de construire une famille infinie de codes binaires qui corrigent une erreur et de trouver deux algorithmes de décodage. ?.?.?Définition Définition?.??.Soitr>2un entier. On posen:= 2r-1. On considère la matriceH?Mr,n(F2)

dont les colonnes sont les vecteurs non nuls deFr2rangés dans l"ordre suivant : à un entierj?J1,nK,

on associée ler-uplet(ε0j,...,εr-1 j)?Fr2tel que?=r-1X i=0ε ij2i et laj-ième colonne deHsera H j=...

ε0j...

r-1 Lecode de Hammingde longueurnest le codeHrde matrice de contrôleH. La dimension de ce code vaut2r-1-r. Calculons la distance minimale du codeC. Il n"y a pas de mot de poids?car les colonnes de la matriceHsont non nulles. De même, il n"y a pas de mots de poids?car les colonnes sont deux à deux distinctes. Cependant, on aJ1+H2+H3= 0, donc le mot(1,1,1,0,...,0)est un mot de poids?du codeHr. Sa distance minimale vaut donc?. ?.?.?Décodage/correction Soity=c+eun mot avecc?Hrete?Fn2tels quewH(e)61. On souhaite trouver un tel motcà partir d"un mot donnéy. Pour se faire, on utilisera le syndrome. Ce dernier vaut S :=Hty=Htc+Hte=Hte qui est nul sie= 0et qui vautHjsie= (δj,i)i?J1,nK.

Premier algorithme

On possède un produit algorithme qui est le suivant.quotesdbs_dbs29.pdfusesText_35

[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