Hamming

Le code de Hamming est un code de détection d’erreurs spécial. Il permet de détecter une erreur, mais il peut aussi la corriger.

Le code de hamming est un code correcteur linéaire dit parfait. Un code est dit parfait si, pour une longueur de code donnée, il n’existe pas d’autre code plus compact permettant la même capacité de correction.

Principe

Nous allons découper un message de N bits en tranches inégales et on va ajouter un nombre R de bits supplémentaires, de manière à satisfaire la formule 2^R-1>=N+R. Ces bits redondants serviront à détecter une erreur et à la corriger. Les bits redondants seront entrelacés avec le message initial. Ces bits redondants (les bits de contrôle) seront ceux dont l’indice est une puissance de 2.

Exemple 1

Prenons un message de 8 bits : 0110 01112

Combien de bits devrons-nous ajouter ? 2^R-1>=8+R→ R vaut 4. il faut donc ajouter 4 bits situés à des positions spécifiques. Le message final (F) comportera 12 bits.

Les 4 bits de contrôles doivent se placer à des indices de puissance 2, à savoir F1, F2, F4, F8 Les autres bits du message initial prennent leur position initiale :

F12 F11 F10 F9 F8 F7 F6 F5 F4 F3 F2 F1
0 1 1 0 C 0 1 1 C 1 C C

Il nous reste à calculer les bits de contrôle. Les bits de contrôles sont un bit de parité paire selon les positions des bits. Nous allons construire un tableau reprenant les positions de 1 à 12 en binaire :

Avec ce tableau, définissons 4 ensembles : L’ensemble E1 contenant les LSB, l’ensemble E2 contenant les bits de rang 2, etc.

E1 = {F1, F3, F5, F7, F9, F11}

E2 = {F2, F3, F6, F7, F10, F11}

E3 = {F4, F5, F6, F7, F12}

E4 = {F8, F9, F10, F11, F12}

Pour chaque ensemble, nous allons maintenant reporter les valeurs que nous connaissons :

Indice de F E4 E3 E2 E1
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0

E1 = {F1, 1, 1, 0, 0, 1}

E2 = {F2, 1, 1, 0, 1, 1}

E3 = {F4, 1, 1, 0, 0}

E4 = {F8, 0, 1, 1, 0}

Remarquez que chaque ensemble possède 1 seul bit inconnu. Nous allons donc déterminer ce bit de manière à ce que chaque ensemble possède un nombre pair de bits à 1 :

F12 F11 F10 F9 F8 F7 F6 F5 F4 F3 F2 F1
0 1 1 0 0 0 1 1 0 1 0 1

Le message à transférer sera alors 0110 0011 0101, avec les 8 bits de données initiales et 4 bits de contrôle.

Quel est le but de ce système ? Si le message possède une erreur, le code de Hamming permet non seulement de la détecter, mais aussi de la corriger !

Exemple 2

Reprenons le message précédent, dans lequel nous glisserons une erreur.

F12 F11 F10 F9 F8 F7 F6 F5 F4 F3 F2 F1
0 1 1 0 0 0 1 1 0 1 0 1

On va reconstruire les ensembles de bits et établir le bit de parité :

  • E1 = {F1, F3, F5, F7, F9, F11} = {1, 1, 0, 0, 0, 1} → E1 = 1
  • E2 = {F2, F3, F6, F7, F10, F11} = {0, 1, 1, 0, 1, 1 } → E2 =0
  • E3 = {F4,F5, F6, F7, F12} = {0, 0, 1, 0, 0 } → E3 = 1
  • E4 = { F8, F9, F10, F11, F12} = {0, 0, 1, 1, 0} → E4 = 0

Et c’est ici que le code de Hamming se révèle intéressant : il a détecté une erreur, puisque les ensembles devaient tous retourner 0. Si on lit les valeurs en sens inverse, de E4 à E1, on obtient 0101. L’erreur se situe au bit de position 0101, à savoir le bit F!

Nous retrouverons le message d’origine en ignorant les bits de contrôle et en corrigeant F5 : 0110 0111.

Astuces

Il existe des astuces pour calculer rapidement un code de Hamming. Reprenons notre premier exemple, avec le message M de 8 bits : 0110 01112.

Pour calculer le nombre C de bits de contrôles, il faut compter le nombre de puissance de 2 disponibles dans le message. Dans notre cas, nous avons les poids 1, 2, 4 et 8, soit 4 bits de contrôle.

Traçons maintenant un tableau de M+C cases (donc 8+4=12).

Nous allons numéroter les cases selon les poids binaire, puis indiquer le message avec les bits de contrôles :

PF12F11F10F9F8F7F6F5F4F3F2F1
M0110F011F1FF

Ensuite, la seconde astuce :

Pour chaque bit à « 1 » dans M, nous allons copier le poids P en binaire. Les bits de contrôles C ne sont pas pris en compte.

P10 P2
11 1 0 1 1
10 1 0 1 0
6 0 1 1 0
5 0 1 0 1
3 0 0 1 1
Parité paire 0 0 0 1

Calculons, colonne par colonne, une parité paire. Le résultat de cette parité paire va donner les différents bits de contrôle à insérer dans le message :

P 12 11 10 9 8 7 6 5 4 3 2 1
M 0 1 1 0 0 0 1 1 0 1 0 1

Reprenons l’exemple n°2 pour voir si l’astuce fonctionne aussi pour le décodage :

P 12 11 10 9 8 7 6 5 4 3 2 1
M 0 1 1 0 0 0 1 0 0 1 0 1

Appliquons la même technique que ci-dessus.

En appliquant une parité paire à notre tableau, il en résulte un nombre binaire 01012, qui est bien la position du bit erroné !

P10 P2
11 1 0 1 1
10 1 0 1 0
6 0 1 1 0
3 0 0 1 1
1 0 0 0 1
Parité paire 0 1 0 1
Print Friendly, PDF & Email