Hamming



--Téléchargez Hamming en PDF --


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 » title= »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.</p>
<h4><b>Exemple 1</b></h4>
<p class=Prenons un message de 8 bits : 0110 01112

Combien de bits devrons-nous ajouter ? 2^R-1>=8+R » title= »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.</p>
<p class=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

0

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.