[PDF] TD Réseau Les codes correcteurs et les codes détecteurs Claude PDF ADuvallet.pdf

Le code de Hamming : un code détecteur et correcteur d'erreurs Le CRC (Cycle Redundancy Check) : un

Le code par parité impaire n'est pas linéaire, sa capacité de détection est de 1 bit , pour tout n Exercice 4: a: toute erreur sur un nombre impair de bit Pas de

[PDF] Cours Codes Correcteurs - LIRMM

J Badrikian, Technosup, Ellipses (cours et exercices) ▫ Codes correcteurs d est noté C(n,k,d) ○ Un code qui corrige jusqu'à t erreurs est appelé t-correcteur

[PDF] Mathématiques des codes correcteurs derreurs - Institut Fourier

Exemple de correction de deux erreurs par un code cyclique et toutes les erreurs de transmission serons corrigées par le code C Exercice Soit p = ps la probabilité des perturbations de symboles au cours de la transmission On détecte un facteur multiple éventuel par l'examen du PGCD entre le polynôme et son

[PDF] Feuille dexercices 3

Remarque : Tous les exercices ne seront pas traités en séance de TD, du forum (http ://cours-jussieu-nombres monforum com/cours-et-td-2009-vf7 html) les Correction des erreurs : supposons que le code est 1-correcteur et notons m le envoyé x en au plus une coordonnée alors l'erreur `a corrigée est ϵ = x − x avec

[PDF] Université Pierre & Marie Curie

Exercice 1 Dire dans chaque cas si le code est linéaire ainsi que le nombre d' erreurs qu'il peut détecter linéaire binaire parfait 1-correcteur de longueur n est que l'entier n soit de la forme n = 2r − 1, où r Montrer que si C est de longueur 17 et de dimension 7, il ne corrige pas plus d'une erreur Examen juin 2004

[PDF] Sécurité des réseaux : codage

19 mai 2008 · d) Que peut-on affirmer sur le nombre d'erreurs corrigées? On s'intéresse dans cet exercice au codage par répétition Il s'agit Conclusion sur la capacité de correction du code ? Exercice 6 Codage de Hamming (examen 2004-2005) Exercice 9 — Codes de Hamming : démonstrations du cours

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

Le code de Hamming : un code détecteur et correcteur d'erreurs Le CRC (Cycle Redundancy Check) : un

[PDF] Travaux Dirigés de réseau no1 - IGM

Cours d'architecture des réseaux —Maıtrise Exercice 1 (Transmission téléphonique) L'objectif de l'exercice est de calculer le débit théorique Exercice 8 On utilise pour une transmission avec detection d'erreur un CRC (Code de Exercice 16 On utilise un code correcteur de Hamming 7+4 (on transmet 7 bits utiles

[PDF] Correction de lexamen du cours de Théorie de l - DI ENS

(a) Montrer que le code de Huffman aura une longueur moyenne égale `a l' entropie de la source On consid`ere maintenant une source discr`ete stationnaire: X0,

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] [PDF] TD Réseau Les codes correcteurs et les codes détecteurs Claude

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: