Loading...
Reload document 
Open in new tab TD Réseau
Les codes correcteurs et les codes détecteurs
Claude Duvallet
Matrise Informatique
Ann´ee 2003-2004
Ann´ee 2003-2004 – p.1/22
Présentation (1)
Pourquoi ?
Des canaux de transmission imparfait entraînant des erreurs lors des
échanges de données.
Probabilité d’erreur sur une ligne téléphonique : P=10(cid:0)4 (cela peut
même atteindre 10(cid:0)7).
) Utilisation de méthodes de détection des erreurs et éventuellement de
correction des erreurs.
Méthodes mises en place au niveau de la couche 2
OSI (“liaison de données”).
Principe général :
Chaque suite de bits (trame) à transmettre est augmentée par une autre
suite de bit dite de redondance ou de contrôle.
Pour chaque suite de k bits transmis, on ajoute r bits. On dit alors que
l’on utilise un code C(n; k) avec n = k + r.
Ann´ee 2003-2004 – p.2/22
Présentation (2)
Principe général (suite) :
À la réception, on effectue l’opération inverse et les bits ajoutés
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
Le code de Hamming (1)
Structure d’un mode de code de Hamming
les m bits du message à transmettre et les n bits de contrôle de parité.
longueur totale : 2n (cid:0) 1
longueur du messages : m = (2n (cid:0) 1) (cid:0) n
) on parle de code x (cid:0) y où x = n + m et y = m.
Exemple de code de Hamming :
un mot de code 7 (cid:0) 4 a un coefficient d’efficacité de 4/7 = 57 %,
un mot de code 15 (cid:0) 11 a un coefficient d’efficacité de 11/15 = 73 %,
un mot de code 31 (cid:0) 26 a un coefficient d’efficacité de 26/31 = 83 %,
Les bits de contrôle de parité Ci sont en position 2i
pour i=0,1,2,…
Les bits du message Dj occupe le reste du message.
D3
D2
D1
C2
D0
C1
C0
7
6
5
4
3
2
1
Ann´ee 2003-2004 – p.4/22
Le code de Hamming (2)
Retrouver l’erreur dans un mot de Hamming
0
0
0
Si les bits de contrôle de réception C
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.
(cid:15) Si C
0 vaut 1, les valeurs possibles de C
2C
1C
2C
1C
0
0
0
0
0 sont 001, 011, 101,
1 vaut 1, les valeurs possibles de C
2C
1C
0 sont 010, 011, 110,
111, c’est-à-dire 1, 3, 5, 7.
(cid:15) Si C
0
(cid:15) Si C
0
111, c’est-à-dire 2, 3, 6, 7.
111, c’est-à-dire 4, 5, 6, 7.
0
0
0
0
0
0
2 vaut 1, les valeurs possibles de C
2C
1C
0 sont 100, 101, 110,
Exercice : y a-t-il une erreur dans le mot suivant ?
1
0
1
0
1
1
0
Ann´ee 2003-2004 – p.5/22