Pour les articles homonymes, voirHamming.
Uncode de Hamming est uncode correcteurliné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 estparfait : 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 lecode de répétition binaire de dimensiontrois et de longueurun est sans doute le codebinaire de paramètres[7,4,3]. Pour chaque alphabet ayant pour nombre de lettres une puissance d'unnombre premier et pour chaque longueurl 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 lescodes cycliques dedistance minimale égale à trois, le code apparait alors comme un cas particulier decode BCH. Il est aussi possible d'utiliser uniquement les outils de l'algèbre linéaire et particulièrement la théorie desmatrices.
Depuis 1946Richard Hamming(1915-1998) travaille sur un modèle decalculateur à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 desbugs. La frustration[1] de Hamming le conduit à inventer le premier code correcteur véritablement efficace.
Cette période correspond à la naissance de lathé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 decaracté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 decodes 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'unmessage. Cette correction est permise grâce à l'ajout d'informations redondantes. Le message estplongé 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 ensembleE constitué desuites de longueurk à valeurs dans un alphabet de tailled, c’est-à-dire qu'à partir du rangk, 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 uneapplication φinjective deE à valeurs dansF, l'espace des suites de longueurn et à valeurs dans un alphabet. La fonction φ est appeléeencodage, φ(E) aussi notéC est appelé lecode, un élément de φ(E)mot du code,k la longueur du code etn la dimension du code. Ces notations sont utilisées dans tout l'article.
Uncode linéaire dispose d'unestructurealgébrique plus riche que celle du cadre général des codes correcteurs.
Les alphabetsA etA' sont identifiés et munis d'une structure decorps fini. Le cas le plus fréquent consiste à choisir le corpsF2 ou l'une de sesextensions finies, on parle alors d'alphabetbinaire.
Les ensemblesE etF sont naturellement munis d'une structure d'espace vectoriel de dimension respectivesk etn. SiFd désigne lecorps fini de cardinald oùd est une puissance d'unnombre premierp, alors l'espace vectoriel finiF est généralement identifié àFdn.
F est muni d'unedistance qui dérive dupoids de Hamming. La distance entre deux points deF correspond au nombre de coordonnées non nulles de la différence entre les deux points, dans labase 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 choisielinéaire, le code est donc unsous-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 det correspondant au nombre maximum d'erreurs corrigibles.
Une interprétation géométrique donne un élément de réponse. Lesboules fermées de rayont centrées sur les mots de code doivent être disjointes. La capacité de correction d'un code correspond au plus grand entiert 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éeborne de Hamming :
Il existe une configuration idéale, correspondant au cas où les boules fermées de rayonun et de centre les mots du code forment unepartition de l'espaceF. 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 ditsparfaits. Ce qui donne lieu à la définition suivante :
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. Notonsm la valeur den -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 :
La propriété correspond à une condition nécessaire. Cependant, pour toute valeur ded et dem, 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 poidsP[X] est le polynôme dont le coefficientpi du monômeXi 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 à :
Le cas le plus simple est sans conteste celui oùd est égal àdeux, c’est-à-dire celui où le code est binaire etm est aussi égal à deux. On obtient un code de paramètre [3,1,3].
Les messages sont constitués d'une lettre, par exemple0, les codes d'une triple répétition de la lettre soit000 dans l'exemple. Comme l'alphabet ne contient que deux lettres, deux au moins sur trois des lettres d'un élément deF sont semblables, en conclusion tout mot deF est à distance deun d'un mot du code. De plus, un mot deF n'est à une distance d'au plusun que d'un unique mot du code, ce qui démontre que ce code estparfait.
Cette propriété tombe si le code contient plus de deux lettres, en effet il existe des éléments deF constitués de trois lettres différentes et donc à distance dedeux de trois mots différents du code et à distance deun d'aucun mot du code. On remarque aussi que la formule des paramètres, sid est différent de deux n'est plus vérifiée.
.svg)
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 dimensionsept, c’est-à-dire que le récepteur reçoitseptbits, de longueurquatre c’est-à-dire qu'une fois décodé, le message contientquatre lettres et la distance minimale entre chaque mot de code esttrois.
La figure de droite est une représentation graphique de ce code. Le message est le motd1d2d3d4. Le mot du code est constitué de troissommes de contrôlesp1p2p3, puis des quatre lettres du mot du message. La valeur depi est égale àzéro si la somme des trois lettres du message incluses dans son cercle sur la figure est paire etun 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 deF est à une distance deun 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 solutionnon évidente, présente une approche à même de démontrer l'existence et l'unicité d'une solution pour toutes les valeurs dem dans le cas d'un code binaire.
Il existe une application linéairesurjective deF dans un espace de dimensionn -k ayant pour noyau exactement le code :
Cette application est essentielle à la fois sur le plan de l'implémentation, car elle permet une détection et une correction simple (cfdé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 est donc supérieure ou égale à trois si, et seulement si, deuxvecteurs colonnes quelconques sontlibres. Cette propriété permet de résoudre le cas binaire pour toutes les valeurs dem.
Remarque :Pour le reste de l'articleH désigne la matrice de parité.
Dans le cas binaire avec pour valeur demquatre, 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 labase canonique deF, c’est-à-dire à un message depoidsun. Si deux colonnes sont semblables, alors le messagem, de poids deux dont les coordonnées valentzéro partout sauf pour les deux colonnes égales où les coordonnées valentun, vérifieHtm = 0. En effet, dans un corps binaire 1 + 1 est égal à 0. Il existerait alors un mot du code de poidsdeux, 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 poidsun serait élément du code.
Or, il n'existe quequinze 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 deun à quinze en binaire. SiH est choisi de telle manière à représenter un code systématique alors on obtient :
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 poidsun n'est élément du code (un message de poidsun est un élément de la base canonique) car leurs images parH est un vecteur non nul. Et aucun message de poidsdeux (un message de poidsdeux est la somme de deux éléments de la base canonique) n'est élément du code. En effet, ils auraient même image parH 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ératriceG deE dansF. L'application linéaire associée doit vérifier deux conditions : elle estinjective, et son image est lenoyau deH. Il suffit donc de trouver une matrice de rang 11 tel queH.G = 0 La construction de la matriceG est simplifiée dans le cas oùH représente un code systématique, siIdq lamatrice identité d'ordreq :
En remarquant que dans un corps binaire les opérations + et - sont les mêmes, on obtient :
Le code est donc composé du message et de quatresommes 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 [2m - 1, 2m -m - 1, 3]. On peut citer comme exemple d'utilisation de code de cette nature, celui duminitel[6] qui a choisi la valeursept pourm. 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 dimensionmx2m - 1. Unecondition 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 dimensionm contient exactement 2m - 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.
Deux raisons poussent à généraliser le code. Une dimension égale à 2m - 1 n'est pas idéale, en terme industriel. Il est en effet plus commode d'utiliser une dimension de la forme 2m. 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 2m - 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.
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 desdisques compacts pouvant corriger jusqu'à 4096 effacements consécutifs[7].
Tous les corps finis possèdent un cardinal de la formepq oùp est un nombre premier. L'industrie utilise souvent la valeurp é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 corpsF8 à 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 decontrôle de redondance cyclique ou encore CRC.
Étudions surF8 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 trouverneuf vecteurs dans un espace de dimensiondeux, libres deux à deux. La logique précédente ne s'applique plus, deux vecteurs distincts peuvent être colinéaires, par exemple:
Une matrice de dimension 2x9 est associée à une distance minimale égale à trois si et seulement si chaque vecteur colonne est choisi dans uneclasse de l'espace projectif deF82 différente. Chaque classe d'équivalence de l'espace projectif contientsept éléments (le cardinal du corps moinsun), 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 à unehomothétie près pour chaque vecteur colonne. On peut choisir par exemple :
La même logique que précédemment permet de déterminer la matrice génératrice :
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 deReed-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 cardinald et pour la valeurm dépend du cardinal de l'espace projectif d'un espace vectoriel sur le corpsFd. L'espace vectorielS des syndromes est de dimensionm. Il contientdm - 1 vecteurs non nuls, le corps contientd - 1 éléments non nuls, l'espace projectif deS est donc de cardinaldm - 1/d - 1. C'est exactement la dimension deF, l'espace des codes. À un ordre près et à une homothétie près sur chaque vecteur de la base canonique deF, il n'existe donc qu'une unique matrice de contrôle. En conclusion :
Sa construction est analogue à celle utilisée pour l'exemple précédent.
Il est possible d'enrichir lastructure algébrique deF d'une structure d'anneau. Cet enrichissement a pour objectif de construire des codes ayant de bonnes propriétés d'optimalité. Les codesBCH 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 deF2 de cardinal 2m possède comme groupe multiplicatif ungroupe cyclique d'ordre 2m - 1, on retrouve ici la dimensionn d'un code binaire de Hamming. Tout élément de l'extension est donc racine dupolynômeP[X] =Xn - 1. Un polynôme à coefficients dansF2,K[X] définit une fonction sur l'extension de cardinal 2m. Il existe un et un seul polynômeR[X] de degré strictement inférieur àn et ayant les mêmes valeurs sur cette extension queK[X]. En effet, la division euclidienne donne l'égalité suivante sidR[X] désigne le degré du polynômeR[X] :
La structure d'anneau choisie est alors celle du quotientFd/P[X]. Les codes associés sont lesidéaux de cet anneau.
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 :
Soit Φn[X] un polynôme cyclotomique d'ordren la dimension du code, et à coefficient dansF2. C'est un polynôme de degrém (cf l'articlePolynôme cyclotomique), de plus :
Il possède labonne distance minimale :
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é.
Articles sur lathéorie des codes en rapport avec lescodes correcteurs | |
|---|---|
