Wie eine Nachricht korrigieren mit Hamming-Code

Question

So mag ich in diesem Sommer Projekt arbeiten Fehler in einer Nachrichtenübertragung zu korrigieren unter Verwendung von Hamming-Code, aber ich kann nicht herausfinden, wie es wirklich funktioniert. Ich habe viele Online-Artikel zu lesen, aber ich verstehe nicht wirklich den Algorithmus. Kann jemand es in einfachen Worten erklären?

Danke.

Answer 1

Es ist alles über Hammingdistanz .

Der Hamming-Abstand zwischen zwei Basis-2-Werten ist die Anzahl der Bits, bei denen sie sich unterscheiden. Wenn Sie also einen übertragen, aber ich erhalte B, dann ist die Anzahl von Bits, die bei der Übertragung eingeschaltet sein muss ist die Hamming-Distanz zwischen A und B.

Hamming-Codes sind nützlich, wenn die Bits in jedem Codewort irgendwie separat übertragen werden. Wir interessieren uns nicht, ob sie seriell oder parallel, aber sie sind nicht zum Beispiel in einen analogen Wert kombiniert mehrere Bits repräsentiert, oder komprimiert / verschlüsselt nach der Codierung.

Somit wird jedes Bit unabhängig (zufällig mit einer festen Wahrscheinlichkeit), entweder korrekt empfangen, oder umgedreht. Unter der Annahme der Übertragung recht zuverlässig ist, sind die meisten Bits korrekt empfangen. So Fehler in einer kleinen Anzahl von Bits sind wahrscheinlicher, und die gleichzeitigen Fehler in einem großen Anzahl von Bits sind unwahrscheinlich.

Also, in der Regel ein Hamming-Code zielt darauf ab, 1-Bit-Fehler zu korrigieren und / oder 2-Bit-Fehler zu erkennen (den Wikipedia-Artikel für Details der beiden Haupttypen sehen). Codes, die korrekten / detect größere Fehler konstruiert werden können, aber AFAIK ist so viel nicht verwendet.

Der Code funktioniert durch die gleichmäßige Verteilung der Codepunkte Abstand heraus in „Hamming-Raum“, die mathematisch der metrische Raum ist, die aus allen Werten der relevanten Wortgröße, mit Hamming-Abstand als Metrik. Stellen Sie sich vor, dass jeder Codepunkt durch eine kleine „Pufferzone“ von ungültigen Werten umgeben ist. Wenn ein Wert empfangen wird, der kein Codepunkt ist, dann muss ein Fehler aufgetreten, weil nur gültige Codepunkte jemals übertragen werden.

Wenn ein Wert in der Pufferzone empfangen wird, dann auf der Annahme, dass ein 1-Bit-Fehler aufgetreten , der den Wert übertragen wurde, muss Abstand 1 von dem Wert empfangen. Aber weil die Codepunkte verteilt sind, gibt es nur einen Code Punkt, der in der Nähe. So ist es „korrigiert“ zu diesem Codepunkt aus Gründen, dass ein 1-Bit-Fehler ist wahrscheinlicher, als der größere Fehler, der für einen anderen Codepunkt benötigt würde, um den Wert erhalten zu produzieren. In der Wahrscheinlichkeits Bedingungen, die Sie die bedingte Wahrscheinlichkeit, die in der Nähe Codepunkt gesendet wird, ist größer als die bedingte Wahrscheinlichkeit, dass Sie einen anderen Code Punkt senden, da ich den Wert erhielt ich. Also ich denke, dass Sie die in der Nähe eines mit einem gewissen Vertrauen auf der Grundlage der Zuverlässigkeit der Übertragung und die Anzahl von Bits in jedem Wort gesendet.

Wenn ein ungültiger Wert empfangen wird, das von zwei Codepunkten gleich weit entfernt ist, dann kann ich nicht sagen, dass man eher ist der wahre Wert ist als der andere sein. Also habe ich den Fehler erkennen, aber ich kann es nicht korrekt.

Offensichtlich 3-Bit-Fehler werden nicht durch einen SECDED Hamming-Code korrigiert. Der empfangene Wert ist weiter von dem Wert, den Sie tatsächlich gesendet, als sie zu einem anderen Codepunkt ist, und ich „korrigieren“, um es den falschen Wert irrtümlich. Also entweder Sie Übertragung zuverlässig brauchen genug, dass man nicht über sie kümmern, sonst müssen Sie auf höhere Ebene Fehlererkennung als auch (zum Beispiel ein CRC über eine gesamte Nachricht).

Answer 2

Speziell von Wikipedia ist der Algorithmus wie folgt:

1. Nummer beginnend die Bits von 1: Bit 1, 2, 3, 4, 5, usw.
.
2. Schreiben Sie die Bit-Zahlen in binär. 1, 10, 11, 100, 101, etc.
3. alle Bit-Positionen, die (nur ein 1-Bit in der binären Form ihrer Position haben) sind Paritätsbits Potenzen von zwei sind.
4. Alle anderen Bitpositionen, mit zwei oder mehreren 1-Bits in der binären Form ihrer Position sind Datenbits.
5. Jedes Datenbit wird in einem einzigartigen Satz von 2 oder mehr Paritätsbits enthalten, wie durch die binäre Form seiner Bitposition bestimmt.
   1. Paritätsbit 1 umfasst alle Bit-Positionen, die das niedrigstwertige Bit gesetzt haben: Bit 1 (das Paritätsbit selbst), 3, 5, 7, 9, usw.
   .
   2. Paritätsbit 2 deckt alle Bitpositionen, die die zweitniedrigstwertigen Bit gesetzt haben: Bit 2 (das Paritätsbit selbst), 3, 6, 7, 10, 11, etc
   .
   3. Paritätsbit 4 deckt alle Bitpositionen, welche die dritte niedrigstwertige Bit gesetzt haben. Bits 4-7, 12-15, 20-23, usw.
   4. Paritätsbit 8 deckt alle Bitpositionen, die das vierte niedrigstwertige Bit gesetzt. Bits 8-15, 24-31, 40-47, usw.
   5. In der Regel jedes Paritätsbit umfasst alle Bits, wobei die binären UND die Paritätsposition und die Bit-Position nicht Null ist.

Answer 3

Die Wikipedia-Artikel es ganz gut erklärt.

Wenn Sie nicht über einen bestimmten Aspekt des Algorithmus verstehen, dann müssen Sie neu zu formulieren (oder Detail) Ihre Frage, so dass jemand Ihren spezifischen Teil des Problems adressieren kann.