distance de Hamming

Placez les suites 101101 et 100001 l'une sous l'autre. Les chiffres coïncident aux première, deuxième, cinquième et sixième positions. Ils diffèrent aux troisième et quatrième positions. La distance de Hamming vaut donc 2.

Cette distance compte les emplacements modifiés, pas l'écart entre les nombres que les suites pourraient représenter. Si la première suite a été envoyée et la seconde reçue, le comptage signale deux bits différents.

La distance de Hamming compare deux mots de même longueur, c'est-à-dire deux suites comportant le même nombre de symboles. Elle compte les positions où les symboles correspondants sont distincts. Pour deux mots binaires nommés u et v, chacun de longueur n, sa définition est :

L'indice i désigne une position, et l'indicateur vaut 1 lorsque les deux bits y diffèrent, 0 sinon. Dans le cas binaire, effectuer le XOR bit à bit produit un 1 exactement aux positions différentes. La distance est donc le poids de Hamming de ce XOR, autrement dit son nombre de 1. La même définition s'applique à tout alphabet fini, sans XOR obligatoire.

Pour un code contenant au moins deux mots de code distincts, la distance minimale est la plus petite distance entre deux tels mots. Si elle vaut δ, le code peut détecter jusqu'à δ − 1 erreurs de symbole. Avec un décodage par plus proche voisin et au plus une réponse non ambiguë, il peut corriger jusqu'à ⌊(δ − 1)/2⌋ erreurs. Ces garanties concernent des mots de longueur fixe et des substitutions de symboles.

Un appareil envoie le mot binaire u = 101101. Le récepteur obtient le mot v = 100001. Le schéma aligne les six positions et met en évidence celles qui contribuent au comptage.

Données.
Mot envoyé : u = 101101.
Mot reçu : v = 100001.
Longueur commune : 6 bits.
Convention : les positions sont numérotées de 1 à 6, de gauche à droite.

Étape 1. Comparons les bits de même position. Les positions 1, 2, 5 et 6 coïncident. Les positions 3 et 4 diffèrent.

Étape 2. Le XOR place un 1 à chacune des deux positions différentes :

Étape 3. Le résultat 001100 contient exactement deux 1. Ainsi, d(u, v) = 2, soit deux bits différents.

Contrôle. En comptant directement les deux colonnes surlignées, on retrouve 2. La distance est aussi symétrique : comparer v à u donne le même résultat.

Lors d'une transmission numérique, on compare un mot reçu à des mots de code autorisés. Si l'on suppose des substitutions de bits et que la distance minimale du code est connue, la distance de Hamming donne une garantie de détection ou de correction.

Pour rapprocher des chaînes de longueur fixe, on compte les positions différentes. Si des insertions ou des suppressions doivent aussi être prises en compte, une distance d'édition est plus adaptée, car l'alignement peut changer.

En informatique, le poids de Hamming d'un masque binaire mesure le nombre de bits actifs. Le calcul revient à comparer ce masque au mot tout-zéro de même longueur.

Distance de Hamming et poids de Hamming. La première compare deux mots de même longueur ; le second compte les symboles non nuls d'un seul mot. Pour 001100, le poids vaut 2, tandis que sa distance à 111100 vaut aussi 2 pour une autre raison : deux positions diffèrent.

Distance de Hamming et code de Hamming. La distance est une mesure applicable à de nombreux mots et codes. Un code de Hamming est une famille particulière de codes correcteurs. Le mot 101101 peut donc être comparé par distance de Hamming sans appartenir à un code de Hamming.

Distance de Hamming et distance d'édition. La distance de Hamming compte seulement les substitutions à positions fixées. Une insertion dans 101101 change la longueur : la distance d'édition peut la compter, tandis que la distance de Hamming n'est alors pas définie.

Longueurs différentes. Si deux mots n'ont pas le même nombre de symboles, leurs positions ne se correspondent pas toutes. La distance de Hamming usuelle n'est pas définie ; il faut choisir un alignement et une autre mesure adaptée.

Distance nulle. Une valeur 0 signifie que les deux mots sont identiques position par position. Elle ne prouve pas qu'aucune erreur physique n'a eu lieu : deux altérations successives peuvent s'annuler avant l'observation.

Altération et différence observée. Deux bits différents ne sont deux erreurs de transmission que si l'un des mots est bien la référence envoyée et si le canal ne fait que substituer des bits. Sinon, le calcul mesure une dissemblance, sans en donner la cause.

Capacité d'un code. Une distance minimale δ ne garantit pas la correction de δ − 1 erreurs. Elle garantit leur détection ; la correction non ambiguë est limitée à ⌊(δ − 1)/2⌋ erreurs. Par exemple, δ = 3 permet de détecter 2 erreurs mais d'en corriger 1.

Le code de Hamming montre comment une distance minimale bien choisie devient une procédure concrète de détection et de correction.

L'article Codes correcteurs : garder les erreurs à distance replace cette mesure dans la construction de codes qui séparent suffisamment leurs mots.

Le problème de Berlekamp ouvre sur un problème de recherche où la distance de Hamming structure l'espace des possibilités.