Distance de Hamming
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

La distance de Hamming, définie par Richard Hamming, est utilisée en informatique, en traitement du signal et dans les télécommunications. Elle joue un rôle important en théorie algébrique des codes correcteurs. Elle permet de quantifier la différence entre deux séquences de symboles.

La distance de Hamming (La distance de Hamming, définie par Richard Hamming, est utilisée en informatique, en traitement du signal et dans les télécommunications. Elle joue un rôle important en théorie algébrique...) est une distance au sens (SENS (Strategies for Engineered Negligible Senescence) est un projet scientifique qui a pour but l'extension radicale de l'espérance de vie humaine. Par une évolution progressive allant du...) mathématique du terme. À deux suites de symboles de même longueur (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est...), elle associe l'entier désignant le cardinal de l'ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une...) des symboles de la première suite qui différent de la deuxième.

Le poids (Le poids est la force de pesanteur, d'origine gravitationnelle et inertielle, exercée par la Terre sur un corps massique en raison uniquement du voisinage de la Terre. Elle est égale à l'opposé de la...) de Hamming correspond au nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'éléments différents de zéro (Le chiffre zéro (de l’italien zero, dérivé de l’arabe sifr, d’abord transcrit zefiro en italien) est un symbole marquant une position vide dans l’écriture des nombres en notation...) dans une chaine d'éléments d'un corps fini.

Intérêt du concept

Histoire et domaine d'applications

La distance de Hamming doit son nom à Richard Hamming (Richard Wesley Hamming (11 février 1915 à Chicago - 7 janvier 1998 Monterey (Californie)) est un mathématicien célèbre à qui on doit le fameux Code de Hamming. Il recut le Prix Turing...) (1915 1998). Elle est décrite dans un article[1] fondateur pour la théorie (Le mot théorie vient du mot grec theorein, qui signifie « contempler, observer, examiner ». Dans le langage courant, une théorie est une idée ou une connaissance spéculative, souvent basée sur...) des codes. Elle est utilisée en télécommunication (Les télécommunications sont aujourd’hui définies comme la transmission à distance d’information avec des moyens électroniques. Ce terme est plus utilisé que le terme synonyme officiel...) pour compter le nombre de bits altérés dans la transmission d'un message (La théorie de l'information fut mise au point pour déterminer mathématiquement le taux d’information transmis dans la communication d’un message par un canal de communication,...) d'une longueur donnée (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction d'affaire, d'un événement, etc.). Le poids de Hamming correspond au nombre de bits différents de zéro, il est utilisé dans plusieurs disciplines comme la théorie de l'information, la théorie des codes et la cryptographie (La cryptographie est une des disciplines de la cryptologie s'attachant à protéger des messages (assurant confidentialité, authenticité et intégrité) en s'aidant souvent de secrets ou clés.). Néanmoins, pour comparer des séquences de longueurs variables, ou des chaines de caractères pouvant subir non seulement des substitutions, mais aussi des insertions ou des effacements, des métriques plus sophistiquées comme la distance de Levenshtein sont plus adaptées.

Motivation (La motivation est, dans un organisme vivant, la composante ou le processus qui règle son engagement dans une action ou expérience. Elle en détermine le déclenchement dans une certaine direction avec l'intensité souhaitée et en assure la...)

Illustration d'un code non correcteur et d'un code correcteur
Illustration d'un code non correcteur et d'un code correcteur

Les codes correcteurs ont leur source dans un problème de la transmission de données. Parfois, une transmission de données se fait en utilisant une voie de communication (La communication concerne aussi bien l'homme (communication intra-psychique, interpersonnelle, groupale...) que l'animal (communication intra- ou inter- espèces) ou la machine (télécommunications, nouvelles technologies...),...) non entièrement fiable. L'objectif d'un code correcteur est l'apport d'une redondance de l'information de telle manière à ce que l'erreur puisse être détectée voir corrigée.

Un message est un élément d'un ensemble E constitué de suites finies de lettres choisies dans un alphabet A. L'apport de la redondance est le résultat d'une application injective φ de E dans un ensemble F constitué aussi de suite finies de lettres d'un alphabet A'. Les suites de l'ensemble F sont choisies a priori plus longues que celle de E. L'ensemble φ(E) est appelé code et un élément de cet ensemble φ(m) mot du code. L'intérêt de transmettre φ(m) à la place de m est illustré par la figure à droite :

Le cas d'un code sans redondance est illustré à gauche sur la figure. F est alors égal à E et φ est l'identité. Si un message en vert (Le vert est une couleur complémentaire correspondant à la lumière qui a une longueur d'onde comprise entre 490 et 570 nm. L'œil humain possède un récepteur,...) subit, lors de sa transmission, une altération, un nouveau message en rouge (La couleur rouge répond à différentes définitions, selon le système chromatique dont on fait usage.) est transmis. Aucune information ne laisse supposer qu'une erreur a été commise.

Pour pallier cet état, l'objectif est d'entourer les mots du code, correspondant, sur la figure de droite aux points verts, par des messages connus pour contenir des erreurs. Ces redondances sont illustrées par les intersections du quadrillage orange. Si une unique erreur se produit, alors le message transmis correspond à un point (Graphie) rouge. Si la redondance a été habilement construite, il n'existe qu'un point vert proche du point rouge reçu, l'erreur est corrigible.

La distance de Hamming correspond sur la figure au plus petit nombre de segments du quadrillage à traverser pour joindre deux points.

Définition (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) et exemples

Définitions

  • Soit A un alphabet et F l'ensemble des suites de longueur n à valeur dans A. La distance de Hamming entre deux éléments a et b de F est le cardinal de l'ensemble des images de a qui diffèrent de celle de b.

Formellement, si d(.,.) désigne la distance de Hamming :

\forall a,b \in F \quad a = (a_i)_{i\in [0, n-1]} \; et \; b = (b_i)_{i\in [0, n-1]} \quad d(a,b) = \#\{ i : a_i\neq b_i \}

La notation #E désigne le cardinal de l'ensemble E.

Un cas important dans la pratique est celui des symboles binaires. Autrement dit A= {0,1}, On peut alors écrire, si ⊕ désigne le ou exclusif.

d(a,b) = \sum_{i=0}^{n-1} (a_i \oplus b_i)

Dans le cas, fréquent, où l'alphabet est un corps fini, F possède une structure d'espace vectoriel (En algèbre linéaire, un espace vectoriel est une structure algébrique permettant en pratique d'effectuer des combinaisons linéaires. Pour une introduction au concept de...) de dimension (Dans le sens commun, la notion de dimension renvoie à la taille ; les dimensions d'une pièce sont sa longueur, sa largeur et sa profondeur/son épaisseur, ou bien son diamètre si c'est une pièce de...) n. La distance dérive alors d'une pseudo-norme :

  • Soit K est un corps fini et F l'ensemble des suites de longueur n à valeur dans K. Le poids de Hamming p(a) d'un élément a de F est le cardinal de l'ensemble des images de a non nulles.

L'alphabet est souvent F2 le corps à deux éléments {0,1}. Le poids de Hamming est une pseudo-norme car :

 \forall a \in F \; \forall \lambda \in \mathbb K \quad p(\lambda .a) = p(a)

Néanmoins, si l'alphabet est un corps fini, alors la distance dérive du poids de Hamming, en effet:

 \forall a,b \in F \quad d(a,b) = p(b-a)

Exemples

Considérons les suites binaires suivantes :

a = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \end{pmatrix} \; et \; b = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix} \quad alors \quad d = 1 + 1 + 0 + 0 + 1 + 0 + 0 = 3

La distance entre a et b est égale à 3 car 3 bits diffèrent.

  • La distance de Hamming entre 1011101 et 1001001 est 2.
  • La distance de Hamming entre 2143896 et 2233796 est 3.
  • La distance de Hamming entre "ramer" et "cases" est 3.

Cas binaire

cube binaire de dimension trois
cube (En géométrie euclidienne, un cube est un prisme dont toutes les faces sont carrées. Les cubes figurent parmi les solides les plus remarquables de l'espace. C'est...) binaire de dimension trois
hyper-cube binaire de dimension quatre
hyper-cube binaire de dimension quatre

Un cas important est celui ou l'alphabet est le corps à deux éléments {0,1}. Une lettre est alors appelée bit. Il est largement utilisé en informatique (L´informatique - contraction d´information et automatique - est le domaine d'activité scientifique, technique et industriel en rapport avec le...) et en télécommunication.

Il est possible d'illustrer graphiquement le code et les distances entre les différents mot.

Le cas ou un mot comporte trois lettres est illustré sur la figure de gauche. La distance entre 010 et 111 est égale à deux car il est nécessaire de parcourir deux segments pour joindre les deux points. La distance pour joindre les points 100 et 011 est égale à trois.

La figure de droite illustre un hyper-cube binaire de dimension quatre. La distance entre 0110 et 1110 est égale à un, alors que la distance entre 0100 et 1001 est égal à trois.

Le poids de Hamming d'un élément a correspond à la distance entre le mot zéro n'ayant que des coordonnées nulles et a.

Propriété

Distance

La distance de Hamming est une distance au sens mathématique du terme :

\forall a,b\in F : d(a,b)=d(b,a) (symétrie)
\forall a,b\in F : d(a,b)=0\Leftrightarrow a=b (séparation)
\forall a,b,c\in F : d(a,c)\leq d(a,b)+d(b,c) (inégalité triangulaire)

La troisième propriété se démontre par une récurrence sur n.

Capacité de correction et distance minimale

La distance minimale δ est le minimum de distance entre deux mots du codes. Elle permet de déterminer le nombre maximal d'erreurs t corrigeables de manière certaine. La valeur de t est en effet celle du plus grand entier strictement inférieur à δ/2.

Si M désigne le nombre de mot du code, q le nombre de lettres de l'alphabet A de F et Vt le cardinal d'une boule fermée de rayon t, alors la majoration suivante est vérifiée:

M \leq \frac{q^n}{V_t}\quad avec \quad V_t=\sum_{i=0}^{t} {n \choose i}  (q-1)^i

Cette majoration porte le nom de Borne de Hamming.

Dans le cas d'un code linéaire (En mathématiques, plus précisément en théorie des codes, un code linéaire est un code correcteur.), et si k désigne la longueur des mots du codes, il existe une autre majoration, dite du borne du singleton :

n-k \le \delta - 1 \;

Applications

Somme de contrôle (Le mot contrôle peut avoir plusieurs sens. Il peut être employé comme synonyme d'examen, de vérification et de maîtrise.)

Données sur 7 bits avec bit de parité
0000000 00000000
1010001 11010001
1101001 01101001
1111111 11111111

La somme de contrôle est un exemple simple d'utilisation de la distance de Hamming. La distance minimale entre deux mots du code est égale à deux. En conséquence, si une unique erreur se produit elle est détectée. En revanche, elle n'est pas corrigeable sans retransmission. En effet, il existe a priori plusieurs mots de code à distance de un du message erroné.

L'exemple le plus simple est celui du bit de parité. Il correspond à une somme de contrôle dans le cas où le corps est binaire, c'est-à-dire qu'il contient deux éléments zéro et un.

Supposons que l'objectif soit la transmission de sept bits. Un bit de parité est défini comme étant égal à zéro si la somme des autres bits est paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) et à un dans le cas contraire. Les huit bits transmis sont d'abord le bit de parité puis les sept bits du message. Il correspond au bit de parité pair, c'est-à-dire la deuxième colonne du tableau (Tableau peut avoir plusieurs sens suivant le contexte employé :) de droite. Les messages envoyés sur huit bits ont toujours la parité zéro, ainsi si une erreur se produit, un zéro devient un un, ou l'inverse (En mathématiques, l'inverse d'un élément x d'un ensemble muni d'une loi de composition interne · notée multiplicativement, est un...); le recepteur sait qu'une altération a eu lieu. En effet la somme des bits devient impaire ce qui n'est pas possible sans erreur de transmission.

Code de Hamming

Le code de Hamming est un exemple un peu plus complexe que le précédent. La distance minimale entre deux mots du code est égale à trois. Si une unique altération se produit, alors le message reçu est à une distance de un d'un unique point du code. Il est ainsi possible de corriger automatiquement une erreur, si l'on sait que l'erreur est unique.

Code linéaire

Les codes linéaires forment une famille contenant les deux exemples précédents. L'alphabet est un corps fini, les ensembles E et F sont des espaces vectoriels et l'application φ est linéaire. La distance de Hamming dérive de la pseudo-norme : le poids de Hamming. Ce contexte (Le contexte d'un évènement inclut les circonstances et conditions qui l'entourent; le contexte d'un mot, d'une phrase ou d'un texte inclut les mots qui l'entourent. Le concept...) est très généralement celui qu'utilise l'industrie.

Code cyclique

Cette famille de codes correspond à un cas particulier de code linéaire. Les structures E et F sont enrichies d'une structure d'anneau leur conférant le statut d'algèbre (L'algèbre, mot d'origine arabe al-jabr (الجبر), est la branche des mathématiques qui étudie, d'une façon générale, les structures algébriques.). Cette structure, se fondant sur la théorie polynômes sur les extensions de corps finis permet de construire des distances minimales aussi élevées qu'on le souhaite.

De nombreux codes sont construits sur cette théorie. Le code de Hamming apparait comme un cas particulier de ceux là. On peut citer aussi les codes BCH ou les codes de Reed-Solomon utilisés par exemple pour les disques compacts.

Notes et références

Articles de Théorie des codes en rapport avec les codes correcteurs
Code correcteur | Code de répétition | Somme de contrôle | Distance de Hamming | Code parfait et code MDS | Code de Hamming | Code de Hamming (7,4) | Code linéaire | Matrice génératrice | Matrice de contrôle | Décodage par syndrome (Un syndrome est un ensemble de signes cliniques et de symptômes qu'un patient est susceptible de présenter lors de certaines maladies, ou bien dans des circonstances...) | Identité de Mac Williams | Code cyclique

Notes

  1. Richard Hamming error-detecting and error-correcting codes Bell (Bell Aircraft Corporation est un constructeur aéronautique américain fondé le 10 juillet 1935. Après avoir construit des avions de combat durant la Seconde Guerre mondiale, mais aussi le premier avion à avoir franchi le mur du son, l'entreprise...) System Technical (Un technical est un anglicisme désignant un véhicule de combat improvisé et typique d'une force militaire irrégulière locale.) Journal 29(2):147-160, 1950
Page générée en 0.172 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique