Distance de Hamming
111646
30691070
2008-06-16T10:29:35Z
Thijs!bot
105469
robot Ajoute: [[ro:Distanţă 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 des [[code correcteur|codes correcteurs]]. Elle permet de quantifier la différence entre deux séquences de symboles.
La '''distance de Hamming''' est une [[distance (mathématiques)|distance]] au sens [[Mathématiques|mathématique]] du terme. À deux suites de symboles de même longueur, elle associe l'[[entier naturel|entier]] désignant le [[Nombre cardinal|cardinal]] de l'ensemble des symboles de la première suite qui différent de la deuxième.
Le '''poids de Hamming''' correspond au nombre d'éléments différents de zéro dans une chaine d'éléments d'un [[corps fini]].
==Intérêt du concept==
===Histoire et domaine d'applications===
{{Article détaillé|Théorie des codes}}
La '''distance de Hamming''' doit son nom à [[Richard Hamming]] <small>([[1915 en science|1915]] [[1998 en science|1998]])</small>. Elle est décrite dans un article<ref>[[Richard Hamming]] ''error-detecting and error-correcting codes'' Bell System Technical Journal 29(2):147-160, [[1950 en science|1950]]</ref> fondateur pour la [[théorie des codes]]. Elle est utilisée en [[télécommunication]] pour compter le nombre de [[bit]]s altérés dans la transmission d'un message d'une longueur donnée. 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]]. 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===
{{Article détaillé|Code correcteur}}
[[Image:Code correcteur.jpg|thumb|rigth|550px|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 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 subit, lors de sa transmission, une altération, un nouveau message en rouge 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 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 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 :
<center><math>\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 \} </math> </center>
La notation #''E'' désigne le [[Nombre cardinal|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|ou exclusif]].
<center><math>d(a,b) = \sum_{i=0}^{n-1} (a_i \oplus b_i)</math></center>
Dans le cas, fréquent, où l'alphabet est un [[corps fini]], ''F'' possède une structure d'[[espace vectoriel]] de dimension ''n''. La distance dérive alors d'une [[Norme (mathématiques)|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 ''F''<sub>2</sub> le corps à deux éléments {0,1}. Le poids de Hamming est une pseudo-norme car :
<center><math> \forall a \in F \; \forall \lambda \in \mathbb K \quad p(\lambda .a) = p(a)</math></center>
Néanmoins, si l'alphabet est un corps fini, alors la distance dérive du poids de Hamming, en effet:
<center><math> \forall a,b \in F \quad d(a,b) = p(b-a)</math></center>
===Exemples===
Considérons les suites binaires suivantes :
<center><math>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 </math></center>
La distance entre ''a'' et ''b'' est égale à '''3''' car 3 [[Bit (informatique)|bits]] diffèrent.
* La distance de Hamming entre '''10<font color=blue>1</font>1<font color=blue>1</font>01''' et '''10<font color=red>0</font>1<font color=red>0</font>01''' est 2.
* La distance de Hamming entre '''2<font color=blue>14</font>3<font color=blue>8</font>96''' et '''2<font color=red>23</font>3<font color=red>7</font>96''' est 3.
* La distance de Hamming entre "'''<font color=blue>r</font>a<font color=blue>m</font>e<font color=blue>r</font>'''" et "'''<font color=red>c</font>a<font color=red>s</font>e<font color=red>s</font>'''" est 3.
===Cas binaire===
[[Image:Hamming distance 3 bit binary example.svg|left|thumb|220px|[[cube]] binaire de dimension trois]]
[[Image:Hamming distance 4 bit binary example.svg|rigth|thumb|300px|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 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 '''<font color=blue>010</font>''' et '''<font color=blue>111</font>''' est égale à deux car il est nécessaire de parcourir deux segments pour joindre les deux points. La distance pour joindre les points '''<font color=red>100</font>''' et '''<font color=red>011</font>''' est égale à trois.
La figure de droite illustre un ''hyper''-[[cube]] binaire de dimension quatre. La distance entre '''<font color=blue>0110</font>''' et '''<font color=blue>1110</font>''' est égale à un, alors que la distance entre '''<font color=red>0100</font>''' et '''<font color=red>1001</font>''' 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 (mathématiques)|distance]] au sens mathématique du terme :
{| border="0" align="center"
|-----
| <math>\forall a,b\in F : d(a,b)=d(b,a)</math>
| '''(symétrie)'''
|-----
| <math>\forall a,b\in F : d(a,b)=0\Leftrightarrow a=b</math>
| '''(séparation)'''
|-----
| <math>\forall a,b,c\in F : d(a,c)\leq d(a,b)+d(b,c)</math>
| '''(inégalité triangulaire)'''
|}
La troisième propriété se démontre par une [[Raisonnement par récurrence|récurrence]] sur ''n''.
===Capacité de correction et distance minimale===
{{Article détaillé|Borne de Hamming}}
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 ''V''<sub>t</sub> le cardinal d'une boule fermée de rayon ''t'', alors la majoration suivante est vérifiée:
<center><math>M \leq \frac{q^n}{V_t}\quad avec \quad V_t=\sum_{i=0}^{t} {n \choose i} (q-1)^i</math></center>
Cette majoration porte le nom de '''Borne de Hamming'''.
Dans le cas d'un [[code linéaire]], et si ''k'' désigne la longueur des mots du codes, il existe une autre majoration, dite du ''' borne du singleton''' :
<center><math>n-k \le \delta - 1 \;</math></center>
==Applications==
===Somme de contrôle===
{{Article détaillé|Somme de contrôle}}
{| align="right" class="wikitable"
!Données sur 7 bits
!avec bit de parité
|-
| 0000000
| '''0'''0000000
|-
| 1010001
| '''1'''1010001
|-
| 1101001
| '''0'''1101001
|-
| 1111111
| '''1'''1111111
|}
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 [[bit]]s. Un bit de parité est défini comme étant égal à ''zéro'' si la somme des autres bits est paire 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 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; 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===
{{Article détaillé|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===
{{Article détaillé|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 est très généralement celui qu'utilise l'industrie.
===Code cyclique===
{{Article détaillé|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 sur un corps|algèbre]]. 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 [[Code BCH|codes BCH]] ou les [[Code de Reed-Solomon|codes de Reed-Solomon]] utilisés par exemple pour les [[disque compact|disques compacts]].
==Notes et références==
{{Code correcteur}}
===Notes===
<references />
===Liens externes===
* {{fr}} [http://zanotti.univ-tln.fr/enseignement/divers/chapter3.html Code correcteur C.I.R.C] par J.P. Zanotti
* {{fr}} [http://www.univ-lille1.fr/bustl-grisemine/pdf/articles/A1998-14.pdf L'algèbre et la correction des erreurs] par Dany-Jack Mercier Université Antilles-Guyane
* {{fr}} [http://www.math.u-bordeaux.fr/~zemor/codes06.pdf Code Linéaire] Université de Bordeaux
* {{fr}} [http://www.ufr-mi.u-bordeaux.fr/CSI/Cours/code.pdf Cours de code] par Christine Bachoc Université de Bordeaux
* {{fr}} [http://agreg-maths.univ-rennes1.fr/documentation/docs/codes.pdf Code correcteur] par M. Coste, A. Paugam, R. Quarez Université de Lille
===Références===
* FJ MacWilliams & JJA ''Sloane The Theory of Error-Correcting Codes'' North-Holland, 1977
* A Spataru ''Fondements de la Théorie de l'Information'' Presses Polytechniques Romandes, 1991
* M. Demazure ''Cours d'algèbre'' Cassini, 1997
* B. Martin - "[http://www.techno-science.net/?onglet=ouvrages&ID=2880745691 Codage, cryptologie et applications]" - <small>(éd. Presses Polytechniques et Universitaires Romandes (PPUR), 2004) - 354 p. </small>- ISBN 978-2880745691
* J.-G. Dumas, J.-L. Roch, E. Tannier et S. Varrette - "[http://www.dunod.com/pages/ouvrages/ficheouvrage.asp?id=50692 Théorie des codes (Compression, cryptage, correction)]" - <small>(éd [[Dunod]], 2007) - 352 p.</small> - ISBN 978-2100506927
{{Navigation algorithmes textes}}
{{Portail|mathématiques|informatique|sécurité informatique}}
[[Catégorie:Distance remarquable]]
[[Catégorie:Détection et correction d'erreur]]
[[Catégorie:codage des télécommunications]]
[[af:Hammingafstand]]
[[ca:Distància de Hamming]]
[[cs:Hammingova vzdálenost]]
[[de:Hamming-Abstand]]
[[en:Hamming distance]]
[[es:Distancia de Hamming]]
[[fi:Hammingin etäisyys]]
[[he:מרחק המינג]]
[[hr:Hammingova udaljenost]]
[[hu:Hamming-távolság]]
[[it:Distanza di Hamming]]
[[ja:ハミング距離]]
[[ko:해밍 거리]]
[[nl:Hammingafstand]]
[[pl:Odległość Hamminga]]
[[ro:Distanţă Hamming]]
[[ru:Расстояние Хэмминга]]
[[vi:Khoảng cách Hamming]]
[[zh:汉明距离]]