Code de Hamming

Depuis 1946 Richard Hamming (1915-1998) travaille 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 voient les machines s'arrêter invariablement sur des bugs. La frustration^[1] de Hamming le conduit à 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.

En 1960, deux mathématiciens R. C. Bose, D. K. Ray-Chaudhuri montrent^[4] que des idéaux de l'anneau des polynômes sur les corps finis de caractéristique deux sont particulièrement adaptés. La théorie est généralisée^[5] par le mathématicien A. Hocquenghem et donne naissance à la famille de codes BCH. Les codes de Hamming binaires apparaissent immédiatement comme des codes BCH.

L'objectif d'un code correcteur est la détection ou la correction d'erreurs après la transmission d'un message. Cette correction est permise grâce à l'ajout d'informations redondantes. Le message est plongé dans un ensemble plus grand, la différence de taille contient la redondance, l'image du message par le plongement est transmise. En cas d'altération du message, la redondance est conçue pour détecter ou corriger les erreurs. Un code de Hamming procède de cette logique, la redondance permet exactement la correction d'une altération sur une unique lettre du message.

Rappelons les éléments de base de la formalisation. Il existe un ensemble E constitué de suites de longueur k à valeurs dans un alphabet de taille d, c’est-à-dire qu'à partir du rang k, toutes les valeurs de la suite sont nulles. Ces éléments sont l'espace des messages que l'on souhaite communiquer. Pour munir le message de la redondance souhaitée, il existe une application φ injective de E à valeurs dans F, l'espace des suites de longueur n et à valeurs dans un alphabet. La fonction φ est appelée encodage, φ(E) aussi noté C est appelé le code, un élément de φ(E) mot du code, k la longueur du code et n la dimension du code. Ces notations sont utilisées dans tout l'article.

Un code linéaire dispose d'une structure algébrique plus riche que celle du cadre général des codes correcteurs.

Les alphabets A et A' sont identifiés et munis d'une structure de corps fini. Le cas le plus fréquent consiste à choisir le corps F₂ ou l'une de ses extensions finies, on parle alors d'alphabet binaire.

Les ensembles E et F sont naturellement munis d'une structure d'espace vectoriel de dimension respectives k et n. Si F_d désigne le corps fini de cardinal d où d est une puissance d'un nombre premier p, alors l'espace vectoriel fini F est généralement identifié à F_dⁿ.

F est muni d'une distance qui dérive du poids de Hamming. La distance entre deux points de F correspond au nombre de coordonnées non nulles de la différence entre les deux points, dans la base canonique. Un code se décrit par trois paramètres, noté [n, k, δ], n est la longueur du code, k la dimension du code et δ la distance minimale entre deux mots du code. Enfin, l'application d'encodage φ est choisie linéaire, le code est donc un sous-espace vectoriel.

Un code de Hamming est un code linéaire, dont la distance minimale δ est égale à trois. Ces notations sont utilisées dans le reste de l'article.

Usuellement, on considère que le mot de code émis est celui se trouvant le plus près du mot reçu, ce qui revient à supposer que le minimum de lettres a été modifié. Ce procédé conduit à une erreur de décodage chaque fois que l'erreur est supérieure à la capacité corrective du code. La question naturelle est celle de la valeur de t correspondant au nombre maximum d'erreurs corrigibles.

Une interprétation géométrique donne un élément de réponse. Les boules fermées de rayon t centrées sur les mots de code doivent être disjointes. La capacité de correction d'un code correspond au plus grand entier t vérifiant cette propriété, c'est aussi le plus grand entier strictement plus petit que δ/2, ce qui donne une valeur égale à un dans le cas d'un code de Hamming. Elle permet de définir une première majoration, appelée borne de Hamming :

${\displaystyle 1+n.(d-1)\leq d^{n-k}}$ 

Il existe une configuration idéale, correspondant au cas où les boules fermées de rayon un et de centre les mots du code forment une partition de l'espace F. Si la transmission ne produit jamais plus d'une altération, alors l'erreur est corrigible. Il n'existe aucune redondance inutile, le code est le plus compact possible pour garantir la correction certaine d'une erreur. Pour de tels codes, la majoration de la borne de Hamming est une égalité. Ils sont dits parfaits. Ce qui donne lieu à la définition suivante :

• Un code de Hamming est un code linéaire parfait de distance minimale égale à trois.

Un code est parfait, si et seulement si la borne de Hamming est atteinte. Cette propriété permet la détermination des paramètres possibles pour un code de Hamming. Notons m la valeur de n - k. On dispose alors des égalités :

${\displaystyle 1+n\cdot (d-1)=d^{m}\quad {\text{donc}}\quad n={\frac {d^{m}-1}{d-1}}}$ 

L'égalité k = n - m et le fait que la distance minimale d'un code de Hamming est égal à trois démontre la propriété suivante :

• Pour tout code de Hamming sur un corps fini de cardinal d, il existe un entier m supérieur ou égal à deux, tel que les paramètres du code soient :

${\displaystyle \left[{\frac {d^{m}-1}{d-1}},{\frac {d^{m}-1}{d-1}}-m,3\right]}$ 

La propriété correspond à une condition nécessaire. Cependant, pour toute valeur de d et de m, la suite de l'article démontre qu'il existe un unique code de Hamming, à une équivalence près. La condition est donc aussi suffisante.

Le polynôme énumérateur des poids P[X] est le polynôme dont le coefficient p_i du monôme Xⁱ est égal au nombre de mots du code de poids de Hamming égal à i. L'identité de Mac Williams permet son calcul (cf article détaillé). Il est égal à :

${\displaystyle P[X]={\frac {1}{d^{m}}}{\Bigg (}{\Big (}1+(d-1)X{\Big )}^{n}+(d^{m}-1){\Big (}1+(d-1)X{\Big )}^{n-d^{m-1}}(1-X)^{d^{m-1}}{\Bigg )}\;}$ 

Le cas le plus simple est sans conteste celui où d est égal à deux, c’est-à-dire celui où le code est binaire et m est aussi égal à deux. On obtient un code de paramètre [3,1,3].

Les messages sont constitués d'une lettre, par exemple 0, les codes d'une triple répétition de la lettre soit 000 dans l'exemple. Comme l'alphabet ne contient que deux lettres, deux au moins sur trois des lettres d'un élément de F sont semblables, en conclusion tout mot de F est à distance de un d'un mot du code. De plus, un mot de F n'est à une distance d'au plus un que d'un unique mot du code, ce qui démontre que ce code est parfait.

Cette propriété tombe si le code contient plus de deux lettres, en effet il existe des éléments de F constitués de trois lettres différentes et donc à distance de deux de trois mots différents du code et à distance de un d'aucun mot du code. On remarque aussi que la formule des paramètres, si d est différent de deux n'est plus vérifiée.

 

Les codes correcteurs réellement utilisés dans l'industrie sont plus complexes que les précédents. Le plus simple est celui de paramètres [7,4,3].

C'est un code de dimension sept, c’est-à-dire que le récepteur reçoit sept bits, de longueur quatre c’est-à-dire qu'une fois décodé, le message contient quatre lettres et la distance minimale entre chaque mot de code est trois.

La figure de droite est une représentation graphique de ce code. Le message est le mot d₁d₂d₃d₄. Le mot du code est constitué de trois sommes de contrôles p₁p₂p₃, puis des quatre lettres du mot du message. La valeur de p_i est égale à zéro si la somme des trois lettres du message incluses dans son cercle sur la figure est paire et un sinon.

On remarque que la somme des éléments de chaque cercle est paire si et seulement si l'élément est un mot du code. De plus, chaque élément de F est à une distance de un d'un mot du code. En conséquence, ce code est parfait et possède une capacité maximale de correction d'une erreur.

Cet exemple, le plus simple présentant une solution non évidente, présente une approche à même de démontrer l'existence et l'unicité d'une solution pour toutes les valeurs de m dans le cas d'un code binaire.

Il existe une application linéaire surjective de F dans un espace de dimension n - k ayant pour noyau exactement le code :

• Une matrice de contrôle d'un code φ(E) est une matrice H de dimension nx(n - k) tel que :

${\displaystyle x\in \varphi (E)\Leftrightarrow H.^{t}x=0}$ 

Cette application est essentielle à la fois sur le plan de l'implémentation, car elle permet une détection et une correction simple (cf décodage par syndrome) et sur celui de la construction d'un code.

Il existe une relation directe entre la matrice de contrôle et la distance minimale du code :

• La distance minimale δ d'un code linéaire est égale à la dimension du plus petit sous-espace vectoriel S de F généré par des éléments de la base canonique et tel que la restriction de la matrice de contrôle à S soit non injective.

La distance minimale est donc supérieure ou égale à trois si, et seulement si, deux vecteurs colonnes quelconques sont libres. Cette propriété permet de résoudre le cas binaire pour toutes les valeurs de m.

Remarque : Pour le reste de l'article H désigne la matrice de parité.

Dans le cas binaire avec pour valeur de m quatre, la matrice de contrôle est de dimension 15x4, c’est-à-dire qu'elle contient quinze colonnes et quatre lignes. Pour obtenir une distance minimale au moins égale à trois, chaque colonne doit être différente. En effet, une colonne correspond au syndrome d'un vecteur de la base canonique de F, c’est-à-dire à un message de poids un. Si deux colonnes sont semblables, alors le message m, de poids deux dont les coordonnées valent zéro partout sauf pour les deux colonnes égales où les coordonnées valent un, vérifie H^tm = 0. En effet, dans un corps binaire 1 + 1 est égal à 0. Il existerait alors un mot du code de poids deux, en conséquence la distance minimale ne peut être égale à trois. De même, aucun vecteur colonne ne peut être nul, sinon, un vecteur de la base canonique de poids un serait élément du code.

Or, il n'existe que quinze vecteurs dans l'ensemble d'arrivée de la matrice de contrôle. À l'ordre près, il n'existe donc qu'une unique matrice de contrôle possible pour ce cas, correspondant à la suite des nombres de un à quinze en binaire. Si H est choisi de telle manière à représenter un code systématique alors on obtient :

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

L'analyse précédente montre qu'il est nécessaire qu'une matrice de contrôle d'un code de distance minimale égale à trois ait cette forme. Réciproquement cette forme est suffisante pour garantir que la distance minimale soit effectivement égale à trois. En effet, aucun message de poids un n'est élément du code (un message de poids un est un élément de la base canonique) car leurs images par H est un vecteur non nul. Et aucun message de poids deux (un message de poids deux est la somme de deux éléments de la base canonique) n'est élément du code. En effet, ils auraient même image par H car deux vecteurs sont colinéaires si et seulement s'ils sont égaux dans le cas d'un corps binaire, or les vecteurs colonnes sont tous différents.

La matrice de contrôle définit totalement la géométrie du code, il suffit donc, pour terminer l'implémentation de trouver une matrice génératrice G de E dans F. L'application linéaire associée doit vérifier deux conditions : elle est injective, et son image est le noyau de H. Il suffit donc de trouver une matrice de rang 11 tel que H.G = 0 La construction de la matrice G est simplifiée dans le cas où H représente un code systématique, si Id_q la matrice identité d'ordre q :

${\displaystyle G={Id_{k} \choose C}\quad \quad H=(-C\;Id_{n-k})\Rightarrow H.G=(-C\;Id_{n-k})\,{Id_{k} \choose C}=0_{n-kk}}$ 

En remarquant que dans un corps binaire les opérations + et - sont les mêmes, on obtient :

${\displaystyle G={Id_{11} \choose C}\quad avec\quad C={\begin{pmatrix}0\quad 0\quad 0\quad 0\quad 1\quad 1\quad 1\quad 1\quad 1\quad 1&1\\0\quad 1\quad 1\quad 1\quad 0\quad 0\quad 0\quad 1\quad 1\quad 1&1\\1\quad 0\quad 1\quad 1\quad 0\quad 1\quad 1\quad 0\quad 0\quad 1&1\\1\quad 1\quad 0\quad 1\quad 1\quad 0\quad 1\quad 0\quad 1\quad 0&1\end{pmatrix}}}$ 

Le code est donc composé du message et de quatre sommes de contrôle permettant de corriger exactement une erreur.

La méthode précédente se généralise pour tous les codes de Hamming binaires. Les paramètres du code recherchés sont maintenant [2^m - 1, 2^m - m - 1, 3]. On peut citer comme exemple d'utilisation de code de cette nature, celui du minitel^[6] qui a choisi la valeur sept pour m. Ainsi, pour un message de longueur cent vingt, sept sommes de contrôle permettent de corriger toute erreur sur un unique bit.

La matrice de contrôle est de dimension mx2^m - 1. Une condition nécessaire et suffisante pour que la distance minimale associée soit égale à trois est que tous les vecteurs soit libres deux à deux. C'est le cas s'ils sont non nuls et tous différents. Un espace vectoriel binaire de dimension m contient exactement 2^m - 1 vecteurs non nuls différents. À l'ordre près, il n'existe donc qu'une unique matrice de contrôle associée à une distance minimale égale à trois.

Il est toujours possible de réordonner la matrice de contrôle pour lui donner la forme d'un code systématique. Cette forme permet simplement de calculer la matrice génératrice systématique associée.

• Si m est un entier supérieur ou égal à deux, il existe un seul code binaire, de paramètres [2^m - 1, 2^m - m - 1, 3], à une équivalence près. Ces codes forment l'ensemble des codes binaires de Hamming, ils sont parfaits.

Deux raisons poussent à généraliser le code. Une dimension égale à 2^m - 1 n'est pas idéale, en terme industriel. Il est en effet plus commode d'utiliser une dimension de la forme 2^m. De plus un tel code corrige une erreur, mais si deux erreurs se produisent, non seulement le code ne le détecte pas, mais en plus il en ajoute une troisième.

Ces deux raisons amènent en général à ajouter une dernière somme de contrôle validant la parité des 2^m - 1 premières lettres du code. Une deuxième erreur est alors détectée, même si elle ne peut être corrigée sans nouvelle transmission.

• Le code de Hamming généralisé (dit également 'étendu'), de paramètre [2^m, 2^m - m - 1, 4] correspond à un code de Hamming classique [2^m - 1, 2^m - m - 1, 3] auquel a été ajouté un bit de parité portant sur les 2^m -1 lettres du mot du code.

L'utilisation d'autres corps que binaires n'est pas une préoccupation uniquement théorique. Ils sont utilisés pour corriger des effacements qui peuvent être importants. Ils sont utilisés par exemple pour la lecture des disques compacts pouvant corriger jusqu'à 4096 effacements consécutifs^[7].

Tous les corps finis possèdent un cardinal de la forme p^q où p est un nombre premier. L'industrie utilise souvent la valeur p égale à deux. Le code est encore transmis sous forme de bits, la table d'addition reste inchangée, en revanche la multiplication n'est plus la même. On obtient, par exemple pour le corps F₈ à huit éléments la table suivante :

Si la logique linéaire reste la même, en revanche, la modification de la table de multiplication engendre une complexité supplémentaire à l'encodage et au décodage. Le terme précis n'est plus somme de contrôle mais de contrôle de redondance cyclique ou encore CRC.

Étudions sur F₈ le cas où m est égal à deux. Il correspond aux paramètres [9, 7, 3]. La matrice de contrôle est de dimension 2x9. Le théorème sur la relation entre la distance minimale et la matrice de contrôle montre que pour bâtir ce code, il suffit de trouver neuf vecteurs dans un espace de dimension deux, libres deux à deux. La logique précédente ne s'applique plus, deux vecteurs distincts peuvent être colinéaires, par exemple:

${\displaystyle (001,011)=011.(010,001)\;}$ 

Une matrice de dimension 2x9 est associée à une distance minimale égale à trois si et seulement si chaque vecteur colonne est choisi dans une classe de l'espace projectif de F₈² différente. Chaque classe d'équivalence de l'espace projectif contient sept éléments (le cardinal du corps moins un), et l'espace projectif est une partition de l'espace des syndromes sans le vecteur nul, c’est-à-dire un ensemble de cardinal soixante trois. Il existe exactement neuf éléments dans l'espace projectif, exactement le nombre de colonnes dans la matrice de contrôle. La matrice de contrôle est donc encore unique, à l'ordre près et à une homothétie près pour chaque vecteur colonne. On peut choisir par exemple :

${\displaystyle H={\begin{pmatrix}001&010&100&011&110&101&111&001&000\\001&001&001&001&001&001&001&000&001\end{pmatrix}}}$ 

La même logique que précédemment permet de déterminer la matrice génératrice :

${\displaystyle G={\begin{pmatrix}Id_{7}&C\end{pmatrix}}\quad avec\quad C={\begin{pmatrix}001&001\\010&001\\100&001\\011&001\\110&001\\101&001\\111&001\end{pmatrix}}}$ 

Le code est donc composé du message et deux contrôles de redondance cyclique permettant de corriger exactement une erreur.

Si l'on compte en termes de bit, trois bits sont nécessaires pour coder une lettre. Le code est donc dune longueur 27 bits avec 6 bits de CRC. Si on le compare au code de Hamming binaire de longueur 26 avec 5 bits de parité, le gain n'est pas clair. En pratique, l'utilisation de corps plus vastes est surtout l'objet de codes offrant des redondances beaucoup plus importantes comme ceux de Reed-Solomon.

Le cas général est proche de l'exemple précédent. L'existence et l'unicité d'un code de Hamming sur un corps de cardinal d et pour la valeur m dépend du cardinal de l'espace projectif d'un espace vectoriel sur le corps F_d. L'espace vectoriel S des syndromes est de dimension m. Il contient d^m - 1 vecteurs non nuls, le corps contient d - 1 éléments non nuls, l'espace projectif de S est donc de cardinal d^m - 1/d - 1. C'est exactement la dimension de F, l'espace des codes. À un ordre près et à une homothétie près sur chaque vecteur de la base canonique de F, il n'existe donc qu'une unique matrice de contrôle. En conclusion :

• Si d est une puissance d'un nombre premier et m un entier supérieur à deux, à une équivalence près, il existe un et un seul code de Hamming de paramètres :

${\displaystyle \left[{\frac {d^{m}-1}{d-1}},{\frac {d^{m}-1}{d-1}}-m,3\right]}$ 

Sa construction est analogue à celle utilisée pour l'exemple précédent.

Il est possible d'enrichir la structure algébrique de F d'une structure d'anneau. Cet enrichissement a pour objectif de construire des codes ayant de bonnes propriétés d'optimalité. Les codes BCH ainsi que ceux de Reed-Solomon sont les exemples principaux. Dans le cas binaire, un code de Hamming apparait comme un code cyclique de type BCH.

Pour comprendre cette structure d'anneau, une première remarque est nécessaire. L'extension de F₂ de cardinal 2^m possède comme groupe multiplicatif un groupe cyclique d'ordre 2^m - 1, on retrouve ici la dimension n d'un code binaire de Hamming. Tout élément de l'extension est donc racine du polynôme P[X] = Xⁿ - 1. Un polynôme à coefficients dans F₂, K[X] définit une fonction sur l'extension de cardinal 2^m. Il existe un et un seul polynôme R[X] de degré strictement inférieur à n et ayant les mêmes valeurs sur cette extension que K[X]. En effet, la division euclidienne donne l'égalité suivante si d R[X] désigne le degré du polynôme R[X] :

${\displaystyle K[X]=Q[X].P[X]+R[X]\quad avec\quad d\,R[X]<n\;}$ 

La structure d'anneau choisie est alors celle du quotient F_d/P[X]. Les codes associés sont les idéaux de cet anneau.

• Soit m un entier strictement positif et n un entier défini par n = 2^m - 1. Un code linéaire sur F_d est dit cyclique si l'espace vectoriel est muni de la structure d'anneau F_d/P[X], avec P[X] = Xⁿ - 1 et que le code est un idéal de F.

Dire que le code est un idéal revient à dire qu'il est cyclique, c’est-à-dire qu'il vérifie la propriété suivante :

${\displaystyle \forall (x_{n-1},x_{n-2},\cdots ,x_{1},x_{0})\in C\quad (x_{n-2},x_{n-3},\cdots ,x_{0},x_{n-1})\in C}$ 

Soit Φ_n[X] un polynôme cyclotomique d'ordre n la dimension du code, et à coefficient dans F₂. C'est un polynôme de degré m (cf l'article Polynôme cyclotomique), de plus :

• L'idéal C engendré par Φ_n[X] est un code cyclique de longueur k = n - m.

Il possède la bonne distance minimale :

• L'idéal C engendré par Φ_n[X] possède une distance minimale égale à trois.

Ce code cyclique est donc un code binaire de Hamming et tout code binaire de Hamming admet une représentation cyclique.

Les démonstrations se trouvent dans l'article associé.

• (en) Jessie MacWilliams et Neil Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977, (ISBN 9780444850096)
• A. Spătaru, Fondements de la théorie de la transmission de l'information, - (éd. PPUR, 1987) - (ISBN 9782880741334)
• Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]

• Code Linéaire par G. Zemor, université Bordeaux I

•   Portail des télécommunications
•   Portail de l'informatique théorique