Code de Hamming (7,4)

En théorie des codes, le Code de Hamming (7,4) est un code correcteur linéaire binaire de la famille des codes de Hamming. À travers un message de sept bits, il transfère quatre bits de données et trois bits de parité. Il permet la correction d'un bit erroné. Autrement dit, si, sur les sept bits transmis, l'un d'eux au plus est altéré (un « zéro » devient un « un » ou l'inverse), alors il existe un algorithme permettant de corriger l'erreur.

Il fut introduit par Richard Hamming (1915-1998) en 1950 dans le cadre de son travail pour les laboratoires Bell.

Histoire

modifier

Depuis 1946 Richard Hamming travaillait sur un modèle de calculateur à carte perforée de faible fiabilité. Si, durant la semaine, des ingénieurs pouvaient corriger les erreurs, les périodes chômées comme la fin de semaine voyaient les machines s'arrêter invariablement sur des bugs. La frustration[1] d'Hamming le conduisit à inventer le premier code correcteur véritablement efficace.

Cette période correspond à la naissance de la théorie de l'information. Claude Shannon (1916 - 2001) formalise cette théorie comme une branche des mathématiques[2]. Hamming développe[3] les prémisses de la théorie des codes et décrit sa solution comme un exemple.

Objectif

modifier

L'objectif du code est la transmission d'un message de quatre bits avec suffisamment de redondances pour que, même si une altération se produit, le récepteur soit capable de corriger automatiquement l'erreur. Le message envoyé est en conséquence plus long. Dans la pratique il contient sept bits, quatre composent le message et les trois autres servent à détecter et à corriger l'erreur, si nécessaire.

L'erreur que protège ce code est nécessairement limitée. Si les sept bits transmis sont tous modifiés, il est vain d'espérer retrouver le message originel. La protection contre la modification d'un unique bit est parfois largement suffisant, c'était le cas de la situation d'Hamming. Une modification d'un unique bit, c’est-à-dire d'un trou non lu sur la carte perforée ou d'une absence de trou considéré comme un trou est relativement rare. Supposons que cette situation se produit sur une série de quatre en moyenne une fois sur mille. Alors cinquante heures d'exécution de programme, qui utilisent par exemple de l'ordre de mille séries voit sa probabilité d'arrêt supérieure à soixante pour cent. La probabilité de trouver deux erreurs sur une série de sept est inférieur à un sur cinq cent mille. L'utilisation de mille séries de longueur sept possède une probabilité d'arrêt inférieure à deux pour mille dans le cas d'une utilisation de cinquante heures si les messages sont protégés par le code. C'était largement suffisant pour éradiquer la frustration d'Hamming.

Approche intuitive

modifier

Code parfait

modifier

La question que l'on peut se poser est : combien d'informations la redondance doit-elle contenir ? Soit p la longueur de cette redondance en bits. En supposant que l'erreur éventuelle ne portera que sur un bit du message total transmis, il existe donc quatre + p états d'erreur possibles, plus un pour l'absence d'erreur. Cinq plus p informations doivent donc être stockées dans p bits. Or p bits peuvent au maximum contenir 2p informations. Cette situation est obtenue si chaque état décrit une information. On peut s'en rendre compte par un exemple. Deux bits peuvent décrire quatre états : 00, 01, 10, 11 ce qui correspond à compter de zéro à trois en base deux. Si le code est idéal, p vérifie l'égalité 5 + p = 2p le terme de gauche décrit les informations nécessaires à la correction et celui de droite la quantité d'informations stockées dans les bits de parité. Cette équation admet une unique solution : p est égal à trois. Un code vérifiant ce type de propriété est dit parfait, l'article associé formalise cette approche.

Bit de parité

modifier
 
Représentation graphique des quatre bits de données et des trois bits de parité

La figure de droite indique le mode de construction du code. Les valeurs d1, d2, d3 et d4 symbolisent les quatre bits du message. Les valeurs p1, p2, p3 correspondent aux bits de parité. Le bit p1 correspond à la parité du cercle vert, si d1 + d2 + d4 est pair p1 est égal à zéro, sinon p1 vaut un. En conséquence, si aucune altération ne se produit, la somme des bits du cercle vert est paire. Cette logique est poursuivie sur les cercles rouge et bleu.

Si une altération se produit par exemple sur p1 alors la parité du cercle de p1 est modifiée, en revanche celles des cercles de p2 et de p3 ne sont pas modifiées. Si la parité de d1 est modifiée, alors celles des cercles de p1 et de p2 le sont mais celle de p3 ne l'est pas. Le récapitulatif de la situation est donné dans le tableau suivant. Les sept colonnes correspondent aux sept possibles altérations des différents bits du message, les trois lignes correspondent aux parités des cercles associés. Si la parité du cercle est conservée alors la cellule associée est verte avec le texte oui, dans le cas contraire la cellule est rouge avec le texte non.

Bit # 1 2 3 4 5 6 7
bit erroné              
Cercle rouge Oui Oui Oui Non Non Non Non
Cercle bleu Oui Non Non Oui Oui Non Non
Cercle vert Non Oui Non Oui Non Oui Non

Si, par exemple les trois parités des trois cercles sont modifiées, alors il existe une erreur sur le bit d4. Pour chaque bit, une erreur engendre un jeu de parité différent. Si aucune erreur n'altère le message alors les trois parités sont à oui.

L'ordre des différentes colonnes n'est pas choisi au hasard. On remarque que si l'on transforme dans le tableau les Non en un et les Oui en zéro alors on obtient la suite des nombres de un à sept en binaire. Cette propriété permet par la suite un décodage aisé.

Construction du code

modifier

Code linéaire

modifier

Un code linéaire dispose d'une structure algébrique plus riche que celle du cadre général des codes correcteurs. L'ensemble E des messages à envoyer est celui de mots de quatre lettres prises dans l'ensemble {0,1}, le message est codé en un mot de sept lettres encore prises dans le même ensemble. On note F l'espace des mots de sept lettres binaires. E et F peuvent être considérés comme des espaces vectoriels sur le corps binaire {0,1}. Les tables d'addition et de multiplication sont les suivantes :

 +   0   1 
 0   0  1
 1   1  0
 .   0   1 
 0   0  0
 1   0  1

L'addition est intéressante car la somme d'une suite de valeurs est égale à zéro dans le corps si la somme est paire dans les entiers et un sinon. La multiplication est habituelle, multiplier par zéro donne toujours zéro et multiplier par un ne modifie pas la valeur.

L'encodage, c’est-à-dire l'opération consistant à transformer le message de E de quatre lettres en un code de F de sept lettres apparait alors comme une application linéaire de E dans F. Elle se décrit par une matrice. Même si le corps est inhabituel, tous les résultats de l'algèbre linéaire s'appliquent ici. Pour cette raison, un tel code est dit linéaire. L'encodage consiste à multiplier le vecteur de quatre lettres binaires par une matrice 7x4 pour obtenir un vecteur composé de sept lettres binaires.

Matrice génératrice

modifier
 
Ordre des différents bits

La connaissance de l'image de chaque vecteur de la base canonique détermine entièrement l'application d'encodage φ. Les quatre vecteurs de la base correspondent aux messages suivants : d1 = 1000, d2 = 0100, d3 = 0010 et d4 = 0001.

L'image de d1, le message qui a des coordonnées nulles en d2, d3 et d4, possède deux parités égales à un, celle de p1 et p2 et une égale à zéro:p3.

En respectant l'ordre de la base de F : p1, p2, d1, p3, d2, d3 et d4, on obtient l'image du premier vecteur :

 

Calculons de la même manière les images des autres vecteurs de la base de E :

 

La matrice de φ, appelée matrice génératrice est formée des quatre colonnes correspondant aux images des vecteurs de la base canonique par φ, on obtient :

 

Exemple

modifier
 
Représentation graphique de l'exemple d = 1011

Considérons l'exemple du message à communiquer d = 1011. Les bits de parités sont alors égaux à zéro pour p1, un pour p2 et zéro pour p3. En respectant l'ordre des vecteurs de la base de F, on obtient manuellement le vecteur c = 0110011. Le produit matriciel de la matrice génératrice G par la matrice colonne D du vecteur d fournit la matrice colonne C du vecteur c:

 

Les deux résultats sont égaux, cependant le calcul matriciel est simple et rapide à implémenter. Le destinataire reçoit le code c contenant à la fois des données et les bits de parité.

Décodage

modifier

Matrice de contrôle

modifier

Le récepteur, sous réserve d'absence d'erreur peut facilement décoder le message c. Il sait que le code reçu : 0110011 contient les données en bleu, en position trois, cinq, six et sept. Il lui faut maintenant savoir si aucune altération n'a modifié le code reçu, ce qui correspond à l'un des rôles des bits de parité en rouge.

Une approche analogue à celle de l'encodage permet la détection d'erreur. Trois conditions doivent être remplies, une par cercle de la figure représentative. Chaque condition s'exprime comme une somme devant être paire, ou encore nulle dans le corps binaire. Ces trois conditions forment les trois lignes d'une matrice dite matrice de contrôle. Un message reçu est sans erreur si et seulement si le produit de la matrice de contrôle H par la matrice colonne C du vecteur c est égal à la matrice colonne nulle.

La condition associée au cercle rouge p3 signifie que la somme p3 + d2 + d3 + d4 doit être paire. La première ligne de la matrice correspond aux coordonnées 0001111. Cette ligne correspond à la première ligne du tableau du paragraphe bit de parité. Il en est de même pour les autres lignes, correspondant aux cercles bleu et vert. On obtient la matrice H :

 

Il est possible de vérifier sur l'exemple que le produit de la matrice H par celle du mot du code c est bien nul. De manière plus générale, il est aussi possible de vérifier que le produit de H par G est bien nul, ce qui assure que tout message reçu est bien validé si aucune altération n'a été commise.

 

Correction d'erreur

modifier
 
Conséquence d'une erreur sur le bit d2

L'objectif du code est la protection contre une erreur. Étudions le cas où le bit de donnée d2 est altéré durant le transfert. Le message reçu n'est plus c = 0110011 mais x = 0110111. Deux conditions, correspondant au cercles rouge et verts, ne sont plus remplies. Le vecteur x ne peut passer le test de la matrice de contrôle :

 

L'erreur est donc détectée, la matrice de contrôle présente un vecteur non nul, correspondant à la valeur 1012 en binaire, soit cinq. La valeur de H.X est appelée syndrome. La correction associée correspond au mot e5 composé de sept lettres égales à zéro sauf une, la cinquième est égale à un. Le décodage, dans le cas d'un syndrome non nul correspond à soustraire (ce qui revient à additionner dans un code binaire) l'erreur e5 = 0000100. On obtient :

 

Quelle que soit l'erreur, à partir du moment où elle n'intervient que sur un bit, la matrice de contrôle fournit en binaire le numéro de la colonne fautive.

Une fois l'erreur corrigée, il est possible d'extraire les données et reconstruire le message initial. Une telle méthode est appelée décodage par syndrome.

Description du mécanisme

modifier

La linéarité de l'application associée à la matrice H filtre totalement le message pour proposer une image ne dépendant que de l'erreur :

 

C'est la raison qui permet de parler de syndrome, il ne dépend que de l'erreur et non du message lui-même.

De plus, l'ordre de la base de F : p1, p2, d1, p3, d2, d3 et d4, ainsi que celui des lignes de la matrice H ont été choisis de telle manière qu'une lecture de gauche à droite correspondent à une liste de colonnes aux représentations binaires des nombres de un à sept ordonnées, l'image de e5 par l'application est donc 101 et une telle propriété est vraie pour tous les ei si i est un entier compris entre un et sept.

Code de Hamming (8,4)

modifier

En cas d'une double erreur, le code détecte une anomalie. Cependant le syndrome propose un chiffre binaire correspondant toujours à une troisième colonne différente des deux précédentes. Ainsi une troisième erreur est ajoutée, car le code ne dispose d'aucun moyen pour différencier une simple d'une double erreur. Pour pallier cet état de fait, ainsi que pour obtenir un code de dimension exactement égale à un octet, un huitième bit est souvent ajouté, il correspond à la parité des sept bits précédents. Une deuxième erreur est ainsi détectée, elle ne peut être corrigée, en revanche l'information d'une double erreur est disponible remplaçant une tentative maladroite, par une demande de retransmission.

Le décodage se fait de la manière suivante :

  • S’il n’y a aucune erreur le syndrome est nul.
  • Si une erreur s’est produite sur les sept premiers bits, les trois premiers éléments du syndrome donnent la position de l'erreur. L'existence d'un nombre d'erreur impair est confirmé par le huitième bit.
  • Si deux erreurs se sont produites, les trois premiers éléments du syndrome ne sont pas tous nuls et le huitième bit indique une parité exacte, signal d'un nombre pair d'erreurs. Une retransmission est nécessaire.
  • Si une erreur s'est produite sur le huitième bit, l'absence d'erreur sur les trois premiers éléments du syndrome permet de localiser l'erreur et le message est validé.

Le tableau suivant décrit les quatre premiers messages ainsi que leurs encodages pour Hamming (7,4) et (8,4)

Données
 
Hamming(7,4) Hamming(7,4) avec bit de parité (Hamming(8,4))
Transmis
 
Diagramme Transmis
 
Diagramme
0000 0000000   00000000  
1000 1110000   11100001  
0100 1001100   10011001  
1100 0111100   01111000  

Notes et références

modifier
  1. Présentation du code de Hamming par l'École Polytechnique fédérale de Lausanne
  2. Claude Shannon A mathematical theory of communication Bell System Technical Journal, vol. 27, p. 379-423 et 623-656, Juil et Oct 1948
  3. Richard Hamming Error-detecting and error-correcting codes Bell Syst. Tech. J. 29 p. 147 à 160 1950

Voir aussi

modifier

Bibliographie

modifier

Liens externes

modifier