Qu'est-ce que Distance de Hamming ?
Nombre de positions où deux suites de bits (ou chaînes de caractères) de même longueur diffèrent. Elle est égale au nombre de 1 dans le OU exclusif des deux suites de bits. Par exemple, la distance de Hamming entre 1011010 et 0110011 vaut 4. La plus petite distance entre deux mots de code d'un code est sa distance de Hamming minimale ; un code de distance de Hamming minimale d peut détecter les erreurs jusqu'à d − 1 bits et corriger les erreurs jusqu'à (d − 1) ÷ 2 bits, arrondi à l'entier inférieur.
Nom japonais: ハミング距離
« Distance de Hamming » apparaît dans 3 questions d'entraînement réparties sur 1 thèmes, dont Bases de la théorie de l'information et du codage.
Domaine: Bases de la théorie de l'information et du codage
Capacité de détection et de correction des erreurs
Plus les mots de code sont éloignés, moins une erreur risque de transformer l'un en un autre. Dans un code de distance de Hamming minimale d, une erreur de d − 1 bits ou moins ne peut pas produire un autre mot de code et peut donc être détectée, et si l'erreur porte sur au plus (d − 1) ÷ 2 bits, le mot de code le plus proche du mot reçu est l'original : elle peut donc être corrigée. Par exemple, le code à répétition qui envoie chaque bit trois fois a d = 3 et corrige une erreur de 1 bit par vote majoritaire.
Questions fréquentes
La distance de Hamming et le code de Hamming sont-ils la même chose ?
Non. La distance de Hamming est une mesure qui compte les différences entre deux suites de bits, tandis qu'un code de Hamming est un code construit pour avoir une distance de Hamming minimale de 3, capable de corriger une erreur de 1 bit. Les deux portent le nom de Hamming.
Peut-on calculer la distance de Hamming entre des suites de bits de longueurs différentes ?
La distance de Hamming n'est définie qu'entre des suites de même longueur. Pour compter les différences en incluant les caractères insérés et supprimés, on utilise la distance d'édition (distance de Levenshtein).