Introduction aux codes correcteurs d’erreurs

le cas du code de r´ep´etition pure (1,3), mais c’est impraticable d`es que k est grand Or, pour satisfaire le point 1, il est clair que k doit ˆetre grand b) A priori, rien ne garantit que le mot de code qui r´ealise le minimum de d(r,m) soit unique C’est le cas du code de r´ep´etition pure (1,3), mais les codes ayant

TIPE : Code correcteur derreurs

La capacité de détection d'erreurs d'un code est naturellement plus éle-vée : on peut détecter toute erreur evéri ant w(e)

CODES CORRECTEURS D’ERREURS

(527) Codes correcteurs d’erreurs Il est clair que ce jeu est un exemple de code correcteur d’erreurs : le spectateur envoie un message m 1 m7 (formé du nombre compris entre 0 et 15, dont l’écriture en base deux est

Codes correcteurs d’erreurs

code Soit C(p) = 1 + plog 2 p+ (1 p)log 2 (1 p): Un th eor eme de Shannon montre que pour une probabilit e d’erreur p

Codes Correcteurs dErreurs Cours 1 + Introduction + Codes

Exemple de code d´etecteur et correcteur d’erreur : le code de r´ep´etition Technique de codage : Pour un bit d’information, 3 bits sont envoy´es (cad cod´es) tels que: 0 → 000 1 → 111 Technique de d´ecodage : Le d´ecodage se fait par vote majoritaire Par exemple, si le mot re¸cu est 001, alors on d´eduit que le bit ´emis

Theorie des codes´ correcteurs d’erreurs I

est appelée probabilité d'erreur, elle dépend du canal de transmission et non du code 3) Si on code oui par 111 et non par 000 C= f000;111g Après transmission de 111, si on reçoit 111 on admet que c'est bon Si on reçoit 011, 110 ou 101 on constate qu'il y a erreur ce ne sont pas des mots de C 000 est peut probable de le recevoir

Codes correcteurs derreurs - u-bourgognefr

110101 Il ne s’agit pas d’un mot du code et on peut afﬁrmer qu’au moins une erreur est apparue En ne changeant qu’un seul bit, on peut former le mot du code 010101 mais on peut egalement obtenir d’autres mots du code en changeant plus´ d’un bit On suppose donc que le mot du code correct est 010101 et on corrige donc 110101 en

TD : Codes de détection et de correction d’erreurs

3 Quel est le code du mot [1101011]? 4 Quelle condition vériﬁe le code s’il n’y a pas eu d’erreur? 5 Quelle condition vériﬁe le code si le bit k a été altéré? Comment fait-on pour le corriger? 6 Quel est le message correspondant au code [11111011100]? 4 Parité bidimensionnelle (block sum check)

[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

Introduction aux codes correcteurs

d"erreurs

Pierre Abbrugiati

23 janvier 2006

Table des mati`eres

1 Introduction 1

2 Les trois principaux param`etres d"un code 3

2.1 Dimension et longueur d"un code . . . . . . . . . . . . . . . . . . 3

2.2 L"algorithme de d´ecodage na¨ıf . . . . . . . . . . . . . . . . . . . . 4

2.3 Distance minimale d"un code . . . . . . . . . . . . . . . . . . . . 6

3 G´en´eralit´es sur les codes lin´eaires 9

3.1 D´efinitions d"un code lin´eaire . . . . . . . . . . . . . . . . . . . . 9

3.2 Distance minimale d"un code lin´eaire . . . . . . . . . . . . . . . . 10

3.3 Matrice de contˆole d"un code lin´eaire . . . . . . . . . . . . . . . . 11

3.4 D´ecodage d"un code lin´eaire . . . . . . . . . . . . . . . . . . . . . 13

4 Codes parfaits 17

4.1 Plusieurs d´efinitions ´equivalentes . . . . . . . . . . . . . . . . . . 17

4.2 Caract´erisation des codes parfaits lin´eaires . . . . . . . . . . . . . 18

5 G´en´eralit´es sur les codes cycliques 21

5.1 (R)appels sur les polynˆomes . . . . . . . . . . . . . . . . . . . . . 21

5.2 D´efinitions d"un code cyclique . . . . . . . . . . . . . . . . . . . . 22

5.3 Codes cycliques vs codes syst´ematiques . . . . . . . . . . . . . . 25

6 Codes BCH 27

6.1 D´etermination des codes cycliques de longueur impaire . . . . . . 27

6.2 Les codes BCH primitifs stricts . . . . . . . . . . . . . . . . . . . 29

6.3 Un algorithme de d´ecodage des codes BCH . . . . . . . . . . . . 30

III

Chapitre 1

Introduction

Par codes, on peut entendre plusieurs concepts bien distincts : cryptogra- phie (RSA,...); codes de compression (Huffman,...); codes correcteurs d"erreurs. Dans ce cours, on s"int´eresse aux codes correcteurs d"erreur; plus pr´ecis´ement `a la famille des codes en bloc. Lorsqu"on envoie un message `a travers un canal de transmission des donn´ees (par exemple : en t´el´echargeant ce cours sur internet), des erreurs de trans- mission peuvent se produire. Le but est d"arriver `a d´etecter, voire corriger des erreurs.

Notre mod`ele est le suivant :

- On consid`ere que le message est une suite de bits... - ... regroup´es en blocs dekbits (k= 1, ou 4, ou 8, ou 256, etc.) - ... et chaque bit a une probabilit´ep?12 donn´ee d"ˆetre invers´e. On se propose de "coder" chaque bloc du message initial en un bloc plus gros (avec des redondances d"information). Exemple 1.1Code par adjonction d"un bit de parit´e(8,9) On d´ecoupe notre message initial en blocs de 8 bits. On transforme ensuite chaque bloc en un bloc de 9 bits en ajoutant un bit `a la fin de chaque bloc de telle sorte que la somme des bits des nouveaux blocs soit toujours paire. Siuneerreur se produit, on peut la d´etecter, mais pas la localiser : on ne peut pas corriger notre bloc, il faut recommencer la transmission. Si d"avantage d"erreurs se produisent, on n"est mˆeme pas sˆur de d´etecter le probl`eme. 1

2CHAPITRE 1. INTRODUCTION

Et donc...qu"attend-on d"un bon code?

1. L"information ne doit pas ˆetre trop dilu´ee.

2. On doit pouvoird´etecteretcorrigerun nombre raisonnable d"erreurs.

3. L"algorithme de codage doit ˆetre suffisamment rapide.

4. L"algorithme de d´ecodage (corrections incluses) doit ˆetre suffisamment

rapide.

Chapitre 2

Les trois principaux

param`etres d"un code

2.1 Dimension et longueur d"un code

Terminologie et notations pr´eliminaires :

Un bloc dekbits sera indiff´eremment appel´ebloc,motouvecteur.

L"ensemble des mots dekbits sera not´e{0,1}k.

On parlera indiff´eremment debitsou delettres.

Un motmdekbits sera not´em1m2...mk, ou ´eventuellement( (m 1... m k)

Remarque pr´eliminaire :

Il y a 2

kmots de k bits. Le principe du codage est le suivant : apr`es avoir d´ecoup´e notre message en blocs dekbits, on va appliquer un mˆeme algorithme sur chaque bloc : a)ou bien en rajoutant des bits de contrˆole `a la fin de chaque bloc b)ou bien en modifiant complˆetement les blocs, mais en ´evitant que deux blocs diff´erents soient transform´es en un mˆeme bloc.

D"o`u la d´efinition suivante :

D´efinition 2.1(codes(k,n))

Un code est une application injectiveφ:{0,1}k→ {0,1}n Le paramˆetrekest appel´e ladimensiondu codeφet le paramˆetrenest appel´e lalongueurdu code : on dit queφest un code de param`etres(k,n). Si de plus pour tout motmde{0,1}k,mest un pr´efixe deφ(m)(c"est `a dire si l"application deφconsiste seulement `a rajouter des bits de contrˆole), on dira queφest un code syst´ematique. 3

4CHAPITRE 2. LES TROIS PRINCIPAUX PARAM`ETRES D"UN CODE

Sauf mention contraire, tous les codes´etudi´es par la suite seront syst´ematiques.

D´efinition 2.2(image d"un code)

L"ensembleC={φ(m), m? {0,1}k}est appel´el"imagedu codeφ. Les ´el´ements deCsont appel´es lesmots de codedeφ(en opposition aux ´el´ements "originels" de{0,1}kqui sont appel´es mots de source). Deux codes ayant la mˆeme image sont dits´equivalents.

Exemple 2.3

a)Le code parit´e pr´esent´e dans l"introduction est un code de param`etres(8,9). On peut aussi former des codes de parit´e de param`etres(k,k+ 1)pour tout entier strictement positifk. b)Exemple de code de param`etres(1,3): l"application?0?→000

1?→111(logique-

ment appel´e code de r´ep´etition pure(1,3))

2.2 L"algorithme de d´ecodage na¨ıf

Attardons-nous sur le code de r´ep´etition pure (1,3). Que peuvent devenir les mots de code apr`es erreur? Pas d ?erreur:000??000 111 ??111

001 110

100 011

011 100

110 001

Trois erreurs:000??111 111

??000

2.2. L"ALGORITHME DE D

´ECODAGE NA¨IF5

Si une, ou mˆeme deux erreurs se produisent, le mot re¸cu n"est pas un mot de code, l"erreur est donc d´etect´ee. Comment corriger? Si le mot re¸cu n"est pas un mot de code, la probabilit´e qu"il se soit produit une erreur est plus importante que la probabilit´e que deux er- reurs aient eu lieu. Il est donc plus raisonnable de corriger par le mot de code le plus "proche". On peut alors corriger une erreur, mais pas deux : 001 correction??000 110 correction??111 000 une erreur une erreur 100
??000 011 ??111 011 echec??111 100 echec??000 000 deux erreur une erreur 110
correction??111 001 correction??000 000

3erreurs??111 111

3erreurs??000

(erreurs non detectees) En r´esum´e, le code de r´ep´etition pure (1,3) est tr`es satisfaisant vis `a vis des points2et3, et satisfaisant vis `a vis du point4, mais inacceptable vis `a vis du point1. G´en´eralisons maintenant l"algorithme de d´ecodage qu"on a mis en oeuvre. On est amen´e `a d´efinir proprement cette notion de "proximit´e" et d´"´eloignement".

D´efinition 2.4(Poids et distance de Hamming)

Soientmetm?deux mots de{0,1}k.

On appelledistance de Hammingentremetm?, et on noted(m,m?)le nombre de lettres distinctes demetm?. On appellepoidsdem, et on notew(n)le nombre de lettres non nulles dem (donc le nombre de bits dem´egux `a1). Anecdotiquement, on a les deux relations suivantes :d(m,m?) =w(m+m?)et doncw(m) =d(m,00...0), o`u+d´esigne l"addition bit `a bit (avec1 + 1 = 0...)

6CHAPITRE 2. LES TROIS PRINCIPAUX PARAM`ETRES D"UN CODE

Algorithme g´en´eral de d´ecodage (na¨ıf) : Etant donn´e le mot re¸cur, on cherche le mot de codemqui r´ealise le minimum ded(r,m), et on d´ecoderparm

Cet algorithme soul`evedeux probl`emes:

a)Sa complexit´e est enO(n.2k). C"est acceptable sikest petit comme dans le cas du code de r´ep´etition pure (1,3), mais c"est impraticable d`es quekest grand. Or, pour satisfaire le point1, il est clair quekdoit ˆetre grand. b)A priori, rien ne garantit que le mot de code qui r´ealise le minimum ded(r,m) soitunique. C"est le cas du code de r´ep´etition pure (1,3), mais les codes ayant cette propri´et´e (codes parfaits) sont tr`es rares. Dans les prochains cours, on ´elaborera donc des strat´egies afin d"obtenir des codes pour lesquels on a des algorithmes de d´ecodage plus rapides.

2.3 Distance minimale d"un code

D´efinition 2.5

Soitφun code d"imageC.

On appelle capacit´e de d´etection deφle plus grand entieredtel qu"on soit tou- jours capable de d´etecterederreurs ou moins. On appelle capacit´e de correction deφle plus grand entierectel qu"on soit tou- jours capable de corrigerecerreurs ou moins. On appelle distance minimale deφet on notedφ(oudC) la plus petite distance non nulle entre deux mots de code.

On aec=dφ-1etec=?dφ-12

Notation :

La distance minimale d"un code quantifie donc sa qualit´e vis `a vis du point1. C"est un param`etre important. En abr´eg´e, "un code de dimensionk, de longueur net de distance minimaled" se dira "un code de param`etres (k,n,d)" ou mˆeme "un code (k,n,d)".

Exemple 2.6(code de r´ep´etition pure(1,3))

Prenons l"exemple o`uφest le code de r´ep´etition pure(1,3). Son image estC={000,111}donc sa distance minimaledφestd(000,111) = 3

On retrouve biened=dφ-1 = 2etec=?dφ-12

?= 1comme attendu.

2.3. DISTANCE MINIMALE D"UN CODE7

Exemple 2.7(code par bit de parit´e(8,9))

Prenons maintenant l"exemple o`uφest le code par bit de parit´e(8,9). Son imageCa28= 256´el´ements. Il est donc exclu de comparer tous les mots de code distincts : il nous faudrait faire9?C2256= 293760comparaisons! N´eanmoins, on peut ´etablir que sa distance minimaledφest2.

D´emonstration:

·000000000 et 000000011 appartiennent `aC(ce sont les deux premiers mots de ·Prenons deux mots de code distincts. Ils s"´ecriventa1...a8peta?1...a?8p?avec p=a1+...+a8etp?=a?1+...+a?8. Alors de deux choses l"une : - ou biend(a1...a8,a?1...a?8)≥2 et alorsa fortiorid(a1...a8p,a?1...a?8p?)≥2 - ou biend(a1...a8,a?1...a?8) = 1, c"est `a dire qu"il y a exactementunelettre de diff´erence entre les motsa1...a8eta?1...a?8, et donc quep=a1+...+a8?= a ?1+...+a?8=p?; il s"ensuit alors qued(a1...a8p,a?1...a?8p?) = 2 Cette analyse montre que dans tous les cas on ad(a1...a8p,a?1...a?8p?)≥2, et donc que la distance minimaledφv´erifiedφ≥2.

·En conclusion,dφ= 2.

On retouve alors comme pr´evued=dφ-1 = 1 etec=?dφ-12 ?= 0

8CHAPITRE 2. LES TROIS PRINCIPAUX PARAM`ETRES D"UN CODE

Chapitre 3

G´en´eralit´es sur les codes

lin´eaires

3.1 D´efinitions d"un code lin´eaire

D´efinition 3.1(code lin´eaire)

Un codeφde param`etres(k,n)est ditlin´eaires"il existe une matriceG? M n,k(F2)(c"est `a dire avecnlignes,kcolonnes, `a coefficients dans{0,1}), de rangk, telle que?m? {0,1}k, φ(m) =G×m. La multiplication matricielle est `a comprendre dansF2(c"est `a dire modulo

2) et le motmest ici consid´er´e comme un vecteur colonne. La condition sur le

rang traduit l"injectivit´e deφ. La matriceGest appel´eematrice g´en´eratricedeφ. Enfin, dire que le codeφest syst´ematique, c"est dire que la matriceGest le la forme?Ik G?? , o`uIkest la matrice identit´e d"ordrek.

Exemple 3.2

a)Consid´eronsφ, code lin´eaire de matrice g´en´eratrice( ((1 0 0 1 1 0 1 1) C"est un code de dimension2, de longueur4, donn´e par le tableau : xφ(x)000000

010101

101011

111110

b)Tous les codes rencontr´es jusqu"`a pr´esent, exception faite du code du td 1, exercice 3, sont lin´eaires. 9

10CHAPITRE 3. G´EN´ERALIT´ES SUR LES CODES LIN´EAIRES

?Pour le code de bit de parit´e(8,9), la matrice g´en´eratrice est?I8

1...1?

?Pour le code de r´ep´etition pure(1,3), la matrice g´en´eratrice est( (1 1 1) ?Pour le code du td 1, exercice 4, la matrice g´en´eratrice est( ((((((1 0 0 0 1 0 0 0 1 1 1 0 0 1 1

1 0 1)

Le caract`ere syst´ematique de ces codes se lit sur la matrice g´en´eratrice. c)Uncode de Hamming syst´ematiquede param`etres(4,7)est le code b

4=a1+a3+a4. Comme on le verra par la suite, il y a d"autres codes de Ham-

ming syst´ematiques de param`etres(4,7): un tel code consite en fait `a rajouter `a a

1a2a3a4trois bits de parit´e correspondant `a trois choix distincts de3´el´ements

parmia1,a2,a3,a4. La matrice g´en´eratrice de celui-ci est :( ((((((((1 0 0 0

0 1 0 0

0 0 1 0

0 0 0 1

1 1 1 0

1 1 0 1

1 0 1 1)

On peut d´ej`a remarquer que les codes lin´eaires se comportent de fa¸con satis- faisante (mais sans plus) vis `a vis du point3: l"algorithme de codage est en effet une multiplication matricielle, dont le coˆut est enO(n×k), et mˆeme en O((n-k)×k) dans le cas d"un code syst´ematique.

3.2 Distance minimale d"un code lin´eaire

Les codes lin´eaires sont ´egalement int´eressants car on dispose d"informations sur leur distance minimale. Tout d"abord, par d´efinition, dire qu"un codeφdequotesdbs_dbs29.pdfusesText_35

[PDF] Introduction aux codes correcteurs d’erreurs