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

et pourtant 8 erreurs (on a reçu un mot de code) " la détection d'anomalies ne permet pas de détecter le nombre d'anomalies ex : si 1 1 0 0 1 0 1 0 devient 0 0 1 1 0 1 0 0, on ne pas savoir qu'il y a eu 7 erreurs # code parité => code détecteur d'un nombre impair d'erreurs mais ne permet pas de corriger des erreurs

Codes correcteur d’erreur

Zéro erreur : y est un mot du code Quelques erreurs : corriger y en un mot du code Quelques erreurs : correction impossible Le décodeur peut se tromper Il peut choisir un mot de code à la place d’un autre Il choisit le mot qui a la probabilité la plus grande d’être correcte On suppose que

Codages détecteurs/correcteurs 1 Exercices

1 2 Détection/correction d'erreurs Exercice 3-3 Numéro INSEE Le numéro INSEE est un numéro composé de 13 chi res auquel on ajoute une clé de deux chi res pour contrôler d'éventuelles erreurs de saisie On obtient cette clé 1 en réduisant le numéro N modulo 97 : r = N (mod 97); 2 en retranchant r à 97 : la clé est k = 97 r

Cours : Codes correcteurs - ENS Rennes

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

TD Ing´enierie des R´eseaux Code d´etecteur et correcteur d

d 0x64 e 0x65 Donner la suite des octets qui seront transf´er´es V´eriﬁer que l’on corrige bien 1 erreur: exemple, le bit 7 (num´erotation de droite a gauche, en commencant par 0) du ’e’ est mal recu Exercice 4 Donner la matrice g´en´eratrice d’un code de Hammings cod´e sur 11 bits: 4 bits de contrˆole et 7 bits d’information

Theorie des codes´ correcteurs d’erreurs I

ou 10 on constate qu'il y a erreur, car ces mots ne sont pas des mots de C 00 est peut probable de le recevoir Dorénaavnt nous supposons que la probabilité de recevoir 0 et 1 en erreur est p(

Codes Correcteurs dErreurs Les codes convolutifs binaires

Figure: Diagramme d’´etat d’un codeur convolutif 2-m´emoires 1/2-taux Note : le taux ou rendement de ce code convolutif est de 1/2 (2 bits produits pour 1 bit d’information) Marc Chaumont Introduction Les codes convolutifs binaires : structure de base D´ecodeur de Viterbi Connection avec les codes blocs Introduction - D´eﬁnitions

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

permettent d’effectuer des contrôles à l’arrivée Il existe deux catégories de code : les codes détecteurs d’erreurs, les codes correcteurs d’erreurs Le code de Hamming : un code détecteur et correcteur d’erreurs Le CRC (Cycle Redundancy Check) : un code détecteur d’erreurs Ann´ee 2003-2004 – p 3/22

TD Codes correcteurs

mieux d= 3 Par exemple, le code dont les mots de code sont 00000, 01101, 10011, 11110] 2 Codes lin´eaires 1 Soit kquelconque On code un bloc de kbits en lui ajoutant un bit de contrˆole choisi de fac¸on que le nombre de 1 dans le mot de code soit toujours pair D´emontrer que ce code est lin ´eaire D ´eterminer sa distance minimale

ClaudeDuvallet

MatriseInformatique

Ann

´ee2003-2004

Ann´ee2003-2004-p.1/22

Présentation(1)

Pourquoi?

Descanauxdetransmissionimparfaitentraînantdeserreurslorsdes échangesdedonnées.Probabilitéd'erreursurunelignetéléphonique:P=10 4 (celapeut mêmeatteindre10 7 )Utilisationdeméthodesdedétectiondeserreursetéventuellementde correctiondeserreurs.

Méthodesmisesenplaceauniveaudelacouche2

OSI("liaisondedonnées").Principegénéral:

Chaquesuitedebits(trame)àtransmettreestaugmentéeparuneautre suitedebitditederedondanceoudecontrôle.Pourchaquesuitedekbitstransmis,onajouterbits.Onditalorsque l'onutiliseuncodeC(n;k)avecn=k+r.

Ann´ee2003-2004-p.2/22

Présentation(2)

Principegénéral(suite):

Àlaréception,oneffectuel'opérationinverseetlesbitsajoutés permettentd'effectuerdescontrôlesàl'arrivée.

Ilexistedeuxcatégoriesdecode:

lescodesdétecteursd'erreurs,lescodescorrecteursd'erreurs.

LecodedeHamming:

uncodedétecteuretcorrecteurd'erreurs.

LeCRC(CycleRedundancyCheck):

uncodedétecteurd'erreurs.

Ann´ee2003-2004-p.3/22

LecodedeHamming(1)

Structured'unmodedecodedeHamming

lesmbitsdumessageàtransmettreetlesnbitsdecontrôledeparité.longueurtotale:2 n 1 longueurdumessages:m=(2 n 1)n )onparledecodexyoùx=n+mety=m.

ExempledecodedeHamming:

unmotdecode74auncoefficientd'efficacitéde4/7=57%,unmotdecode1511auncoefficientd'efficacitéde11/15=73%,unmotdecode3126auncoefficientd'efficacitéde26/31=83%,

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 d'erreursinonlavaleurdesbitsdecontrôleindiquelapositionde 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.

Exercice:ya-t-iluneerreurdanslemotsuivant?

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 vaut011,c'estàdire3enbase10.Ilyadoncuneerreurà l'indice3dumot.

Ann´ee2003-2004-p.6/22

LecodedeHamming(4)

Émissionpouruncontrôledeparitépair.

C 2 estcalculéparrapportauxbitsd'indice7,6,5etsavaleur4. C 1 estcalculéparrapportauxbitsd'indice7,6,3et2. C 0 estcalculéparrapportauxbitsd'indice7,5,3et1.

Onsouhaiteenvoyerlemessage1010,compléterle

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

Quelssontlesbitsdecontrôledeparité?Quelestlemessagereçu?Est-cequelemessagereçucorrespondaumessage

transmis?Quelaétélemessagetransmis?

Ann´ee2003-2004-p.9/22

LecodedeHamming(7)

Lesbitsdecontrôledeparitésontenposition2

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

Lesbitsdecontrôle:1111Lemessagereçu:10110111010Lesbitsdecontrôlederéceptionvontêtre:C 0 3 C 0 2 C 0 1 C 0 0 SiC 0 0 vaut1,lesvaleurspossiblessont(0001,0011,0101,0111,1001,1011,1101,

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

SiC 0 1 vaut1,lesvaleurspossiblessont(0010,0011,0110,0111,1001,1010,1011,

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

SiC 0 2 vaut1,lesvaleurspossiblessont(0100,0101,0110,0111,1100,1101,1110,

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

SiC 0 3 vaut1,lesvaleurspossiblessont(1000,1001,1010,1011,1100,1101,1110,

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 Cquotesdbs_dbs12.pdfusesText_18

[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?

Méthodesmisesenplaceauniveaudelacouche2

OSI("liaisondedonnées").Principegénéral:

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.

Exercice:ya-t-iluneerreurdanslemotsuivant?

Ann´ee2003-2004-p.5/22

LecodedeHamming(3)

Exercice(Correction)

Ann´ee2003-2004-p.6/22

LecodedeHamming(4)

Émissionpouruncontrôledeparitépair.

Onsouhaiteenvoyerlemessage1010,compléterle

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)

Lesbitsdecontrôledeparitésontenposition2

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: