Qu'est-ce qu'un code de Hamming?
Un code de Hamming est une méthode de détection et de correction des erreurs dans une transmission binaire. Pour ce faire, il faut inclure dans la séquence des chiffres binaires supplémentaires utilisés pour la vérification, ainsi qu’un algorithme fournissant la logique de détection. Un tel code est capable de trouver deux erreurs dans n'importe quelle séquence de bits et de réparer un bit qui peut être incorrect. Le code de Hamming le plus couramment cité est le code de Hamming (7,4), où le nombre quatre indique le nombre initial de bits de départ et le sept représente le nombre total de bits de la séquence après inclusion des bits de contrôle supplémentaires.
La technique tire son nom de son créateur, Richard Hamming, qui a publié la méthode en 1950. Le code de Hamming fonctionne en prenant une chaîne de bits et en insérant des bits de contrôle supplémentaires, appelés bits de parité, dans la séquence. Les bits de contrôle sont toujours injectés à une position égale à deux, de sorte que tout nombre de bits peut être vérifié en incluant des bits de parité supplémentaires. Cela peut continuer jusqu'à ce que le dernier bit de parité ajouté à la séquence se trouve dans une position correspondant à une puissance de deux, inférieure ou égale à la position finale de la séquence.
Avec tous les bits de parité en place, les positions restantes sont les bits de données réels. Étant donné l'exemple de quatre bits, les positions de bits un, deux et quatre seraient les bits de parité, tandis que les positions trois, cinq, six et sept sont les données. Une fois que cette séquence a été établie, la logique du code de Hamming se met au travail.
Dans un code de Hamming, chacun des bits de parité ajoutés à la séquence permet de vérifier certaines des positions de bits dont ils sont proches, y compris eux-mêmes. Le bit de parité en position un vérifie toutes les positions de bits, qui sont essentiellement toutes les positions impaires de la séquence. Le second bit de parité, en position deux, vérifie les positions deux et trois, puis saute deux positions, vérifie deux autres positions, en saute deux autres, et ainsi de suite. S'il existe un bit de parité en position quatre, il agit de la même manière en ce sens qu'il vérifie les positions quatre à sept, puis ignore quatre positions, en vérifie quatre autres, et plus. Chaque bit de parité de la séquence continue de cette manière tout au long de la séquence.
Le processus par lequel un code de Hamming détecte et corrige une erreur consiste à additionner les bits de la séquence de contrôle pour chaque contrôle de parité, chacun d'eux devant donner un nombre pair. Dans l'exemple sept bits, pour le premier contrôle de parité, les bits un, trois, cinq et sept sont additionnés. Si le total est un nombre pair, la parité est vérifiée, mais si le total est impair, il y a une erreur. Puisque les contrôles de parité se chevauchent, deux erreurs de ce type apparaîtront. Lorsque les positions des bits à deux parités qui ne parviennent pas à obtenir des totaux égaux sont additionnées, cela indique le bit à corriger.
Dans l'exemple de code Hamming à sept bits, considérez que le bit à la position numéro cinq est incorrect. La somme des bits aux positions un, trois, cinq et sept apparaîtra sous la forme d'un nombre impair, de même que la somme des bits des positions quatre à sept. Cela indique que les contrôles de parité pour les bits de contrôle aux positions un et quatre ont échoué. Lorsque l'on additionne un et quatre, le total est cinq, ce qui correspond à la position du bit incorrect dans la transmission à corriger.