Distance de Hamming

La distance de Hamming est une notion mathématique, définie par Richard Hamming, et utilisée en informatique, en traitement du signal et dans les télécommunications. Elle joue un rôle important en théorie algébrique des codes correcteurs. Elle permet de quantifier la différence entre deux séquences de symboles. C'est une distance au sens mathématique du terme. À deux suites de symboles de même longueur, elle associe le nombre de positions où les deux suites diffèrent. Le poids de Hamming correspond au nombre d'éléments différents de zéro dans une chaîne d'éléments d'un corps fini. Théorie des codes La distance de Hamming doit son nom à Richard Hamming (1915-1998). Elle est décrite dans un article fondateur pour la théorie des codes. Elle est utilisée en télécommunication pour compter le nombre de bits altérés dans la transmission d'un message d'une longueur donnée. Le poids de Hamming correspond au nombre de bits différents de zéro, il est utilisé dans plusieurs disciplines comme la théorie de l'information, la théorie des codes et la cryptographie. Néanmoins, pour comparer des séquences de longueurs variables, ou des chaines de caractères pouvant subir non seulement des substitutions, mais aussi des insertions ou des effacements, des métriques plus sophistiquées comme la distance de Levenshtein sont plus adaptées. Code correcteur Les codes correcteurs ont leurs sources dans un problème de la transmission de données. Parfois, une transmission de données se fait en utilisant une voie de communication non entièrement fiable. L'objectif d'un code correcteur est l'apport d'une redondance de l'information de telle manière que l'erreur puisse être détectée, voire corrigée. Un message est un élément d'un ensemble E constitué de suites finies de lettres choisies dans un alphabet A. L'apport de la redondance est le résultat d'une application injective φ de E dans un ensemble F constitué aussi de suite finies de lettres d'un alphabet A'. Les suites de l'ensemble F sont choisies a priori plus longues que celle de E.