TD Codes correcteurs d’erreurs
Exo 1 Soit le code correcteur d’erreurs donné par : a 7→ 0100, b 7→ 0011, c 7→ 1000, et d 7→ 1111. Décoder
au plus proche voisin : 0111, 0110, 0011. Donner : la distance minimale et le taux d’information. Combien
corrige-t-il d’erreurs ?
0110 0111 1111
1110
0100 0101 1100 1101
0010 0011 1010 1011
0000
0001 1000 1001
Exo 2 Le code : (i) avec bit de parité, et (ii) le code de deux répétitions d’une ‘plage de trois’, est-il un
code linéaire ?
Donner pour les deux codes : les mots du code, la matrice génératrice, la dimension du code, la distance
minimale, les paramètres, le taux d’information
; combien
corrige-t-il d’erreurs ?
100011
Exo 3 Soit la matrice génératrice G = 010101 d’un code linéaire.
001110
1. Quels sont les mots du code ?
2. Quelle est la dimension du code ?
3. Quelle est sa distance minimale?
4. Quels sont les paramètres de ce code ?
5. Quel est son taux d’information ?
6. Combien corrige-t-il d’erreurs ?
7. Comparer ce code avec celui de l’exo 2 point (ii),
8. Vérifier la proposition de Hamming pour ce code.
Exo 4 Soit le code où la suite binaire a1 a2 a3 a4 est codée par a1 a2 a3 a4 c1 c2 c3 , et les ‘bits de parité’
c1 , c2 , c3 sont donnés par :
0 si a1 + a2 + a3 est pair,
c1 =
1 sinon,
0 si a1 + a2 + a4 est pair,
c2 =
1 sinon,
0 si a2 + a3 + a4 est pair,
c3 =
1 sinon.
Donner la matrice génératrice de ce code et répondre aux questions 1–8 de l’exo 3.
Exo 5 Pour le code linéaire définie en exo. 3 :
1. Donner le tableau standard et les classes latérales,
2. Décoder 111011 et 110011.
Exo 6 Si G = (Idk P ) est une matrice génératrice sous forme normale d’un code C, on en déduit une
matrice génératrice H du code dual C d appelée aussi matrice de contrôle par: H = (P t Idn−k ) où P t
dénote la transposée
de la matrice P . Montrer que la matrice de contrôle du code engendré par la matrice
101
génératrice G = est la matrice génératrice du code de répétition de longueur 3.
011
1
TD Codes correcteurs d’erreurs : décodage efficace
100011
Exo 7 Soit la matrice génératrice G = 010101 d’un code linéaire.
001110
1. Calculer la matrice de contrôle H.
2. Calculer le syndrome des chefs de classes.
3. Décoder 111011 et 110011.
Exo 8
1. Donner la matrice de contrôle de Ham(3), pour laquelle les colonnes sont ordonnées selon l’ordre
naturel.
2. Soit y = 1101011. Calculer S(y), le syndrome de y, et decoder y.
3. Construire une matrice génératrice qui correspond à la matrice de contrôle de Ham(3).
Exo 9 Le code de Hamming étendu noté Ham(r) est obtenu à partir du code de Hamming Ham(r) en
lui ajoutant un test de parité. La distance minimale de ce code linéaire passe alors de 3 à 4. Ainsi, les
paramètres de Ham(r) sont (2r , 2r − r, 4). En fait, ce code n’est pas plus efficace que Ham(r) pour le
décodage. En effet, on a ajouté un bit de plus à transmettre à chaque mot du code. Cependant, puisque
ce code a une distance minimale de 4, il permet de corriger une erreur et d’en détecter deux.
00011110
01100110
H= 10101010
11111111
L’algorithme de décodage est : Pour un message reçu y on calcule le syndrome S(y) = (s1 s2 s3 s4 )
• si s4 = 0 et (s1 s2 s3 ) = (0, 0, 0) alors on suppose qu’il n’y a pas eu d’erreur ;
• si s4 = 0 et (s1 s2 s3 ) 6= (0, 0, 0) alors on suppose qu’il y a eu deux erreurs ;
• si s4 = 1 et (s1 s2 s3 ) = (0, 0, 0) alors on suppose qu’il y a eu une erreur en dernière position ;
• si s4 = 1 et (s1 s2 s3 ) 6= (0, 0, 0) alors on suppose qu’il y a eu une erreur en position j, où j est le
nombre representé en binaire (s1 s2 s3 ).
Avec cet algorithme décoder : y = 00000000, y = 10000010, y = 10100010 et y = 11111111.
