Série d’Exercice N° 02 – Corrigé – Licence 03 ISIL B – 2023/2024

Exercice 1 : Contrôle de Parité

Soit une code C contenant les mots suivants : 1010010101, 1011110111, 0001001000
• On veut appliquer un contrôle de parité impaire sur chaque mot du code C, que devient ce code ?
Code VRC : Contrôle de Parité Verticale – Par Ligne – Parité Impaire :
- si Nombre de bits ‘1’ est Paire ➔ bit de Parité == 1
- si Nombre de bits ‘1’ est Impaire ➔ bit de Parité == 0
On a : C == M1|M2|M3
On a : M1 == 1010010101 – Nombre de bits ‘1’ == 5 ➔ Impaire ➔ bit de Parité == 0
On a : M2 == 1011110111 – Nombre de bits ‘1’ == 8 ➔ Paire ➔ bit de Parité == 1
On a : M3 == 0001001000 – Nombre de bits ‘1’ == 2 ➔ Paire ➔ bit de Parité == 1
➔ VRC_Impaire(M1) == 1010010101 | 0
➔ VRC_Impaire(M2) == 1011110111 | 1
➔ VRC_Impaire(M3) == 0001001000 | 1
➔ VRC_Impaire(C) == 101001010101011110111100010010001
• Même question avec un contrôle VRC/LRC.
Code VRC/LRC : Contrôle de Parité Verticale && Longitudinale – Par Ligne && Par Colonne – Parité Impaire :
- si Nombre de bits ‘1’ est Paire ➔ bit de Parité == 1
- si Nombre de bits ‘1’ est , ➔ bit de Parité == 0
On a : M1 == 1010010101
On a : M2 == 1011110111
On a : M3 == 0001001000
VRC/LRC_Impaire(C) == 1010010101 | 0
1011110111 | 1
0001001000 | 1
-----------+---
1111010101 | 1
➔ VRC/LRC_Impaire(C) == 10100101010101111011110001001000111110101011
• On suppose que l'émetteur applique un contrôle VRC/LRC. Le récepteur reçoit le bloc suivant (la colonne 11 et la
ligne 4 sont des bits de parité) :
10100101010
11011001111
00010010001
11110101011
a. Y-a-il une erreur lors de la réception ? si Oui corriger cette erreur.
On vérifie les bits de Parité – Parité Impaire :
1010010101|0
1101100111|1 X
0001001000|1
------------
1111010101|1
XX X
La ligne N°02 est Erronée && les Colonnes N°02 && 03 && 06 sont Erronées ➔ La réception comporte des Erreurs
Correction des Erreurs : Les bits Erronés représentent l’Intersection de la ligne N°02 et les Colonnes N° 02 && 03
&& 06
➔ Inverser les 03 bits au niveau de ces Intersections
Message Corrigé :
1010010101|0
1011110111|1
0001001000|1
1111010101|1
Exercice 2 : Code de Hamming
On veut appliquer le code auto-correcteur de Hamming sur le Code C (voir exercice 1).
• Que vaut la distance de Hamming ?
On a : C == M1|M2|M3
On a : M1 == 1010010101
On a : M2 == 1011110111
On a : M3 == 0001001000
On sait que : dHamming(C) == MIN(dHamming(M1,M2), dHamming(M1,M3), dHamming(M2,M3))
dHamming(M1,M2) == dHamming(1010010101, 1011110111) == 3
dHamming(M1,M3) == dHamming(1010010101, 0001001000) == 7
dHamming(M2,M3) == dHamming(1011110111, 0001001000) == 8
➔ dHamming(C) == MIN(3, 7, 8) == 3
• Combien de bits erronés peut-on détecter ? corriger ?
Nombre de bits erronés : e :
On sait que : Capacité de Détection : Cd : Cd == 1 + e <= dHamming
➔ e == dHamming – 1 == 3 – 1 == 2 bits
Nombre de bits erronés : c :
On sait que : Capacité de Correction : Cc : Cc == 1 + 2*c <= dHamming
➔ c == (dHamming – 1)/2 == (3 – 1)/2 == 1 bit
• Que devient la taille de chaque mot codé sachant que le nombre de bits de contrôle à utiliser est calculé par la
formule r = log2(k) + 1 (k : la taille du mot à coder) ?
On sait que : n == k + r
- n : Taille du mot Codé (Information Utile + bits de Contrôle)
- k : Taille du mot à coder (Information Utile)
- r : Taille du Code (bits de Contrôle)
D’après l’exercice, on a : k == 10 bits
On sait que : r == log2(k) + 1
➔ r == log2(10) + 1 == 3 + 1 == 4 bits
➔ n == 10 + 3 == 14 bits
• Coder le mot " 10100101010 " en appliquant une parité paire. :
On a : C == 10100101010
On a : k == 11 bits
➔ r == log2(11) + 1 == 3 + 1 == 4 bits
➔ Il faut ajouter au mot C 4 bits de Contrôle : k1, k2, k4 et k8
k1, k2, k4 et k8 occupent les bits avec des positions puissance de 2 :
- k1 : bit de position 20 == 1
- k2 : bit de position 21 == 2
- k4 : bit de position 22 == 4
- k8 : bit de position 23 == 8
➔ Les bits du mot Codé (qui est d’une taille de 11 + 4 == 15 bits) occupent les autres positions :
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
1 0 1 0 0 1 0 k8 1 0 1 k4 0 k2 k1
- 3 == 2 + 1 (le bit à la Position N°3 est Contrôlé par les bits de Contrôle k1 et k2)
- 5 == 4 + 1 (le bit à la Position N°5 est Contrôlé par les bits de Contrôle k4 et k1)
- 6 == 4 + 2 (le bit à la Position N°6 est Contrôlé par les bits de Contrôle k4 et k2)
- 7 == 4 + 2 + 1 (le bit à la Position N°7 est Contrôlé par les bits de Contrôle k4, k2 et k1)
- 9 == 8 + 1 (le bit à la Position N°9 est Contrôlé par les bits de Contrôle k8 et k1)
- 10 == 8 + 2 (le bit à la Position N°10 est Contrôlé par les bits de Contrôle k8 et k2)
- 11 == 8 + 2 + 1 (le bit à la Position N°11 est Contrôlé par les bits de Contrôle k8, k2 et k1)
- 12 == 8 + 4 (le bit à la Position N°12 est Contrôlé par les bits de Contrôle k8 et k4)
- 13 == 8 + 4 + 1 (le bit à la Position N°13 est Contrôlé par les bits de Contrôle k8, k4 et k1)
- 14 == 8 + 4 + 2 (le bit à la Position N°14 est Contrôlé par les bits de Contrôle k8, k4 et k2)
- 15 == 8 + 4 + 2 + 1 (le bit à la Position N°15 est Contrôlé par les bits de Contrôle k8, k4, k2 et k1)

➔ Les bits de Contrôle k1, k2, k4 et k8 contrôlent les bits aux Positions suivantes :
- k1 Contrôle les bits aux Positions N° : 3, 5, 7, 9, 11, 13 et 15
- k2 Contrôle les bits aux Positions N° : 3, 6, 7, 10, 11, 14 et 15
- k4 Contrôle les bits aux Positions N° : 5, 6, 7, 12, 13, 14 et 15
- k8 Contrôle les bits aux Positions N° : 9, 10, 11, 12, 13, 14 et 15

➔ D’après l’exercice : le Codage demandé est de Parité Paire :

- si Nombre de bits ‘1’ est Paire ➔ bit de Parité == 0
- si Nombre de bits ‘1’ est Impaire ➔ bit de Parité == 1
03 05 07 09 11 13 15
- k1 : 0 1 1 0 0 1 1 == 0
03 06 07 10 11 14 15
- k2 : 0 0 1 1 0 0 1 == 1
05 06 07 12 13 14 15
- k4 : 1 0 1 0 1 0 1 == 0
09 10 11 12 13 14 15
- k8 : 0 1 0 0 1 0 1 == 1
➔ Message Codé : 101001011010010
• On suppose que le récepteur reçoit le mot suivant " 11011101010100 ". Y-a-il une erreur ? si oui corriger cette
erreur ? (On suppose que la taille du code initial est 10 bits)
On a : C == 11011101010100
On a : k == 10 bits
On a : n == 14 bits
On sait que : n == k + r
➔ r == n – k == 14 – 10 == 4 bits
14 13 12 11 10 9 8 7 6 5 4 3 2 1
1 1 0 1 1 1 k8 == 0 1 0 1 k4 == 0 1 k2 == 0 k1 == 0
On a : Les bits de Contrôle k1, k2, k4 et k8 contrôlent les bits aux Positions suivantes :
- k1 Contrôle les bits aux Positions N° : 3, 5, 7, 9, 11 et 13
- k2 Contrôle les bits aux Positions N° : 3, 6, 7, 10, 11 et 14
- k4 Contrôle les bits aux Positions N° : 5, 6, 7, 12, 13 et 14
- k8 Contrôle les bits aux Positions N° : 9, 10, 11, 12, 13 et 14
➔ D’après l’exercice : le Codage demandé est de Parité Paire :
03 05 07 09 11 13
- k1 : 1 1 1 1 1 1 == 0 ➔ Vrai
03 06 07 10 11 14
- k2 : 1 0 1 1 1 1 == 0 ➔ Faux
05 06 07 12 13 14
- k4 : 1 0 1 0 1 1 == 0 ➔ Vrai
09 10 11 12 13 14
- k8 : 1 1 1 0 1 1 == 0 ➔ Faux
➔ Le Message reçu comporte une Erreur
L’Erreur est détectée par k2 et k8 et non pas par k1 et k4 ➔ Le bit Erroné est Contrôlé par k2 et k8 et non pas par k1
et k4 ➔ {3, 6, 7, 10, 11, 14} ^ {9, 10, 11, 12, 13, 14} – {3, 5, 7, 9, 11, 13} v {5, 6, 7, 12, 13, 14}
➔ {10, 11, 14} – {3, 5, 6, 7, 9, 11, 12, 13, 14} == 10
➔ Le bit Erroné se trouve à la Position N°10 == 1  (1010)2 == 10
Correction du bit à la Position N°10 : 1 est remplacé par 0 ➔ Message Corrigé : 11010101010100
Exercice 3 : Codes de détection d'erreurs polynomiaux CRC
• On désire transmettre la séquence de bits suivante : 1101011011. En utilisant le polynôme générateur suivant :
G(X) = X4 + X + 1.
a. Donner la forme polynomiale du message émis.
On sait que : M == (Uk Uk-1 Uk-2 … U2 U1 U0)2 ➔ M(X) == Uk.Xk + Uk-1.Xk-1 + Uk-2.Xk-2 + … + U2.X2 + U1.X1 + U0.X0
On a : M == 1101011011
➔ M(x) == 1.X9 + 1.X8 + 0.X7 + 1.X6 + 0.X5 + 1.X4 + 1.X3 + 0.X2 + 1.X1 + 1.X0
➔ M(x) == X9 + X8 + X6 + X4 + X3 + X + 1
b. Donner la suite binaire complète transmise au récepteur (mot de code émis).
On a : (M)2 == 1101011011
On a : G(X) == X4 + X + 1 ➔ G(X) est de degré 4 ➔ r == 4
➔ Ajouter 4 bits == 0 à M ➔ 11010110110000
On sait que : G(X) en binaire donne : 10011
On divise 11010110110000 par 10011
11010110110000 | 10011
10011 +---------
010011 | 1100001010 == Q(X)
10011 |
0000010110 |
10011 |
0010100 |
10011 |
R(X) == 001110 |
(R)2 == 1110 ➔ Message Transmis == Message Utile | (R)2 == 1101011011 1110
• La détection d'erreurs utilise le CRC G(X) = X6 + X4 + X + 1. Le récepteur reçoit la séquence binaire suivante
101011000110. Le message reçu est-il correct ?
On a : G(X) == X6 + X4 + X + 1 ➔ (G)2 == 1010011
On a : (Message Reçu)2 == 101011000110
On divise 101011000110 par 1010011, si (R)2 == 0 ➔ Pas d’Erreurs, sinon : Erreurs
101011000110 | 1010011
1010011 +---------
00001010011 | 100010
1010011 |
00000000 |
On trouve : (R)2 == 0 ➔ Pas d’Erreurs de Transmission