Comment corriger un message en utilisant le code Hamming

Question

Je veux travailler sur ce projet d'été pour corriger des erreurs dans une transmission de message en utilisant le code Hamming, mais je ne peux pas comprendre comment cela fonctionne vraiment. J'ai lu de nombreux articles en ligne, mais je ne comprends pas vraiment l'algorithme. Quelqu'un peut-il expliquer en termes simples?

Merci.

Answer 1

Il est tout au sujet de distance de Hamming .

La distance de Hamming entre deux valeurs de base 2 est le nombre de bits à laquelle ils diffèrent. Donc, si vous transmettez A, mais que je reçois B, le nombre de bits qui doit avoir été commuté dans la transmission est la distance de Hamming entre A et B.

codes de Hamming sont utiles lorsque les bits de chaque mot de code sont transmises en quelque sorte séparément. Nous ne nous soucions pas s'ils sont en série ou parallèle, mais ils ne sont pas, par exemple, combinés en une valeur analogique représentant plusieurs bits, ou compressé / crypté après l'encodage.

Ainsi, chaque bit est indépendamment (au hasard avec une probabilité fixe), soit reçu correctement, ou retournée. En supposant que la transmission est assez fiable, la plupart des bits sont reçus correctement. Ainsi, les erreurs dans un petit nombre de bits sont des erreurs plus susceptibles, et simultanément dans un grand nombre de bits sont peu probables.

Ainsi, un code de Hamming vise généralement à corriger les erreurs 1 bit, et / ou pour détecter les erreurs de 2 bits (voir l'article de Wikipedia pour les détails des deux types principaux). Codes qui corrigent / détecter plus grandes erreurs peuvent être construites, mais AFAIK ne sont pas utilisés autant.

Le code fonctionne en espaçant uniformément les points de code dans « l'espace de Hamming », qui, en termes mathématiques est l'espace métrique constitué de toutes les valeurs de la taille de mot correspondant, avec une distance de Hamming en tant que métrique. Imaginez que chaque point de code est entouré d'une petite « zone tampon » de valeurs non valides. Si une valeur est reçue et non un point de code, une erreur doit se produire, parce que les points de code valides sont jamais transmis.

Si la réception d'une valeur dans la zone tampon, puis sur l'hypothèse qu'une erreur de 1 bit est survenue , la valeur qui a été transmise doit être la distance 1 de la valeur reçue. Mais parce que les points de code sont répartis, il n'y a qu'un seul point de code qui ferment. Il est donc « corrigé » à ce point de code, pour des raisons qu'une erreur de 1 bit est plus probable que la plus grande erreur qui serait nécessaire pour tout autre point de code pour produire la valeur reçue. En termes de probabilité, la probabilité conditionnelle que vous avez envoyé le point de code à proximité est supérieure à la probabilité conditionnelle que vous envoyez un autre point de code, étant donné que je reçu la valeur que je l'ai fait. Donc je suppose que vous avez envoyé l'un à proximité, avec une certaine confiance basée sur la fiabilité de la transmission et le nombre de bits dans chaque mot.

Si une valeur non valide est reçue qui est à égale distance de deux points de code, alors je ne peux pas dire que l'on est plus susceptible d'être la vraie valeur que l'autre. Donc, je perçois l'erreur, mais je ne peux pas corriger.

Il est évident que les erreurs de 3 bits ne sont pas corrigées par un code SECDED Hamming. La valeur reçue est plus loin de la valeur que vous avez effectivement envoyé, que d'un autre point de code, et je tort « corriger » à la valeur erronée. Donc, vous avez besoin soit une transmission assez fiable que vous ne se soucient pas eux, ou bien vous avez besoin de détection d'erreur de niveau supérieur ainsi (par exemple, un CRC sur un message entier).

Answer 2

Plus précisément de Wikipedia , l'algorithme est le suivant:

1. Numéro de bits à partir de 1: bit 1, 2, 3, 4, 5, etc
.
2. Ecrire les numéros de bits en binaire. 1, 10, 11, 100, 101, etc.
3. Toutes les positions de bit qui sont des puissances de deux (avoir un seul bit 1 sous la forme binaire de leur position) sont des bits de parité.
4. Toutes les autres positions de bit, avec deux ou plusieurs bits dans une forme binaire de leur position, sont des bits de données.
5. Chaque bit de données est inclus dans un ensemble unique de 2 ou plusieurs bits de parité, telle que déterminée par la forme binaire de sa position de bit.
   1. Parité bit 1 couvre toutes les positions binaires qui ont le moins de jeu de bit de poids faible: bit 1 (bit de parité lui-même), 3, 5, 7, 9, etc
   .
   2. Parité bit 2 couvre l'ensemble des positions de bits ayant le second ensemble de bits de poids faible: bit 2 (bit de parité lui-même), 3, 6, 7, 10, 11, etc
   .
   3. Parité bit 4 couvre toutes les positions binaires qui ont le bit le moins significatif troisième:. Les bits 4-7, 12-15, 20-23, etc.
   4. 8 Bit de parité couvre toutes les positions binaires qui ont le quatrième bit le moins significatif ensemble:. Les bits 8-15, 24-31, 40-47, etc.
   5. En général, chaque bit de parité couvre tous les bits où le binaire et de la situation de parité et la position de bit est non nul.

Answer 3

Le wikipedia article explique tout à fait bien.

Si vous ne comprenez pas un aspect spécifique de l'algorithme, alors vous aurez besoin de reformuler (ou de détail) votre question, de sorte que quelqu'un peut répondre à votre partie spécifique du problème.