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

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 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. Hamming développe les prémisses de la théorie des codes et décrit sa solution comme un exemple.

Objectif

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

Code parfait

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 2^p 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 = 2^p 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é

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 d₁, d₂, d₃ et d₄ symbolisent les quatre bits du message. Les valeurs p₁, p₂, p₃ correspondent aux bits de parité. Le bit p₁ correspond à la parité du cercle vert, si d₁ + d₂ + d₄ est pair p₁ est égal à zéro, sinon p₁ 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 p₁ alors la parité du cercle de p₁ est modifiée, en revanche celles des cercles de p₂ et de p₃ ne sont pas modifiées. Si la parité de d₁ est modifiée, alors celles des cercles de p₁ et de p₂ le sont mais celle de p₃ 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é	$p_{1}$	$p_{2}$	$d_{1}$	$p_{3}$	$d_{2}$	$d_{3}$	$d_{4}$
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 d₄. 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

Code linéaire

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

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 : d₁ = 1000, d₂ = 0100, d₃ = 0010 et d₄ = 0001.

L'image de d₁, le message qui a des coordonnées nulles en d₂, d₃ et d₄, possède deux parités égales à un, celle de p₁ et p₂ et une égale à zéro:p₃.

En respectant l'ordre de la base de F : p₁, p₂, d₁, p₃, d₂, d₃ et d₄, on obtient l'image du premier vecteur :

$\varphi (1000)=1110000$

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

$\varphi (0100)=1001100\;,\quad \varphi (0010)=0101010\;et\quad \varphi (0001)=1101001\;$

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 :

$\mathbf {G} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}$

Exemple

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 p₁, un pour p₂ et zéro pour p₃. 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:

$\mathbf {D} ={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}\quad \mathbf {G.D} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}\quad et\quad \mathbf {C} =\mathbf {G.D} ={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}$

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

Matrice de contrôle

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 p₃ signifie que la somme p₃ + d₂ + d₃ + d₄ 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 :

$\mathbf {H} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}$

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.

$\mathbf {H.C} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}.{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}\quad et\quad \mathbf {H.G} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}.{\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}={\begin{pmatrix}0&0&0&0\\0&0&0&0\\0&0&0&0\\\end{pmatrix}}$

Correction d'erreur

Conséquence d'une erreur sur le bit d₂

L'objectif du code est la protection contre une erreur. Étudions le cas où le bit de donnée d₂ 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 :

$\mathbf {H.X} ={\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\\\end{pmatrix}}.{\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}$

L'erreur est donc détectée, la matrice de contrôle présente un vecteur non nul, correspondant à la valeur 101₂ en binaire, soit cinq. La valeur de H.X est appelée syndrome. La correction associée correspond au mot e₅ 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 e₅ = 0000100. On obtient :

$\mathbf {C} =\mathbf {X} +\mathbf {E} _{5}={\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\0\\{\overline {1}}\\0\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}$

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

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 :

$\mathbf {H.X} =\mathbf {H} .(\mathbf {C} +\mathbf {E} _{5})=\mathbf {H.C} +\mathbf {H.E} _{5}=0+\mathbf {H.E} _{5}=\mathbf {H.E} _{5}$

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 : p₁, p₂, d₁, p₃, d₂, d₃ et d₄, 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 e₅ par l'application est donc 101 et une telle propriété est vraie pour tous les e_i si i est un entier compris entre un et sept.

Code de Hamming (8,4)

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 $({\color {blue}d_{1}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})$	Hamming(7,4)		Hamming(7,4) avec bit de parité (Hamming(8,4))
	Transmis $({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}})$	Diagramme	Transmis $({\color {red}p_{1}},{\color {red}p_{2}},{\color {blue}d_{1}},{\color {red}p_{3}},{\color {blue}d_{2}},{\color {blue}d_{3}},{\color {blue}d_{4}},{\color {green}p_{4}})$	Diagramme
0000	0000000		00000000
1000	1110000		11100001
0100	1001100		10011001
1100	0111100		01111000

Voir aussi

Bibliographie

• (en) Jessie MacWilliams et Neil Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977 (ISBN 978-0-44485009-6)
• A. Spătaru, Fondements de la théorie de la transmission de l'information, PPUR, 1987 (ISBN 978-2-88074133-4)

Liens externes

• Code correcteur C.I.R.C par J.P. Zanotti, université de Toulon
• L'algèbre et la correction des erreurs par Dany-Jack Mercier, université Antilles-Guyane
• Code Linéaire par G. Zemor, université Bordeaux I
• Cours de code par Christine Bachoc, université Bordeaux I
• Hamming (7,4) Code Calculator
• Hamming (7,4) Code Checker