Code de Hamming (7,4)

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.

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é	${\displaystyle p_{1}}$	${\displaystyle p_{2}}$	${\displaystyle d_{1}}$	${\displaystyle p_{3}}$	${\displaystyle d_{2}}$	${\displaystyle d_{3}}$	${\displaystyle 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é.

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 :

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.

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 :

${\displaystyle \varphi (1000)=1110000}$

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

${\displaystyle \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 :

${\displaystyle \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}}}$

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:

${\displaystyle \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é.

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 :

${\displaystyle \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.

${\displaystyle \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}}}$

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 :

${\displaystyle \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 :

${\displaystyle \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.

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 :

${\displaystyle \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.

• (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)

• 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