TD 3 — Détection et correction des erreurs binaires
Exercice 1 — Codes à contrôle de parité
On souhaite transmettre le message M=”Bonjour”. Les codes ASCII (sur 7 bits) des caractères sont (en hexadécimal) :
B j n o r u
42 6A 6E 6F 72 75
Q. 1.1 Quel est le message transmis en utilisant un VRC pair ?
Q. 1.2 Quel est le message transmis en utilisant un LRC impair ?
Q. 1.3 Quel est le message transmis en utilisant un VRC pair+LRC pair ?
Correction
Lettre ASCII Binaire VRC pair
B 42 1000010 0
o 6F 1101111 0
n 6E 1101110 1
j 6A 1101010 0
o 6F 1101111 0
u 75 1110101 1
r 72 1110010 0
LRC impair 0111110
VRC pair+LRC pair 1000001 0
Les séquences de bits envoyées avec, soulignés, les bits/mots de parité :
VRC pair ⇒ 10000100 11011110 11011101 11010100 11011110 11101011 11100100
LRC impair ⇒ 1000010 1101111 1101110 1101010 1101111 1110101 1110010 0111110
VRC+LRC pair ⇒ 10000100 11011110 11011101 11010100 11011110 11101011 11100100 10000010
3
Exercice 2 — Code polynômial
On utilise un code de polynôme générateur G(x) = x5 + x3 + x + 1 pour transmettre le message M = 10110010.
Q. 2.1 Quel est le message M’ transmis ?
Correction
On suit la méthode donnée dans le cours (Diapo 8/16).
1. M(x) = x7 + x5 + x4 + x
2. P(x) = M(x) × degré de G(x) = (x7 + x5 + x4 + x) × x5 = x12 + x10 + x9 + x6
3. division de P(x) par G(x)
x12 + x10 + x9 + x6 x5 + x3 + x + 1
+ x12 + x10 + x8 + x7 x7 + x4 + x3 + 1
x + x8 + x7
9 + x6
+ x9 + x7 + x5 + x4
x 8 + x6+ x5 + x4
+ x8 + x6 + x4 + x3
x5 + x3
+ x5 + x3 + x + 1
R(x) = x + 1
4. M 0 (x) = P(x) + R(x) = x12 + x10 + x9 + x6 + x + 1
5. On envoie donc M’=1011001000011.
1
3
Q. 2.2 On reçoit le message M’=11100111001. Ce message est-il correct ?
Correction
Pour que le message soit considéré comme correct il faut que son polynôme soit divisible par G(x) (i.e., que la division donne un reste de
0). Le polynôme équivalent à M’ est M 0 (x) = x10 + x9 + x8 + x5 + x4 + x3 + 1.
x10 + x9 + x8 + x5 + x4 + x3 + 1 x5 + x3 + x + 1
+ x 10 + x 8 + x + x5
6 x5 + x4 + x2 + x
x 9 + x6 + x4 + x3 + 1
+ x9 + x7 + x5 + x4
x7 + x6 + x5 + x3 + 1
+ x7 + x5 + x3 + x2
x 6 + x2 + 1
+ x6 + x 4 + x2 + x
R(x) = x4 + x + 1
R(x) 6= 0 ⇒ Le message est donc erroné. 3
Exercice 3 — Code de Hamming
Soit le code de Hamming de dictionnaire D = {000000, 000111, 101010, 111000, 111111}.
Q. 3.1 On reçoit le message M = 001011. Quel était le message envoyé ?
Correction
M n’est pas un mot du dictionnaire. On calcule donc sa distance par rapport à chaque mot du dictionnaire (distance entre deux mots =
nombres de positions dans les deux mots auxquelles les bits diffèrent).
– d(001011, 000000) = 3
– d(001011, 000111) = 2
– d(001011, 101010) = 2
– d(001011, 111000) = 4
– d(001011, 111111) = 3
La distance est minimale pour deux mots du dictionnaire : 000111 ou 101010. Le message était sans doute un de ces deux mots mais on ne
peut pas le corriger. 3
Q. 3.2 On reçoit le message M = 110101. Quel était le message envoyé ?
Correction
– d(110101, 000000) = 4
– d(110101, 000111) = 3
– d(110101, 101010) = 5
– d(110101, 111000) = 3
– d(110101, 111111) = 2
M n’est pas dans le dictionnaire mais il est à une distance de 2 de 111111 et à une distance supérieure à 2 des autres mots. On corrige donc
M en 111111. 3
