Comment fonctionne le code Hamming?

Lors de la transmission de données, le code de Hamming apparemment vous permet de recréer de données qui a été endommagé sur le fil (un code correcteur d'erreur).

Comment cela fonctionne et quelles sont ses limitations, le cas échéant?

Y a de meilleures solutions pour la correction d'erreur (par opposition à la retransmission)? Existe-il des circonstances où la retransmission est mieux?

source d'informationauteur paxdiablo

  1. 35

    Nous allons essayer d'expliquer un peu:

    Nous avons 3 nombre de bits. Les possibilités qui peut être présenté comme un cube dans lequel chaque bit représente un axe. Les huit possibilités sont sur les coins.

    000 --------001
 | \         | \
 | 100---------101
 |  |        |  |
 |  |        |  |
010- | -------011 |
   \|          \|
   110---------111

    Chaque défaut (par exemple 101 est lu comme 100) entraîne un déplacement sur une ligne sur le cube.

    Si nous utilisons deux bits pour les données et la troisième pour un contrôle de parité (dire par exemple même de la parité). Nous perdre 4 points de données. Mais elle a l'avantage de pouvoir détecter un seul bit d'échec (ce qui le transforme en un même nombre de 1 dans un nombre impair d'unités).
    Les nombres impairs sont marqués avec un *. Et nous voyons que chaque odd (à tort transmis) mot est acculé par le même (à juste titre transmis) mots. Donc, si nous recevons 100, on peut être sûr que c'est faux.

    Mais (avec un seul échec de bit) la représentation correcte aurait été 000, 101 et 110. On peut donc détecter quelque chose de mal, mais nous ne pouvons pas détecter ce qui ne va pas:

     000 -------*001
  | \         | \
  |*100---------101
  |  |        |  |
  |  |        |  |
*010- | -------011 |
    \|          \|
    110--------*111

    Cela s'appelle un bit d'erreur de détection de code.

    Si l'on utilise un autre bit de vérifier et de supprimer ainsi l'un pour les données. Nous nous retrouvons avec 1 databit et 2 "vérifier bits".
    Dans ce cas, permet de supposer 000 et 111 sont valables à la représentation des données et les six autres ne le sont pas. Maintenant, nous avons une situation intéressante si un bit est de déformation pendant le transport.
    Si nous envoyons 000 et recevoir 010, nous voyons que 010 a un valide voisin (000) et deux non valide (110 et 011). Alors maintenant, nous savons que nous avons l'intention d'envoyer des 000 et sont en mesure de rectifier:

     000 -------*001
  | \         | \
  |*100--------*101
  |  |        |  |
  |  |        |  |
*010- | ------*011 |
    \|          \|
   *110---------111

    Cela s'appelle un bit de code de correction des erreurs.

    Veuillez noter qu'un bit de code correcteur d'erreur est également l'un des deux bits d'erreur de détection de code.

    Et plus généralement.

    Si vous avez n vérifier bits, vous avez un n de bits d'erreur de détection de code.
    Si vous avez 2n vérifier bits, vous avez un n de bits de correction d'erreur de code.

    De sûr, vous devriez ordre de la "validité" des codes de sorte qu'ils ne sont pas de frontière sur l'autre.

  2. 12

    Voici ce qui est vraiment aperçu de haut niveau.

    Suppose that every time I send a message, I send thrie copies of the text.
Suppose that every time I send z message, I send three copies of the teyt.
Suppose that every tyme I send a message, I send three copies if the tezt.

    Par la comparaison des caractères et de prendre un vote à la majorité simple dans chaque position, vous pouvez corriger unique des caractères erronés. Cependant, le coût de ce régime (quantité de données qui doivent être envoyées) est élevée, et il ne l'attrape pas, peu probable, mais possible en cas de deux erreurs dans les positions correspondantes des différentes copies (comme dans le dernier mot de l'exemple ci-dessus).

    Codes de Hamming (et d'autres types de codes de correction d'erreur, tels que Reed-Solomon) sont basées sur les formules de calcul les données supplémentaires (plutôt que de la simple duplication). L'ajout de bits dépend des combinaisons de bits de données dans une manière que les erreurs dans la copie de rendre détectable des modèles de changements lorsque le calcul est répété à la fin de réception.

    Par souci d'illustration, nous allons commencer avec de simples parité impaire, l'ajout d'un seul bit pour vous assurer que le nombre total de bits dans un message est impair. De sorte que le message 10110110 devient 101101100 (cinq 1s, pas de supplément de 1 nécessaire) et le message 10010110 devient 100101101 (quatre 1s, 1 nécessaire). Si vous recevez un message de 101101101 et de voir qu'il y a six 1s, vous savez qu'il y a une erreur, mais ne sais pas où. Supposons que nous ajoutons plus de bits de parité, de chacun sur la fonction que sur un partie du message, comme illustré ci-dessous en le copiant les bits considéré et en utilisant le " - " pour bits ignoré:

    10110110
1-1-0-1- => 0
-0-1-1-0 =>  1
10--01-- =>   1
--11--10 =>    0
1011---- =>     0
----0110 =>      1

    donc le message complet est 10110110011001. Maintenant, supposons qu'une erreur de transmission des changements de la troisième bit dans le message, de sorte qu'il est 10010110011001. Lorsque le récepteur re-exécute la vérification des erreurs de calcul, il ne parvient pas à égaler:

    10010110
1-0-0-1- => 1*
-0-1-1-0 =>  1
10--01-- =>   1
--01--10 =>    1*
1001---- =>     1*
----0110 =>      1

    et la vérification de bits qui ne correspondent pas aux sont exactement ceux touchés par le tiers de bits de données. C'est pas un véritable, solide à correction d'erreur système; c'est juste un croquis pour illustrer comment créer de la redondance peut aider à identifier la nature exacte de l'erreur.

  3. 5

    Vous trouverez des détails sur la façon dont il fonctionne ici

    Des informations plus générales sur l'Erreur Corecting Codes est disponible ici

  4. 3

    Informations sur le code de Hamming est disponible ici et ici.

    Que pour la pertinence , cette explique pourquoi :

    1. Codes de correction d'erreur comme de Hamming sont adaptés pour les canaux simplex où aucun retransmission peuvent être demandées.

    2. De détection des erreurs en plus de la retransmission est souvent préféré car il est plus efficace.

    À des fins de comparaison, considérons un canal avec des taux d'erreur par bit. Laissez-bloc d'une taille de 1000 bits.

    Pour corriger une erreur (par code de Hamming), 10 enregistrement de bits par bloc sont nécessaires. Pour transmettre 1000 blocs de 10 000 vérifier bits (frais généraux) sont nécessaires.
    Pour détecter une seule erreur, un seul bit de parité par bloc suffira. Pour transmettre 1000 blocs, un seul exter bloc (en raison du taux d'erreur par bit) devra être retransmis, en donnant les frais généraux de seulement 2001 (=+de 1000 1001) bits.

  5. 0

    De Hamming code mathématique est un truc pour corriger jusqu'à 4 perdu bits dans une transmission en série. Il est également utilisé en faveur de la "bit de parité" moderne des puces de mémoire.

    Limitations dans le nombre de bits qui peuvent être restaurée, ce qui n'est pas plus de 4. Si plus de 4 bits sont perdus, la retransmission est nécessaire.

    Différentes situations qui nécessitent différentes techniques de correction des erreurs. Certaines de ces techniques sont répertoriés dans les autres posts ici.

  6. 0

    @GameCat et ce sur les 2 bits d'erreur de détection de code.

    Dans ce cas, disons 111 a changé à 100. Alors nous pouvons être sûr qu'il y a 2 bits de mal et nous le savons parce que la distance entre 111 et 100 est de 2 bits, et la distance de 000 et 100 est de 1 bit. Donc, si nous savons qu'il y a erreur sur 2 bits, on peut être sûr qu'elle est la bonne valeur.