WikiDer > Hamming-Code

Hamming-code

In dem Telekommunikation ist ein Hamming-Code ein fehlerkorrigierender Code, benannt nach dem Erfinder, Richard Hamming. Hamming-Codes sind lineare Codes, und sie können 1- oder 2-Bit-Fehler erkennen oder 1-Bit-Fehler korrigieren. Dies steht im Gegensatz zur Verwendung einer einzelnen Paritätsprüfung (mit 1 Paritätsbit), die keine gerade Anzahl von Bitfehlern erkennt und bei der Korrektur gefundener Bitfehler nicht helfen kann.

Geschichte

Hamming arbeitete in der 1940er Jahre Biene Bell Labs zum Bell Model V Computer, einem elektromechanischen Relais-Giganten mit einer Zykluszeit von wenigen Sekunden. Die Dateneingabe erfolgte über Lochkarten, was immer zu Lesefehlern führte. An Werktagen sorgte ein spezieller Code dafür, dass Fehler erkannt und die Bediener über Lichtsignale gewarnt wurden, um das Problem zu beheben. Außerhalb der Bürozeiten und an Wochenenden, wenn kein Bediener anwesend war, fuhr die Maschine einfach mit der nächsten Aufgabe fort.

Hamming arbeitete an Wochenenden und wurde zunehmend frustriert, seine Programme aufgrund der Unzuverlässigkeit des Kartenlesers neu starten zu müssen. Er beschäftigte sich mehrere Jahre mit dem Thema Fehlerkorrektur und entwickelte eine Reihe leistungsstarker Algorithmen. 1950 veröffentlichte er den heutigen Hamming-Code, der in bestimmten Situationen noch heute verwendet wird.

Codes, die dem Hamming-Code vorausgingen

Eine Reihe einfacher Fehlererkennungscodes wurden zuvor verwendet, aber sie waren gleich Redundanz viel weniger effektiv als Hamming-Codes. Einige werden hier kurz beschrieben.

Paritätsbit

Ein einzelnes Bit wird zu einem Codewort hinzugefügt, das anzeigt, ob in diesem Wort ein Ein bisschen oder ein seltsam Anzahl der Bits hat den Wert 1. Ein einzelner Bitfehler auf dem Übertragungsweg ändert die Parität, wodurch der Fehler erkannt wird. Dadurch wird jedoch eine gerade Anzahl von Bitfehlern nicht bemerkt. Außerdem ist ein erkannter Bitfehler nicht klar welche Bitfehler wurde empfangen; die einzig mögliche Korrekturmethode besteht darin, eine erneute Übertragung durchzuführen.

'Zwei von fünf'-Code

In den 1940er Jahren verwendete Bell auch einen etwas ausgefeilteren Code, der als bekannt ist zwei von fünf. Dieser Code hatte die Eigenschaft, dass jedes 5-Bit-Codewort genau zwei Einsen enthielt. Heute nennen wir das a Konstantgewichtscode. Wenn die Eingabe vom Computer ein Wort mit nicht genau zwei Einsen erhielt, trat eine Fehlererkennung auf. Es ist aber auch bei diesem Code möglich, dass 2 Bitfehler in 1 Wort nicht erkannt werden.

Probencode

Ein anderer Code wiederholt einfach jedes Datenbit mehrmals. Wenn beispielsweise das zu sendende Datenbit eine 1 war, wurde ein n=3 gesendet Probencode das Wort "111". Waren die drei empfangenen Bits nicht identisch, erfolgte eine Fehlererkennung. Die Fehlerkorrektur funktioniert wie folgt: Beim Empfang von 000, 001, 010 oder 100 wird das decodierte Datenbit zu einer 0, während der Empfang von 111, 110, 101 oder 011 zu einer Decodierung führt, als ob die empfangenen Bits " demokratisch" geben an, was das ursprüngliche Bit ist. Dies ist ein grundlegendes Beispiel für einen Fehlerkorrekturcode.

Natürlich können solche Codes nicht alle möglichen Fehler korrekt korrigieren. Außerdem ist der Probencode sehr ineffizient.

Hamming-Codes

Grafische Darstellung der 4 Datenbits und 3 Paritätsbits und welche Paritätsbits zu welchen Datenbits im (7.4) Hamming-Code gehören

Wenn einer Nachricht weitere fehlerkorrigierende Bits hinzugefügt werden und diese Bits so angeordnet sind, dass unterschiedliche "falsche" Bits unterschiedliche Auswirkungen haben, werden fehlerhafte Bits identifizierbar. In einer 7-Bit-Nachricht sind sieben Einzelbitfehler möglich, so dass im Prinzip drei redundante Bits ausreichen, um nicht nur anzuzeigen, dass ein Fehler aufgetreten ist, sondern auch (bei einem Einzelbitfehler), welches Bit falsch ist.

Hamming studierte die bestehenden Codes, einschließlich zwei von fünf, und suchte nach Verallgemeinerungen. Wenn beispielsweise ein Paritätsbit verwendet wird, wird jedem Datenwort ein einzelnes Bit hinzugefügt; ab ASCIIBuchstaben bestehend aus 7 Bit, Hamming beschrieb dies als a (8,7)Code mit insgesamt acht Bits, davon 7 Datenbits. Der Probencode im Beispiel wäre a (3,1)Code genannt. Das Informationsrate ist die zweite Zahl geteilt durch die erste, für unseren Probencode 1/3.

Hamming untersuchte auch die Probleme, die mit zwei oder mehr Bitfehlern verbunden sind, und entwickelte das Konzept der Hamming-Abstand. Der Paritätscode hat einen Abstand von 2, da ein Doppelbitfehler nicht bemerkt wird. Der (3.1) Wiederholungscode hat einen Abstand von 3, da bei einem zulässigen Codewort (000 oder 111) drei Bits geändert werden müssen, um ein anderes zulässiges Codewort zu erhalten.

Hamming interessierte sich für zwei Themen; er wollte sowohl den Abstand (und damit die Fehlerkorrekturkapazität) wie möglich erhöhen und die Informationsrate (mittlerer Informationsgehalt eines Übertragungsbits) möglichst groß machen. Während der 1940er Jahre er entwickelte mehrere Codes, die eine große Verbesserung gegenüber bereits existierenden Codes darstellten. Alle seine Systeme hatten die Eigenschaft, dass sich sowohl die Paritätsbits als auch die Datenbits gegenseitig „überprüften“.

Der Algorithmus des (verallgemeinerten) Hamming-Codes ist einfach:

alle Bitpositionen mit Zweierpotenzen werden als Paritätsbits verwendet (Bitpositionen 1, 2, 4, 8, 16, 32, 64 usw.)
alle anderen Bitpositionen werden für die zu codierenden Daten verwendet (Bitpositionen 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17 usw.)
jedes Paritätsbit berechnet die Parität für eine Anzahl von Bits aus dem Codewort. Die Position des Paritätsbits bestimmt die Reihe der Bits, die jeweils in die Berechnung des Paritätsbits eingehen.
- Paritätsbit 1: Bit 1 (das Paritätsbit selbst), 3, 5, 7, 9 usw.
- Paritätsbit 2: Bit 2 (das Paritätsbit selbst), 3, 6, 7, 10,11 usw.
- Paritätsbit 4: Bit 4 (das Paritätsbit selbst), 5, 6, 7, 12, 13, 14, 15 usw.
- Paritätsbit 8: Bit 8 (das Paritätsbit selbst), 9, 10, 11, 12, 13, 14, 15 usw.
- und so weiter

Beispiel mit dem (11.7) Hamming-Code

Betrachten Sie das 7-Bit-Datenwort "0110101". Sehen Sie sich die Tabellen an, um zu veranschaulichen, wie Hamming-Codes entworfen und verwendet werden, um einen Fehler zu erkennen. Mit d zeigt ein Datenbit an, und p ein Paritätsbit.

Zuerst werden die Datenbits an die richtige Bitposition gesetzt und dann die Paritätsbits berechnet, immer ausgehend von Ein bisschen Parität.

*Berechnung von Hamming-Code-Paritätsbits*
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇
Datenwort (ohne Parität):			0		1	1	0		1	0	1
p₁	1		0		1		0		1		1
p₂		0	0			1	0			0	1
p₃				0	1	1	0
p₄								0	1	0	1
Codewort (mit Parität):	1	0	0	0	1	1	0	0	1	0	1

Das Codewort (mit Paritätsbits) ist "10001100101".

Nehmen Sie nun an, dass das letzte Bit falsch empfangen wurde. Unser empfangenes Wort ist "10001100100"; und jetzt setzen wir jedes Paritätsbit auf 1, wenn die Paritätsprüfung eine Fehlererkennung ergibt.

*Paritätsbits prüfen* (geändertes Bit markiert)
	p₁	p₂	d₁	p₃	d₂	d₃	d₄	p₄	d₅	d₆	d₇	Paritätsprüfung	Paritätsbit
Empfangenes Wort:	1	0	0	0	1	1	0	0	1	0	0	1
p₁	1		0		1		0		1		0	Erkennung	1
p₂		0	0			1	0			0	0	Erkennung	1
p₃				0	1	1	0					Richtig	0
p₄								0	1	0	0	Erkennung	1

Der letzte Schritt besteht darin, den Wert der Paritätsbits zu bestimmen (das Bit mit dem niedrigsten Wert geht am weitesten nach rechts). Der Dezimalwert der Paritätsbits ist 11, woraus folgt, dass das elfte Bit im empfangenen Wort (einschließlich Paritätsbits) fehlerhaft ist und daher invertiert werden muss.

	p₄	p₃	p₂	p₁
binär	1	0	1	1
Dezimal	8		2	1	= 11

Das Invertieren des elften Bits ändert sich 10001100100 zurück zu 10001100101. Das Entfernen der Hamming-Paritätsbits ergibt das ursprüngliche Datenwort 0110101.

Da sich die Paritätsbits nicht gegenseitig prüfen, führt die Fehlererkennung für ein einzelnes Paritätsbit dazu, dass das Paritätsbit selbst falsch ist und nicht eines der geprüften Datenbits.

Nehmen wir nun an, dass sich zwei Bits ändern, an den Positionen X und ja. wenn X und ja binär geschrieben an Position 2^k den gleichen Bitwert haben, ändert das Paritätsbit an dieser Position seinen Wert nicht, da beide Bitfehler 'geprüft' werden. Es muss jedoch Paritätsbits geben, die den Wert ändern, weil X und ja haben nicht an jeder Position den gleichen Bitwert. Daraus folgt, dass der Hamming-Code alle Doppelbitfehler erkennt.

Heute bezeichnet Hamming-Code einen spezifischen (7.4)-Code, der 1950 von Hamming eingeführt wurde. Der Hamming-Code fügt zu jeweils vier Datenbits der zu sendenden Nachricht drei Prüfbits hinzu. Hamming-Code (7.4) kann jeden Einzelbitfehler korrigieren und alle Doppelbitfehler erkennen. Für in der Praxis vorkommende Kanäle würde die Verwendung des Hamming-Codes einen fehlerfreien Informationstransport realisieren.

Eine Erklärung mit Matrixmultiplikation

Ein Hamming-Code ist ein Beispiel für a linearer Code. Hamming-Codes verwenden die Multiplikation von Matrizen und sind eine Erweiterung des Konzepts der „Parität“. Zum Beispiel verwenden wir für den Hamming-Code (7.4) zwei Matrizen, nämlich

{displaystyle H_{e}:={ egin{pmatrix}1&0&0&0/0&1&0&0/0&0&1&0/0&0&0&1/1&1&0&1/1&0&1&1/0&1&1&1/end{pmatrix}}}

(kodieren)

und

{displaystyle H_{d}:={ egin{pmatrix}0&0&0&1&1&1&1/1&1&0&0&0&1&1/1&0&1&0&1&0&1/end{pmatrix}}}

(dekodieren)

Hinweis:

{displaystyle H_{e}}

ist die Transponierte der Generatormatrix G, So

{displaystyle mathbf {G} ={ egin{pmatrix}1&0&0&0&1&1&0/0&1&0&0&1&0&1/0&0&1&0&0&1&1/0&0&0&1&1&1&1/end{pmatrix}}}

Im aktuellen Beispiel ist das Format mit

{displaystyle H_{e}}

gehalten, also die transponiert Notation relativ zur Notation mit G.

{displaystyle H_{d}}

ist die Paritätsprüfmatrix, die entspricht G (sehen linearer Code).

Wir verwenden 'Blöcke' von vier Datenbits (daher die 4 im Namen) und berechnen drei redundante Prüfbits (daher die 7 im Namen, weil 4 3=7). Zum Senden der Daten betrachten wir den zu sendenden Datenbitblock als Vektor, zum Beispiel bei den Datenbits "1011" ist es der Vektor

{displaystyle mathbf {p} ={ egin{pmatrix}1/0/1/1end{pmatrix}}}

Angenommen, wir möchten diese Datenbits senden. Wir multipliziere die Matrix ${displaystyle H_{e}}$ mit p, natürlich Modulo 2 berechnen:

{displaystyle H_{e}mathbf {p} ={ egin{pmatrix}1&0&0&0/0&1&0&0/0&0&1&0/0&0&0&1/1&1&0&1/1&0&1&1/0&1&1&1/end{pmatrix}}{ egin{pmatrix}1/ }={ .in{pmatrix} /0/1/1/0/1/0end{pmatrix}}=mathbf {r} }

Der Empfänger erhält die r mal ${displaystyle H_{d}}$ , um zu sehen, ob ein Fehler aufgetreten ist. Daraus ergibt sich (wieder modulo 2 berechnend):

{displaystyle H_{d}mathbf {r} ={ egin{pmatrix}0&0&0&1&1&1&1/1&1&0&0&0&1&1/1&0&1&0&1&0&1/end{pmatrix}}{ egin{pmatrix}1/0/1/1/0/1/0end}=pmatrix { start {pmatrix}0/0/0ende{pmatrix}}}

In diesem Fall ist das Ergebnis der Nullvektor, so dass der Empfänger schließen kann, dass keine Bitfehler aufgetreten sind.

Nehmen Sie nun an, dass ein einzelner Bitfehler aufgetreten ist. Wir können das empfangene Wort schreiben als

{displaystyle mathbf {r} mathbf {e} _{i}}

modulo 2, wobei e_ichEinheitsvektor Nummer ich ist: ein mit Nullen gefüllter Vektor, aber mit einer 1 an Position ich. So ${displaystyle mathbf {r} mathbf {e} _{i}}$ entspricht einem einzelnen Bitfehler an Ort und Stelle ich.

Wenn wir diesen Vektor mit multiplizieren ${displaystyle H_{d}}$ :

{displaystyle H_{d}(mathbf {r} mathbf {e} _{i})=H_{d}mathbf {r} H_{d}mathbf {e} _{i}}

weil r ist das empfangene Codewort, wenn keine Bitfehler vorliegen, ist das Produkt von ${displaystyle H_{d}}$ und r gleich Null. So

{displaystyle H_{d}mathbf {r} H_{d}mathbf {e} _{i}=mathbf {0} H_{d}mathbf {e} _{i}=H_{d}mathbf {e} _{ ich}}

Das Produkt von ${displaystyle H_{d}}$ mit Einheitsvektornummer ich wird die Spalte von sein ${displaystyle H_{d}}$ Das ist an der Bitposition, an der der Fehler aufgetreten ist. Die Spalten von ${displaystyle H_{d}}$ alle unterscheiden sich voneinander und sind in einer speziellen Reihenfolge: Wenn wir jede Spalte als binär geschriebene ganze Zahl betrachten, dann sind die Spalten genau aufsteigend mit Schrittweite 1.

Wenn wir mit dem empfangenen Wort beginnen ${displaystyle mathbf {s} }$ , dann macht es Sinn ${displaystyle H_{d}mathbf {s} }$ in binäre Zahl umwandeln; zum Beispiel (1, 0, 1) ist eine Spalte von ${displaystyle H_{d}}$ und entspricht Position 5. Bei einem einzelnen Bitfehler wissen wir, wo der Fehler aufgetreten ist und können ihn korrigieren.

Nehmen wir zum Beispiel an, dass

{displaystyle mathbf {s} =mathbf {r} mathbf {e} _{2}={ egin{pmatrix}1/1/1/1/0/1/0end{pmatrix}}}

Dann ist

{displaystyle H_{d}mathbf {s} ={ egin{pmatrix}0&0&0&1&1&1&1/1&1&0&0&0&1&1/1&0&1&0&1&0&1/end{pmatrix}}{ egin{pmatrix}1/1/1/1/0/1/0end}=pmatrix { start {pmatrix}0/1/0Ende{pmatrix}}}

was Spalte 2 entspricht (dezimale Übersetzung der binären "010"); an Stelle 2 ist also ein Fehler aufgetreten, der nun korrigiert werden kann.

Es ist nicht schwer zu zeigen, dass auf diese Weise nur Einzelbitfehler korrigiert werden können. Hamming-Codes können jedoch auch verwendet werden, um sowohl Einzel- als auch Doppelbitfehler zu erkennen, indem beachtet wird, dass das Produkt von ${displaystyle H_{d}}$ mit ${displaystyle mathbf {s} }$ bei Bitfehlern ungleich Null ist. Denn bei zwei Bitfehlern wird das empfangene Wort ${displaystyle mathbf {s} =mathbf {r} mathbf {e} _{i} mathbf {e} _{j}}$ und ist ${displaystyle H_{d}mathbf {s} }$ gleich der Summe von zwei Spalten von ${displaystyle H_{d}}$ ; dies wird niemals der Nullvektor sein, da alle Spalten unterschiedlich sind. Somit werden immer zwei Bitfehler erkannt.

Ein gleichzeitiges Korrigieren von Einzelbitfehlern und Erkennen von Doppelbitfehlern ist nicht möglich. Sie haben also die Wahl zwischen:

Korrektur einzelner Bitfehler
Erkennung von Einzel- und Doppelbitfehlern

Siehe auch

Navigation