Réseaux Informatiques : Td reseau codes correcteurs et codes detecteurs réseaux inf
Télécharger PDFObtenir le pack complet des cours, TDs, examens sur Réseaux Informatiques!
Vous souhaitez maîtriser Réseaux Informatiques ? Ne cherchez plus, nous avons le pack bien choisi pour vous.
Accédez à une collection complète des supports de cours, des travaux dirigés (TD) corrigés, examens...
Télécharger packTD RéseauLes codescorr ecteurset lescodes détecteursClaude Duvallet Matrise
Informatique
Ann ́ee 2003-2004
Ann ́ee 2003-2004
– p.1/22
Présentation(1) Pourquoi? Descanaux de
transmissionimparf ait
entraînantdes erreurslors des
échangesde données.
Probabilité
d’erreursur uneligne téléphonique
: P=10 �4 (celapeut même
atteindre10 �7 ).) Utilisationde méthodesde détectiondes erreurs
et éventuellementde correctiondes erreurs.
Méthodesmises enplace auniveau de
la couche2 OSI
("liaisonde données").
Principegénéral :Chaque suitede bits(trame) à transmettreest augmentéepar uneautre suitede bitdite de
redondanceou de
contrôle.Pour chaquesuite dek bits
transmis,on ajouter bits.On ditalors quel’on utiliseun codeC (
n; k) avecn =k +r .
Ann ́ee 2003-2004
– p.2/22
Présentation(2) Principegénéral (suite): À la réception,on effectue
l’opérationinverse et lesbits ajoutés
permettentd’ef fectuerdes contrôles
à l’arrivée. Il existedeux catégoriesde code: lescodes détecteurs
d’erreurs,les codes
correcteurs
d’erreurs.Le codede Hamming: uncode détecteur
et correcteur
d’erreurs.Le CRC(Cycle Redundanc
y Check): uncode détecteur
d’erreurs.
Ann ́ee 2003-2004
– p.3/22Le codede Hamming(1) Structured’un modede codede Hammingles mbits dumessage à transmettre
et lesn bitsde contrôlede parité.
longueurtotale :2 n� 1
longueurdu messages: m= (2n �1) �n )on parlede codex �y oùx =n +m ety =m .Ex emplede codede Hamming: unmot decode 7� 4
a uncoef ficientd’ef ficacitéde 4/7
= 57%, unmot decode 15� 11
a uncoef ficientd’ef ficacitéde 11/15
= 73%, unmot decode 31� 26
a uncoef ficientd’ef ficacitéde 26/31
= 83%, Lesbits de
contrôlede paritéC isont en
position2 ipour i=0,1,2,...Les bitsdu messageD joccupe le restedu message.D3 D2D1 C2D0 C1C0 76 54 32 1
Ann ́ee 2003-2004
– p.4/22Le codede Hamming(2) Retrouver l’erreurdans unmot deHamming Siles bitsde contrôlede réceptionC 02 C0 1C 00 valent0, il n’y
a pas
d’erreursinon la valeurdes bitsde contrôleindique la positionde l’erreurentre 1 et 7. SiC 00 vaut
1, lesvaleurs possiblesde C0 2C 01 C0 0sont 001,011, 101,111, c’est-à-dire
1, 3, 5,7. Si C0 1vaut 1, lesvaleurs possiblesde C0 2C 01 C0 0sont 010,011, 110,111, c’est-à-dire
2, 3, 6,7. Si C0 2vaut 1, lesvaleurs possiblesde C0 2C 01 C0 0sont 100,101, 110,111, c’est-à-dire
4, 5, 6,7. Exercice : y a-t-ilune erreurdans le motsui vant? 10 10 11 0
Ann ́ee 2003-2004
– p.5/22Le codede Hamming(3) Exercice (Correction)1 01 01 10 C0 2vaut 1 + 0 + 1 + 0 = 0(bits d’indice7, 6, 5 et 4).C 01 vaut
1 + 0 + 1 + 1 = 1(bits d’indice7, 6, 3 et 2).C 00 vaut
1 + 1 + 1 + 0 = 1(bits d’indice7, 5, 3 et 1).) C0 2C 01 C0 0vaut 011,c’est à dire
3 enbase 10.
Il y a doncune erreurà l’indice
3 dumot. Ann ́ee 2003-2004
– p.6/22Le codede Hamming(4) Émissionpour un
contrôlede paritépair .C 2est calculépar rapportaux bits
d’indice
7, 6,
5 et savaleur 4.C 1est calculépar rapportaux bits
d’indice
7, 6,
3 et 2.C 0est calculépar rapportaux bits
d’indice
7, 5,
3 et 1.On souhaiteenvoyer le message1010 , compléterle motde Hamming
correspondant: 10 1_ 0_ _
Ann ́ee 2003-2004
– p.7/22Le codede Hamming(5) 10 1_ 0_ _C2 vaut
0 pourpouv oirrendre pair
1 + 0 + 1(les bits
d’indices
7, 6, 5)1 01 00 __ C1vaut 1 pourpouv oirrendre pair
1 + 0 + 0(les bits
d’indices
7, 6, 3)1 01 00 1_ C0vaut 0 pourpouv oirrendre pair
1 + 1 + 0(les bits
d’indice
7, 5, 3)1 01 00 10 Ann ́ee 2003-2004
– p.8/22Le codede Hamming(6) Soitun motde Hammingde longueur15 10 11 01 11 10 11 01 115 1413 1211 109 87 65 43 21 Quelssont lesbits de
contrôlede parité? Quelest le messagereçu ?Est-ce que
le messagereçu correspondau message
transmis? Quel
a été
le message
transmis? Ann ́ee 2003-2004
– p.9/22Le codede Hamming(7) Lesbits de
contrôlede paritésont en
position2 iD10 D9D8 D7D6 D5D4 C3D3 D2D1 C2D0 C1C0 10 11 01 11 10 11 01 115 1413 1211 109 87 65 43 21 Lesbits de
contrôle: 1111Le messagereçu :
10110111010Les bitsde contrôlede réceptionvont être: C0 3C 02 C0 1C 00 SiC 00 vaut
1, lesvaleurs possiblessont (0001,0011, 0101,0111, 1001,1011, 1101,1111) soit(1, 3, 5, 7, 9, 11,13, 15).Si C0 1vaut 1, lesvaleurs possiblessont (0010,0011, 0110,0111, 1001,1010, 1011,1111) soit(2, 3, 6, 7, 10,11, 14,15). SiC 02 vaut
1, lesvaleurs possiblessont (0100,0101, 0110,0111, 1100,1101, 1110,1111) soit(4, 5, 6, 7, 12,13, 14,15). SiC 03 vaut
1, lesvaleurs possiblessont (1000,1001, 1010,1011, 1100,1101, 1110,1111) soit(8, 9, 10,11, 12,13, 14,15). Ann ́ee 2003-2004
– p.10/22Le codede Hamming(8) Dans
le message
considéréon a :C 00 =
1 + 0 + 1 + 1 + 1 + 0 + 1 + 1= 0C 01 =
1 + 0 + 0 + 1 + 1 + 0 + 0 + 1= 0C 02 =
1 + 1 + 0 + 1 + 1 + 1 + 0 + 1= 0C 03 =
1 + 1 + 1 + 0 + 1 + 1 + 0 + 1= 0) C0 3C 02 C0 1C 00 vaut0000 . Il n’y
a doncpas d’erreurdans le messagereçu. Ann ́ee 2003-2004
– p.11/22Le CRC(1) Représentationsous forme
polynomialedes suitesde bits
à transmettre: M= m1 m2 ...m n) représentéepar le polynômeI (x )= mn +m n� 1x +::: +m 1x n� 1Ex emple: Lasuite 11000101est représentéepar le polynômex 6+ x5 + 0x 4
+ 0x 3+ x2 + 0x + 1= x6 +x 5+ x2 + 1
Utilisationde polynômes
générateurs
possédantdes propriétés
mathématiques
particulières: CRC-12= x12 +x 11+ x3 +x 2+ x
+ 1CRC-16 =x 16+ x15 +x 2
+ 1
CRC-CCITT= x16 +x 12+ x5 + 1CRC-32 =x 32+ x26 +x 23+ x22 +x 16+ x12 +x 11+ x10 +x 8+ x7 +x 5+ x4 +x + 1
Ann ́ee 2003-2004
– p.12/22Le CRC(2) En
émission: onajoute aumessage à émettreun code
contrôletel le polynôme
correspondantau messageplus le codede contrôlesoit divisiblepar le
polynôme
générateur. En
réception: le messagereçu qui
contientles données
et le CRCdoit être
divisiblepar le polynôme
générateur
. Onvérifie doncpar une
division
euclidienneen base
2 que
le restede la divisionest nulle.
Ann ́ee 2003-2004
– p.13/22Le CRC(3) Émissiond’un mot: Onchoisit un
polynôme
générateurpuis on
le transformeen unmot binaire.Ex emple
: avec
le polynôme
générateurx 4+ x2 +x , onobtient 10110. Onajoute mzéros aumot binaire
à transmettreoù mest le degrédu polynôme
générateur. Exemple : on
souhaite
transmettre
le mot
11100111en utilisantle polynôme
générateurx 4+ x2 +x , onobtient alors
111001110000. On
va ajouteritérati vement
à cemot, le mot
correspondantau polynôme
générateurjusqu’à ceque le motobtenu soit
inférieurau polynôme
générateur
. Cemot obtenu
correspondau CRC
à ajouterau motavant de
l’émettre.On effectuedonc une
division
euclidiennedans laquelleon netient pascompte du
quotient.
Ann ́ee 2003-2004
– p.14/22Le CRC(4) Exemple d’émissiond’un mot: 11 10 01 11 00 00 10 11 00 10 10 11 01 10 00 01 11 10 10 11 00 10 00 01 01 10 00 11 00 01 01 10 01 11 0Le CRCest donc1110 et le mot
à transmettre
111001111110 .
Ann ́ee 2003-2004
– p.15/22Le CRC(5) Réceptiond’un mot: 11 10 01 11 11 10 10 11 00 10 10 11 01 10 00 01 11 11 10 11 00 10 01 11 01 10 00 10 11 01 01 10 00 00 0Le restede la divisionest nulle,
il n’y
a doncpas d’erreur. Ann ́ee 2003-2004
– p.16/22Le CRC(6) Exercices :On utilisera
le polynôme
générateurx 4+ x2 +x .1. On
souhaite
transmettre
le messagesui vant: 1111011101
, quelsera leCRC à ajouter? 2.Même questionavec le mot
1100010101. 3.Je viensde recevoir les
messagessui vants: 1111000101010, 11000101010110
, sont-ils
corrects? Ann ́ee 2003-2004
– p.17/22Le CRC(7) Correction
: quelCRC à ajouteravant d’émettrele message
1111011101? 11 11 01 11 01 00 00 10 11 00 10 00 11 01 10 00 11 11 11 01 10 01 00 10 10 11 00 01 00 10 10 11 00 01 00 00 10 11 00 01 10 0Le CRCest donc1100 et le mot
à transmettre
11110111011100 .
Ann ́ee 2003-2004
– p.18/22Le CRC(8) Correction
: quelCRC à ajouteravant d’émettrele message
1111011101? x13 x12 x11 x10 x8 x7 x6 x4 x4 +x 2+ xx 13x 11x 10x 12x 8x 7x 6x 4x 9+ x8 +x 6x 12x 10x 9+ x5 +x 3+ x2 x10 x9 x8 x7 x6 x4 +x x10 x8 x7 x9 x6 x4 x9 x7 x6 x7 x4 x7 x5 x4 x5 x5 x3 x2 x3 x2 Ann ́ee 2003-2004
– p.19/22Le CRC(9) Correction
: quelCRC à ajouteravant d’émettrele message
1100010101? 11 00 01 01 01 00 00 10 11 00 11 10 11 01 10 01 01 10 10 11 00 00 00 10 10 01 01 10 00 01 00 0Le CRCest donc1000 et le mot
à transmettre
11000101011000 .
Ann ́ee 2003-2004
– p.20/22Le CRC(10) Correction
: le messagereçu 1111000101010est-il correct? 11 11 00 01 01 01 01 01 10 01 00 00 10 11 00 01 10 01 10 11 00 01 11 10 10 11 00 10 00 11 01 10 00 11 10 11 01 10 01 01 10 10 11 00 00 00 Lereste estnul )
il n’y
a pas
d’erreurdans le mot
transmis.
Ann ́ee 2003-2004
– p.21/22Le CRC(11) Correction
: le messagereçu 11000101010110est-il correct? 11 00 01 01 01 01 10 10 11 00 11 10 11 01 10 01 01 10 10 11 00 00 00 10 10 11 01 10 00 01 11 0Le resteest 1110) il y a uneerreur dans
le mot
transmis.
Ann ́ee 2003-2004
– p.22/22