Distance de Hamming

La distance de Hamming est une notion mathématique développée par Richard Hamming dont le domaine d’utilisation est plutôt en informatique et en télécommunication. Cette notion a pour but de calculer la différence entre deux chaînes de symboles ayant la même taille. Pour donner un exemple concret, considérons deux vecteurs de 4 bits représentant les chiffres 3 et 0 respectivement (0011 et 0000). Comme on peut le constater, le nombre de bits qui diffère entre ces deux vecteurs est de 2.

En informatique, la distance de Hamming est utilisée en théorie de codes correcteurs qui permettent l’envoie des données d’une façon sûre par les voies de communications qui ne sont pas toujours fiables. Pour déterminer le niveau de fiabilité d’un canal de communication, on peut utiliser la distance de Hamming.   Pour le faire, on envoie un mot binaire de l’émetteur au récepteur puis on calcule la distance de Hamming entre le mot d’origine et le mot reçu. De cette façon, le résultat nous montre combien de bits du mot reçu sont erronés par le bruit ou d’autres facteurs influençant la qualité de service dans le réseau de communication.  

Il y a plusieurs algorithmes proposés pour réaliser la distance de Hamming. Le premier algorithme en programmation est de parcourir les deux vecteurs binaires donnés et de comparer les bits ayant le même indice dans les vecteurs et de compter le nombre de bits différents. Le problème de cet algorithme est sa complexité élevée qui augmente le temps de la compilation du programme et le nombre de ressources utilisées dans le cas de la conception d’un module numérique. Une autre solution peut être l’utilisation du port logique XOR. Dans ce cas, comme la solution précédente, il faut comparer bit à bit les deux vecteurs et faire l’opération XOR sur les deux bits ayant le même indice pour déterminer la différence entre les deux vecteurs. Cette solution diminue le nombre de ressources utilisées tout en augmentant le temps de compilation. L’autre problème de cette solution est que l’opération logique XOR n’est pas directement faisable dans certains langages de programmation.

J’ai trouvé une solution pour les chiffres positifs qui ne parcourt qu’un seul vecteur et exige moins de ressources d’après le synthétiseur du logiciel Active-HDL utilisé pour la conception des systèmes numériques. Cette solution, telle qu’elle est illustrée dans la figure ci-dessous, est codée en langage de programmation VHDL.

La fonction trouverDistanceHamming contenant ma solution consiste d’abord de convertir les deux vecteurs binaires en valeurs décimales puis de trouver la différence de ces deux valeurs et la mettre dans la variable diff qui est de type integer. Ensuite, on fait la conversion explicite de la valeur diff en appelant la fonction to_unsigned (). Le résultat de cette conversion est mis dans la variable uDiff qui est du même type et de la même taille que les deux vecteurs donnés. Puis dans une boucle for, on parcourt le vecteur uDiff et à chaque itération, on incrémente la variable cpt lorsqu’on rencontre un bit ‘1’. Le nombre de bits ‘1’ existant dans le vecteur uDiff représente la distance de Hamming entre les deux vecteurs d’entrée.

Il est possible de coder cette solution dans d’autre langage de programmation.