Distance de Hamming
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 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 très important en théorie algébrique des codes correcteurs. Elle permet de quantifier la différence entre deux séquences de symboles.
Si on pose a = a0...an − 1 et b = b0...bn − 1, où les ai et bi sont des symboles appartenant à un ensemble A, la distance de Hamming se définit formellement par : 
la notation 
désignant le cardinal de l'ensemble E.
Sommaire |
[modifier] Cas binaire
Le cas le plus important dans la pratique, également le plus simple, est celui des symboles binaires. Autrement dit A = {0,1}. On peut alors écrire 
où 
est le ou exclusif et 
désigne une somme dans 
.
[modifier] Propriétés
La distance de Hamming est une distance au sens mathématique du terme :
- elle est symétrique, d(a,b) = d(b,a);
- elle sépare les éléments,
; - elle vérifie l'inégalité triangulaire,
.
[modifier] Exemple
Prenons les séquences binaires suivantes :
d = 1 + 1 + 0 + 0 + 1 + 0 + 0 = 3
La distance entre a et b vaut : 3 car il y a 3 bits qui diffèrent.
[modifier] La métrique
La métrique est intimement liée à la distance de Hamming. Elle définit la loi d'évolution de la distance de Hamming bit après bit.
En prenant l'exemple ci-dessus, la métrique vaudra elle aussi 3 au final. Voici son évolution.
La métrique et la distance de Hamming sont toujours positives et ne peuvent que croître.
