Code de Hamming
| Sommaire |
Usage du code de Hamming
Travaillons avec des données de longueur 4, comportant 3 symboles de contrôles. Ceci donne des mots codes de longueur 7.
En partant de la matrice de contrôle :
La relation entre les symboles d'information (a1, a2, a3, a4) et ceux de contrôle (a5, a6, a7) est donnée comme ceci :
a5 = a2 + a3 + a4 a6 = a1 + a3 + a4 a7 = a1 + a2 + a4
Une des matrices génératices est donc :
Pour savoir si un mot-code reçu (w) est correct, il faut que z = H * wT = 0. dans le cas contraire, z correspond au bit de erroné en se reportant à la bonne colonne de la matrice H.
Principe
- Les codes de Hamming utilisent la théorie des matrices: on utilise des matrices appelées Matrices de Hamming et notées H, constituées de m+n colonnes. Comme on travaille en base 2, les éléments de H sont des 0 ou des 1.
- Le codage des mots a de n bits consiste à rajouter m bits de correction pour former le mot codé ac de m+n bits. Ces bits de correction seront calculés de façon à ce que le produit de H par ac soit un vecteur colonne nul. Ainsi, si une erreur apparaît à la ième position (bi « bi), le produit de H par le mot transmis a’ ne sera plus nul. En fait, comme un bit diffère entre ac et a’, le produit de H par a’ va donner le vecteur colonne de H situé à la ième position: pour corriger l’erreur, il suffit alors de changer la valeur du bit bi de a’ et d’enlever les bits de correction.
Code de Hamming simple
- Les mots a contiennent 4 bits (n=4) et on rajoute 3 bits de correction.
- À chaque mot a=[b1, b2, b3, b4], on rajoute 3 bits de correction: ac=[ b1, b2, b3, b4, b5, b6, b7]. b1, b2, b3 et b4 sont connus, mais il reste à déterminer b5, b6 et b7. Il faut donc trois équations: elles sont fournies par le produit de H par ac (c’est pour cela que H a trois lignes).
- Une fois la résolution de S achevée, le mot ac peut être transmis. Le décodeur reçoit le mot a’ qui diffère de ac par un bit. Le décodeur fait alors le produit de H par a’ et obtient un vecteur colonne V=[a1, a2, a3]. Ce vecteur colonne se retrouve dans la matrice H à la position i. On sait alors que l’erreur se porte sur le bit bi du mot a’: on peut alors corriger le mot.
- Là aussi, on suppose qu’il n’apparaît tout au plus qu’une erreur par mot c’est à dire une erreur pour 7 bits, ce qui autorise des taux d’erreurs plus faibles qu’avec le code de redondance. Mais ici, le rendement est supérieur: R=4/7.
Code de Hamming avec bit de parité
- En reprenant le même code que précédemment, il est possible d’ajouter un bit de parité afin de rendre le code capable de corriger une erreur et d’en détecter une autre (sans pour autant la corriger). Cela permet des taux d’erreurs plus importants. Le mot codé comporte alors 8 bits: ac=[ b1, b2, b3, b4, b5, b6, b7, bp]. Il faut donc une autre équation pour obtenir la valeur de bp: cette équation est bp=b1+b2+b3+b4+b5+b6+b7 mod 2. Cela revient à rajouter une 4ème ligne à la matrice de Hamming précédente, puis à rajouter une 8ème colonne.
- Le décodage se fait de la même manière sauf que le produit de H par a’ donnera un vecteur colonne V de 4 lignes.
- S’il n’y a aucune erreur, V=[0,0,0,0]
- Si une erreur s’est produite, les trois premiers éléments de V forment le début du vecteur colonne de H donnant la position de l’erreur: on peut donc corriger l’erreur. Le 4ème élément est nul (pas de détection d’autre erreur).
- Si deux erreurs se sont produites, le cas est identique au précédent sauf que le 4ème élément de V est un 1: il y a donc eu détection d’une deuxième erreur: le décodeur peut demander la retransmission du mot.
appartient aux domaines :
- Théorie de l'information
- Théorie du codage