TD Réseau Les codes correcteurs et les codes détecteurs

Le code de Hamming est donc un code binaire parfait On peut de la même manière construire un code de Hamming pour toutes les valeurs de k La matrice de contrôle de parité est constituée de tous les 2k – 1 vecteurs non nuls de longueur k On a donc toujours un code 1-correcteur parfait La matrice H est de taille (2k –1) x k

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

Techniques de détection & de correction des erreurs de

R Kanawati, Cours réseaux, IUT de Villetaneuse, département GTR, 1er année, 2002-2003 Code de Hamming n La distance de Hamming entre deux séquences binaires de même taille est égale au nombre de bits de rang identique par lesquels elles différent n Exemple : d(1100110, 1010110) = 2 n Soit un code composé de N mot valides

TD Réseau Les codes correcteurs et les codes détecteurs

Le code de Hamming (2) Retrouver l’erreur dans un mot de Hamming Si les bits de contrôle de réception C0 2C 0 1C 0 0 valent 0, il n’y a pas d’erreur sinon la valeur des bits de contrôle indique la position de l’erreur entre 1 et 7 Si C0 0 vaut 1, les valeurs possibles de C 0 2C 0 1C 0 0 sont 001, 011, 101, 111, c’est-à-dire 1, 3

Cours : Codes correcteurs

Cours : Codes correcteurs Emily Clement Enseignant : Delphine Boucher Master 1 de Mathématiques Semestre 2 2015-2016

Theorie des codes´ correcteurs d’erreurs I

1 6 Capacité de détection et de correction d'un code 7 1 8 Bornes sur les codes 9 1 9 Codes Parfaits 10 1 10 Exercices 11 Chapitre 2 Codes linéaires 15 2 1 Dé nition 15 2 2 Matrice génératrice 15 2 4 Code dual et matrice de contrôle 16 2 9 Distance minimale 18 2 12 Décodage 21 2 16 Rayon de couverture 24 2 17 Construction de

Le contrôle d’erreur - imag

• Distance de Hamming du code complet (ou distance minimale) h = { Min Disth(x1, x2) ; x1 et x2 ∈ M et x1≠x2} M est l’ensemble des 2 m mots de codes possibles si on admet que les r bits de contrôle sont calculés en fonction des m bits de données Contrôle d’erreur : un modèle d’étude

48 Application des corps ﬁnis aux codes correcteurs d’erreur

4 8 Application des corps ﬁnis aux codes correcteurs d’erreur Cette section se veut une introduction succincte et très partielle à la vaste théorie des codes correcteurs, l’une des applications pratiques les plus célèbres de la théorie des corps

Mot information Mot code

RSE : exercices MRI 20-21 7 La chaîne 1011001 a été reçue par une entité de la couche liaison dont le protocole implique l'utilisation du code de Hamming correcteur d'une erreur Si vous savez qu'au maximum une seule erreur s'est produite, corrigez la chaîne et donneu les bits d'information transmis originalement 8

ClaudeDuvallet

MatriseInformatique

Ann

´ee2003-2004

Ann´ee2003-2004-p.1/22

Présentation(1)

Pourquoi?

4 (celapeut mêmeatteindre10 7 correctiondeserreurs. l'onutiliseuncodeC(n;k)avecn=k+r.

Ann´ee2003-2004-p.2/22

Présentation(2)

Principegénéral(suite):

Ilexistedeuxcatégoriesdecode:

LecodedeHamming:

uncodedétecteuretcorrecteurd'erreurs.

LeCRC(CycleRedundancyCheck):

uncodedétecteurd'erreurs.

Ann´ee2003-2004-p.3/22

LecodedeHamming(1)

Structured'unmodedecodedeHamming

n 1 longueurdumessages:m=(2 n 1)n )onparledecodexyoùx=n+mety=m.

ExempledecodedeHamming:

LesbitsdecontrôledeparitéC

i sontenposition2 i pouri=0,1,2,...LesbitsdumessageD j occupelerestedumessage. D3 D2 D1 C2 D0 C1 C0

7654321

Ann´ee2003-2004-p.4/22

LecodedeHamming(2)

Retrouverl'erreurdansunmotdeHamming

SilesbitsdecontrôlederéceptionC

0 2 C 0 1 C 0 0 valent0,iln'yapas l'erreurentre1et7. SiC 0 0 vaut1,lesvaleurspossiblesdeC 0 2 C 0 1 C 0 0 sont001,011,101,

111,c'est-à-dire1,3,5,7.

SiC 0 1 vaut1,lesvaleurspossiblesdeC 0 2 C 0 1 C 0 0 sont010,011,110,

111,c'est-à-dire2,3,6,7.

SiC 0 2 vaut1,lesvaleurspossiblesdeC 0 2 C 0 1 C 0 0 sont100,101,110,

111,c'est-à-dire4,5,6,7.

1 0 1 0 1 1 0

Ann´ee2003-2004-p.5/22

LecodedeHamming(3)

Exercice(Correction)

1 0 1 0 1 1 0 C 0 2 vaut1+0+1+0=0(bitsd'indice7,6,5et4). C 0 1 vaut1+0+1+1=1(bitsd'indice7,6,3et2). C 0 0 vaut1+1+1+0=1(bitsd'indice7,5,3et1). )C 0 2 C 0 1 C 0 0 l'indice3dumot.

Ann´ee2003-2004-p.6/22

LecodedeHamming(4)

C 2 C 1 C 0 motdeHammingcorrespondant: 1 0 1 _ 0 _ _

Ann´ee2003-2004-p.7/22

LecodedeHamming(5)

1 0 1 _ 0 _ _

C2vaut0pourpouvoirrendrepair1+0+1(les

bitsd'indices7,6,5) 1 0 1 0 0 _ _

C1vaut1pourpouvoirrendrepair1+0+0(les

bitsd'indices7,6,3) 1 0 1 0 0 1 _

C0vaut0pourpouvoirrendrepair1+1+0(les

bitsd'indice7,5,3) 1 0 1 0 0 1 0

Ann´ee2003-2004-p.8/22

LecodedeHamming(6)

SoitunmotdeHammingdelongueur15

1 0 1 1 0 1 1 1 1 0 1 1 0 1 1

151413121110987654321

Ann´ee2003-2004-p.9/22

LecodedeHamming(7)

i D10 D9 D8 D7 D6 D5 D4 C3 D3 D2 D1 C2 D0 C1 C0 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1

151413121110987654321

0 3 C 0 2 C 0 1 C 0 0 SiC 0 0

1111)soit(1,3,5,7,9,11,13,15).

SiC 0 1

1111)soit(2,3,6,7,10,11,14,15).

SiC 0 2

1111)soit(4,5,6,7,12,13,14,15).

SiC 0 3

1111)soit(8,9,10,11,12,13,14,15).

Ann´ee2003-2004-p.10/22

LecodedeHamming(8)

Danslemessageconsidéréona:

C 0 0 =1+0+1+1+1+0+1+1=0 C 0 1 =1+0+0+1+1+0+0+1=0 C 0 2 =1+1+0+1+1+1+0+1=0 C 0 3 =1+1+1+0+1+1+0+1=0 )C 0 3 C 0 2 C 0 1 C 0 0

Ann´ee2003-2004-p.11/22

LeCRC(1)

debitsàtransmettre: M=m 1 m 2 ...m n )représentéeparlepolynômeI(x)=m n +m n1 x+:::+m 1 x n1

Exemple:

x 6 +x 5 +0x 4 +0x 3 +x 2 +0x+1=x 6 +x 5 +x 2 +1

CRC-12=x

12 +x 11 +x 3 +x 2 +x+1

CRC-16=x

16 +x 15 +x 2 +1

CRC-CCITT=x

16 +x 12 +x 5 +1

CRC-32=x

32
+x 26
+x 23
+x 22
+x 16 x 12 +x 11 +x 10 +x 8 +x 7 +x 5 +x 4quotesdbs_dbs6.pdfusesText_11

[PDF] TD Réseau Les codes correcteurs et les codes détecteurs

ClaudeDuvallet

MatriseInformatique

´ee2003-2004

Ann´ee2003-2004-p.1/22

Présentation(1)

Pourquoi?

Ann´ee2003-2004-p.2/22

Présentation(2)

Principegénéral(suite):

Ilexistedeuxcatégoriesdecode:

LecodedeHamming:

LeCRC(CycleRedundancyCheck):

Ann´ee2003-2004-p.3/22

LecodedeHamming(1)

Structured'unmodedecodedeHamming

ExempledecodedeHamming:

LesbitsdecontrôledeparitéC

7654321

Ann´ee2003-2004-p.4/22

LecodedeHamming(2)

Retrouverl'erreurdansunmotdeHamming

SilesbitsdecontrôlederéceptionC

111,c'est-à-dire1,3,5,7.

111,c'est-à-dire2,3,6,7.

111,c'est-à-dire4,5,6,7.

Ann´ee2003-2004-p.5/22

LecodedeHamming(3)

Exercice(Correction)

Ann´ee2003-2004-p.6/22

LecodedeHamming(4)

Ann´ee2003-2004-p.7/22

LecodedeHamming(5)

C2vaut0pourpouvoirrendrepair1+0+1(les

C1vaut1pourpouvoirrendrepair1+0+0(les

C0vaut0pourpouvoirrendrepair1+1+0(les

Ann´ee2003-2004-p.8/22

LecodedeHamming(6)

SoitunmotdeHammingdelongueur15

151413121110987654321

Ann´ee2003-2004-p.9/22

LecodedeHamming(7)

151413121110987654321

1111)soit(1,3,5,7,9,11,13,15).

1111)soit(2,3,6,7,10,11,14,15).

1111)soit(4,5,6,7,12,13,14,15).

1111)soit(8,9,10,11,12,13,14,15).

Ann´ee2003-2004-p.10/22

LecodedeHamming(8)

Danslemessageconsidéréona:

Ann´ee2003-2004-p.11/22

LeCRC(1)

Exemple:

CRC-12=x

CRC-16=x

CRC-CCITT=x

CRC-32=x