Distance de Hamming

La distance de Hamming entre deux mots de même longueur $ n $ est le nombre de positions pour lesquelles les symboles correspondants diffèrent. Elle mesure la dissimilarité entre deux mots.

Formellement, pour deux mots $ x = (x_1, \dots, x_n) $ et $ y = (y_1, \dots, y_n) $, la distance de Hamming est : $$ \operatorname{Hamming}(x,y) = \sum_{i=1}^{n} \mathbf{1}_{x_i \neq y_i} $$

Pour calculer la distance de Hamming entre deux nombres binaires de même longueur : comparer les bits position par position et compter le nombre de positions où les bits diffèrent.

La distance de Hamming généralisée peut s'appliquer à toute chaine de caractères. Elle compte le nombre de positions où les symboles diffèrent.

La distance de Hamming sert à mesurer à quel point deux mots de même longueur sont différents. Elle est utilisée pour :

— comparer deux chaînes de caractères ou suites de symboles

— quantifier une erreur entre une donnée attendue et une donnée observée

— mesurer la similarité entre deux objets discrets

Plus la distance est faible, plus les deux mots sont similaires. Si la distance est nulle, les deux mots sont identiques.

Plusieurs codes sont basés sur la distance de Hamming comme le code de Hamming (7,4) : 4 bits de données, 3 bits de parité ou le code de Hamming étendu (8,4) : 4 bits de données, 4 bits de parité