Un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d'une erreur si elle ne porte que sur une lettre du message.
Un code de Hamming est parfait : pour une longueur de code donnée il n'existe pas d'autre code plus compact ayant la même capacité de correction. En ce sens son rendement est maximal.
Il existe une famille de codes de Hamming ; le plus célèbre et le plus simple après le code de répétition binaire de dimension trois et de longueur un est sans doute le code binaire de paramètres [7,4,3]. Pour chaque alphabet ayant pour nombre de lettres une puissance d'un nombre premier et pour chaque longueur l de code il existe un code de Hamming utilisant cet alphabet et de longueur au moins égal à l.
Plusieurs méthodes permettent de construire un code de Hamming. Une approche consiste à rechercher les codes cycliques de distance minimale égale à trois, le code apparait alors comme un cas particulier de code BCH. Il est aussi possible d'utiliser uniquement les outils de l'algèbre linéaire et particulièrement la théorie des matrices.
Histoire 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 frustrationPrésentation du code de Hamming par l'Ecole Polytechnique fédérale de Lausanne 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ématiquesClaude Shannon A mathematical theory of communication Bell System Technical Journal, vol. 27, pp. 379-423 et 623-656, Juil et Oct 1948. Hamming développeRichard Hamming Error-detecting and error-correcting codes Bell Syst. Tech. J. 29 pp 147 à 160 1950 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 montrentR. C. Bose and D. K. Ray-Chaudhuri On a class of error-. correcting. binary group codes Inform. Control, vol. 3, pp. 68-79, Mars 1960 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éeA. Hocquenghem Codes correcteurs d'erreurs Chiffre 1959 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.
Contexte Code correcteur
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.
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.
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 F2 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 Fd 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é à Fdn.
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.
Code parfait
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 :
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. Paramètres du code Détermination 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 :
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 :
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.
Polynôme énumérateur des poids
Le polynôme énumérateur des poids P[X] est le polynôme dont le coefficient pi du monôme Xi 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 à :
Exemple : code de répétition
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. Exemple : le cas binaire de longueur quatre
] 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 d1d2d3d4. Le mot du code est constitué de trois sommes de contrôles p1p2p3, puis des quatre lettres du mot du message. La valeur de pi 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 dune 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.
Approche linéaire Matrice de parité
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 :
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é.
Exemple : cas binaire de paramètres [15,11,4] Matrice de contrôle 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 Htm = 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.