Qu’est-ce que la distance de Hamming ?

Distance de Hamming

La distance de Hamming est une métrique permettant de comparer deux chaînes de données binaires. En comparant deux chaînes binaires de longueur égale, la distance de Hamming est le nombre de positions de bits dans lesquelles les deux bits sont différents.

La distance de Hamming entre deux chaînes, a et b est notée d(a,b).

Elle est utilisée pour la détection ou la correction des erreurs lorsque les données sont transmises sur des réseaux informatiques. Il est également utilisé dans la théorie du codage pour comparer des mots de données de longueur égale.

Calcul de la distance de Hamming

Pour calculer la distance de Hamming entre deux chaînes, et , on effectue leur opération XOR, (a⊕ b), puis on compte le nombre total de 1 dans la chaîne résultante.

Exemple

Supposons qu’il existe deux chaînes de caractères 1101 1001 et 1001 1101.

11011001 ⊕ 10011101 = 01000100. Puisque, ceci contient deux 1, la distance de Hamming, d(11011001, 10011101) = 2.

Distance de Hamming minimale

Dans un ensemble de chaînes de longueurs égales, la distance de Hamming minimale est la plus petite distance de Hamming entre toutes les paires possibles de chaînes dans cet ensemble.

Exemple

Supposons qu’il y ait quatre chaînes 010, 011, 101 et 111.