Im Fernmeldewesen sind Codes von Hamming eine Familie von geradlinigen Fehlerkorrekturcodes, die den Hamming (7,4) - Code verallgemeinern, der von Richard Hamming 1950 erfunden ist. Codes von Hamming können bis zu zwei entdecken und bis zu ein Bit Fehler korrigieren. Im Vergleich kann der einfache Paritätscode nicht Fehler korrigieren, und kann nur eine ungerade Zahl von Fehlern entdecken. Codes von Hamming sind darin speziell sie sind vollkommene Codes, d. h. sie erreichen die höchstmögliche Quote für Codes mit ihrer Block-Länge und minimaler Entfernung 3.

In mathematischen Begriffen sind Codes von Hamming eine Klasse von binären geradlinigen Codes. Für jede ganze Zahl gibt es einen Code mit der Block-Länge und Nachrichtenlänge.

Folglich ist die Rate von Codes von Hamming, der für Codes mit der Entfernung und Block-Länge höchstmöglich ist.

Die Paritätskontrolle-Matrix eines Codes von Hamming wird durch die Auflistung aller Säulen der Länge gebaut, die linear unabhängig pairwise sind.

Wegen der Einfachheit von Codes von Hamming werden sie im Computergedächtnis (ECC Gedächtnis) weit verwendet. In diesem Zusammenhang verwendet man häufig einen verlängerten Code von Hamming mit einem Extraparitätsbit. Erweiterte Hamming-Codes erreichen eine Entfernung dessen, der dem Decoder erlaubt, zwischen der Situation zu unterscheiden, in der am grössten Teil des Ein-Bit-Fehlers vorgekommen ist und die Situation, in der Zwei-Bit-Fehler vorgekommen sind. In diesem Sinn sind erweiterte Codes von Hamming das Korrigieren des einzelnen Fehlers und Ermitteln des doppelten Fehlers, und häufig verwiesen auf als SECDED.

Geschichte

Hamming hat an Glockenlaboratorien in den 1940er Jahren auf dem Glockencomputer des Modells V, einer elektromechanischen relaisbasierten Maschine mit der Zykluszeit in Sekunden gearbeitet. Eingang wurde in auf geschlagenen Karten gefüttert, die Fehler unveränderlich gelesen hätten. Während Werktage würde spezieller Code Fehler und Blitz-Lichter finden, so konnten die Maschinenbediener das Problem korrigieren. Während nachbörslicher Perioden und an den Wochenenden, als es keine Maschinenbediener gab, ist die Maschine einfach zum folgenden Job weitergegangen.

Hamming hat an den Wochenenden gearbeitet, und ist zunehmend frustriert mit der Notwendigkeit gewachsen, seine Programme von Kratzer wegen der Unzuverlässigkeit des Karte-Lesers wiederanzufangen. Im Laufe der nächsten paar Jahre hat er am Problem der Fehlerkorrektur gearbeitet, eine immer stärkere Reihe von Algorithmen entwickelnd. 1950 hat er veröffentlicht, was jetzt als Hamming Code bekannt ist, der im Gebrauch heute in Anwendungen wie ECC-Gedächtnis bleibt.

Das Codezurückdatieren Hamming

Mehrere einfache Fehlererkennungscodes wurden vor Codes von Hamming verwendet, aber niemand war so wirksam wie Codes von Hamming in demselben oben des Raums.

Gleichheit

Gleichheit fügt ein einzelnes Bit hinzu, das anzeigt, ob die Zahl von 1 Bit in den vorhergehenden Daten sogar oder seltsam war. Wenn eine ungerade Zahl von Bit in der Übertragung geändert wird, wird die Nachricht Gleichheit ändern, und der Fehler kann an diesem Punkt entdeckt werden. (Bemerken Sie, dass das Bit, das sich geändert hat, das Paritätsbit selbst gewesen sein kann!) Besteht die allgemeinste Tagung darin, dass ein Paritätswert von 1 anzeigt, dass es eine ungerade Zahl von in den Daten gibt, und ein Paritätswert von 0 anzeigt, dass es eine gerade Zahl von in den Daten gibt. Mit anderen Worten: Die Daten und das Paritätsbit sollten zusammen eine gerade Zahl 1s enthalten.

Paritätsüberprüfung ist nicht sehr robust, seitdem wenn die Zahl von geänderten Bit sogar ist, hat die Kontrolle gebissen wird gültig sein, und der Fehler wird nicht entdeckt. Außerdem zeigt Gleichheit nicht an, welches Bit den Fehler enthalten hat, selbst wenn es es entdecken kann. Die Daten müssen völlig verworfen und von Kratzer wiederübersandt werden. Auf einem lauten Übertragungsmedium konnte eine erfolgreiche Übertragung viel Zeit in Anspruch nehmen oder kann nie vorkommen. Jedoch, während die Qualität der Paritätsüberprüfung schwach ist, da es nur ein einzelne Bit, diese Methode Ergebnisse im geringsten oben verwendet. Außerdem berücksichtigt Paritätsüberprüfung wirklich die Wiederherstellung eines falschen Bit, wenn seine Position bekannt ist.

Zwei fünf codieren

Zwei fünf codieren ist ein Verschlüsselungsschema, das fünf Ziffern verwendet, die aus genau drei 0s und zwei 1s bestehen. Das stellt zehn mögliche Kombinationen zur Verfügung, um genug die Ziffern 0 - 9 zu vertreten. Dieses Schema kann alle einzelnen Bit-Fehler und alle sonderbaren numerierten Bit-Fehler entdecken. Jedoch kann es nicht noch für diese Fehler korrigieren.

Wiederholung

Ein anderer Code im Gebrauch hat zurzeit jeden wiederholt Daten haben mehrere Male gebissen, um sicherzustellen, dass es durchgekommen ist. Zum Beispiel, wenn die Daten gebissen haben, um gesandt zu werden, war 1, ein n=3 Wiederholungscode würde "111" senden. Wenn die erhaltenen drei Bit nicht identisch waren, ist ein Fehler vorgekommen. Wenn der Kanal den größten Teil der Zeit sauber genug ist, wird sich nur ein Bit in jeden ändern verdreifachen sich. Deshalb, 001, 010, und 100 entspricht jeder 0 Bit, während 110, 101, und 011 einem 1 Bit entsprechen, als ob die Bit als "Stimmen" dazu gezählt haben, wie das ursprüngliche Bit war. Ein Code mit dieser Fähigkeit, die ursprüngliche Nachricht in Gegenwart von Fehlern wieder aufzubauen, ist als ein Fehlerkorrekturcode bekannt. Dieser dreifache Wiederholungscode ist wirklich der einfachste Code von Hamming damit, da es 2 Paritätsbit gibt, und Daten gebissen haben.

Solche Codes können alle Fehler jedoch nicht richtig reparieren. In unserem Beispiel, wenn der Kanal zwei Bit und der Empfänger geschnipst hat, ist "001" gekommen, das System würde den Fehler entdecken, aber beschließen, dass das ursprüngliche Bit 0 war, der falsch ist. Wenn wir die Zahl von Zeiten steigern, kopieren wir jedes Bit zu vier, wir können alle Zwei-Bit-Fehler entdecken, aber können sie (die Stimmen "Band") nicht korrigieren; an fünf können wir alle Zwei-Bit-Fehler, aber nicht alle Drei-Bit-Fehler korrigieren.

Außerdem ist der Wiederholungscode äußerst ineffizient, Durchfluss vor dreimal mit unserem ursprünglichen Fall reduzierend, und die Leistungsfähigkeit fällt drastisch, weil wir die Zahl von Zeiten steigern, wird jedes Bit kopiert, um mehr Fehler zu entdecken und zu korrigieren.

Codes von Hamming

Wenn mehr fehlerkorrigierende Bit mit einer Nachricht eingeschlossen werden, und wenn jene Bit solch eingeordnet werden können, dass verschiedene falsche Bit verschiedene Fehlerergebnisse erzeugen, dann konnten schlechte Bit identifiziert werden. In einer 7-Bit-Nachricht gibt es sieben mögliche einzelne Bit-Fehler, so konnten drei Fehlerkontrollbit nicht nur potenziell angeben, dass ein Fehler vorgekommen ist, sondern auch der gebissen hat, hat den Fehler verursacht.

Hamming hat die vorhandenen Codierschemas, einschließlich zwei fünf studiert, und hat ihre Konzepte verallgemeinert. Um mit anzufangen, hat er sich entwickelt, um das System, einschließlich der Zahl von Datenbit und Fehlerkorrektur-Bit in einem Block zu beschreiben. Zum Beispiel schließt Gleichheit ein einzelnes Bit für jedes Datenwort ein, so ASCII Wörter mit 7 Bit annehmend, Hamming hat das als (8,7) Code mit acht Bit insgesamt beschrieben, von denen 7 Daten sind. Das Wiederholungsbeispiel würde (3,1), im Anschluss an dieselbe Logik sein. Die Coderate ist die zweite Zahl, die durch das erste, für unser Wiederholungsbeispiel, 1/3 geteilt ist.

Hamming hat auch die Probleme mit dem Schnipsen von zwei oder mehr Bit bemerkt, und hat das als die "Entfernung" beschrieben (es wird jetzt die Entfernung von Hamming, nach ihm genannt). Gleichheit hat eine Entfernung 2, weil irgendwelche Zwei-Bit-Flips unsichtbar sein werden. (3,1) hat Wiederholung eine Entfernung 3, weil drei Bit in demselben geschnipst werden müssen, das dreifach ist, um ein anderes Codewort ohne sichtbare Fehler zu erhalten. (4,1) hat Wiederholung (wird jedes Bit viermal wiederholt), eine Entfernung 4, so das Schnipsen von zwei Bit kann entdeckt, aber nicht korrigiert werden. Wenn der Drei-Bit-Flip in derselben Gruppe dort Situationen sein kann, wo der Code zum falschen Codewort korrigiert.

Hamming hat sich für zwei Probleme sofort interessiert; die Erhöhung der Entfernung so viel wie möglich, während man zur gleichen Zeit die Coderate so viel wie möglich vergrößert. Während der 1940er Jahre hat er mehrere Verschlüsselungsschemas entwickelt, die dramatische Verbesserungen auf vorhandenen Codes waren. Der Schlüssel zu allen seinen Systemen war, das Paritätsbit-Übergreifen, solch zu haben, dass sie geschafft haben, einander sowie die Daten zu überprüfen.

Allgemeiner Algorithmus

Der folgende allgemeine Algorithmus erzeugt einen Code des Korrigierens des einzelnen Fehlers (SEC) für jede Zahl von Bit.

1. Numerieren Sie die Bit, die von 1 anfangen: Bit 1, 2, 3, 4, 5, usw.
2. Schreiben Sie die Bit-Zahlen in der Dualzahl. 1, 10, 11, 100, 101, usw.
3. Alle Bit-Positionen, die Mächte zwei sind (haben nur ein 1 Bit in der binären Form ihrer Position), sind Paritätsbit.
4. Alle anderen Bit-Positionen, mit zwei oder mehr 1 Bit in der binären Form ihrer Position, sind Datenbit.
5. Jeder haben Daten gebissen wird in einen einzigartigen Satz von 2 oder mehr Paritätsbit, wie bestimmt, durch die binäre Form seiner Bit-Position eingeschlossen.
6. Gleichheit hat 1 Deckel alle Bit-Positionen gebissen, die den am wenigsten bedeutenden Bohrersatz haben: Bit 1 (das Paritätsbit selbst), 3, 5, 7, 9, usw.
7. Gleichheit hat 2 Deckel alle Bit-Positionen gebissen, die den zweiten am wenigsten bedeutenden Bohrersatz haben: Bit 2 (das Paritätsbit selbst), 3, 6, 7, 10, 11, usw.
8. Gleichheit hat 4 Deckel alle Bit-Positionen gebissen, die den dritten am wenigsten bedeutenden Bohrersatz haben: Bit 4-7, 12-15, 20-23, usw.
9. Gleichheit hat 8 Deckel alle Bit-Positionen gebissen, die den vierten am wenigsten bedeutenden Bohrersatz haben: Bit 8-15, 24-31, 40-47, usw.
10. Im Allgemeinen bedeckt jedes Paritätsbit alle Bit, wo die Dualzahl UND der Paritätsposition und der Bit-Position Nichtnull ist.

Die Form der Gleichheit ist irrelevant. Gerade Bitzahl ist von der Perspektive der theoretischen Mathematik einfacher, aber es gibt keinen Unterschied in der Praxis.

Diese allgemeine Regel kann visuell gezeigt werden:

:

Gezeigt sind nur 20 verschlüsselte Bit (5 Gleichheit, 15 Daten), aber das Muster geht unbestimmt weiter. Das Schlüsselding über Hamming-Codes, die von der Sichtprüfung gesehen werden können, besteht darin, dass jedes gegebene Bit in einen einzigartigen Satz von Paritätsbit eingeschlossen wird. Um für Fehler zu überprüfen, überprüfen Sie alle Paritätsbit. Das Muster von Fehlern, genannt das Fehlersyndrom, identifiziert das Bit irrtümlicherweise. Wenn alle Paritätsbit richtig sind, gibt es keinen Fehler. Sonst identifiziert die Summe der Positionen der falschen Paritätsbit das falsche Bit. Zum Beispiel, wenn die Paritätsbit in Positionen 1, 2 und 8 einen Fehler anzeigen, dann hat 1+2+8=11 gebissen ist irrtümlicherweise. Wenn nur ein Paritätsbit einen Fehler anzeigt, ist das Paritätsbit selbst irrtümlicherweise.

Wie Sie sehen können, wenn Sie Paritätsbit haben, kann es Bit von 1 bis dazu bedecken. Wenn wir die Paritätsbit abziehen, werden wir mit Bit verlassen, die wir für die Daten verwenden können. Wie sich ändert, bekommen wir alle möglichen Codes von Hamming:

Wenn, außerdem, ein gesamtes Paritätsbit (hat 0 gebissen), eingeschlossen wird, kann der Code (aber nicht richtig) jeden Zwei-Bit-Fehler entdecken, einen SECDED-Code machend. Die gesamte Gleichheit zeigt an, ob die Gesamtzahl von Fehlern sogar oder seltsam ist. Wenn der grundlegende Code von Hamming einen Fehler entdeckt, aber die gesamte Gleichheit sagt, dass es eine gerade Zahl von Fehlern gibt, ist ein unkorrigierbarer 2-Bit-Fehler vorgekommen.

Hamming codiert mit der zusätzlichen Gleichheit (SECDED)

Codes von Hamming haben eine minimale Entfernung 3, was bedeutet, dass der Decoder entdecken und einen einzelnen Fehler korrigieren kann, aber er kann keinen doppelten Bit-Fehler von einem Kennwort von einem einzelnen Bit-Fehler eines verschiedenen Kennwortes unterscheiden. So können sie Fehler des doppelten Bit nur entdecken, wenn Korrektur nicht versucht wird.

Um diesen Fehler zu beheben, können Codes von Hamming durch ein Extraparitätsbit erweitert werden. Auf diese Weise ist es möglich, die minimale Entfernung des Codes von Hamming zu 4 zu vergrößern, der dem Decoder erlaubt, zwischen einzelnen Bit-Fehlern und Zwei-Bit-Fehlern zu unterscheiden. So kann der Decoder entdecken und einen einzelnen Fehler korrigieren und zur gleichen Zeit (aber nicht richtig) einen doppelten Fehler entdecken. Wenn der Decoder nicht versucht, Fehler zu korrigieren, kann er bis zu 3 Fehler entdecken.

Das hat sich ausgestreckt Code von Hamming ist in Computerspeichersystemen populär, wo er als SECDED ("einzelne Fehlerkorrektur, doppelte Fehlerentdeckung") bekannt ist. Besonders populär ist (72,64) Code, ein gestutzter (127,120) Code von Hamming plus ein zusätzliches Paritätsbit, das denselben Raum oben wie hat (9, 8) Paritätscode.

Hamming (7,4) Code

1950 hat Hamming (7,4) Code eingeführt. Es verschlüsselt 4 Datenbit in 7 Bit durch das Hinzufügen von drei Paritätsbit. Hamming (7,4) kann entdecken und Fehler des einzelnen Bit korrigieren. Mit der Hinzufügung eines gesamten Paritätsbit kann es auch (aber nicht richtig) Fehler des doppelten Bit entdecken.

Aufbau von G und H

Die Matrix

I_k |-a^t \\

\end {pmatrix} </Mathematik> wird eine (Kanonische) Generator-Matrix eines geradlinigen (n, k) Code, genannt

und

| I_ {n-k} \\

\end {pmatrix} </Mathematik> wird eine Paritätskontrolle-Matrix genannt.

Das ist der Aufbau von G und H im Standard (oder systematisch) Form. Unabhängig von der Form muss G und H für geradlinige Block-Codes befriedigen

, eine Vollnullmatrix [Mond, p. 89].

Seitdem (7,4,3) = (n, k, d) = [2  1, 21-M, M]. Die Paritätskontrolle-Matrix H eines Codes von Hamming wird durch die Auflistung aller Säulen der Länge M gebaut, die mit dem Paar kluger Unabhängiger sind.

So ist H eine Matrix, deren linke Seite alle NichtnullN-Tupel ist, wo die Ordnung der N-Tupel in den Säulen der Matrix nicht von Bedeutung ist. Die rechte Seite ist gerade (n-k) - Identitätsmatrix.

So kann G bei H durch die Einnahme des Umstellens der linken Seite von H mit der IdentitätsK-Identitätsmatrix linker Hand Seite von G erhalten werden.

Die Codegenerator-Matrix und die Paritätskontrolle-Matrix sind:

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} _ {4,7} </Mathematik>

und

1 & 1 & 0 & 1 & 1 & 0 & 0 \\

1 & 0 & 1 & 1 & 0 & 1 & 0 \\

0 & 1 & 1 & 1 & 0 & 0 & 1 \\

\end {pmatrix} _ {3,7}. </Mathematik>

Schließlich können diese matrices in gleichwertige unsystematische Codes durch die folgenden Operationen [Mond, p verändert werden. 85]:

• Säulenversetzungen (Säulen tauschend)

,

• Elementare Reihe-Operationen (eine Reihe durch eine geradlinige Kombination von Reihen ersetzend)

,

Verschlüsselung

Beispiel

Von der obengenannten Matrix haben wir 2=2=16 Kennwörter.

Die Kennwörter dieses binären Codes können dabei erhalten werden. Mit damit bestehen in (Ein Feld mit zwei Elementen nämlich 0 und 1).

So sind die Kennwörter alle 4 Tupel (K-Tupel).

Deshalb,

(1,0,1,1) wird als (1,0,1,1,0,1,0) verschlüsselt.

Hamming (7,4) Code mit einem zusätzlichen Paritätsbit

Der Hamming (7,4) kann zu (8,4) Code durch das Hinzufügen eines Extraparitätsbit oben auf (7,4) verschlüsseltes Wort leicht erweitert werden (sieh Hamming (7,4)).

Das kann mit dem revidierten matrices summiert werden:

:

1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\

1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\

0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\

1 & 1 & 0 & 1 & 0 & 0 & 1 & 0

\end {pmatrix} _ {4,8} </Mathematik>

und:

\mathbf {H}: =

\begin {pmatrix }\

1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\

0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 \\

0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 \\

1 & 1 & 1 & 1 & 1 & 1 & 1 & 1

\end {pmatrix} _ {4,8 }\

. </Mathematik>

Bemerken Sie, dass H nicht in der Standardform ist. Um G zu erhalten, können elementare Reihe-Operationen verwendet werden, um eine gleichwertige Matrix zu H in der systematischen Form zu erhalten:

:

\mathbf {H} =

\left (\left.\begin {Reihe} {cccc }\

0 & 1 & 1 & 1 \\

1 & 0 & 1 & 1 \\

1 & 1 & 0 & 1 \\

1 & 1 & 1 & 0\end {ordnen }\\Recht |\begin {Reihe} {cccc }\

1 & 0 & 0 & 0 \\

0 & 1 & 0 & 0 \\

0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1\end {ordnen }\\Recht) _ {4,8 }\

. </Mathematik>

Zum Beispiel ist die erste Reihe in dieser Matrix die Summe der zweiten und dritten Reihen von H in der unsystematischen Form. Mit dem systematischen Aufbau für Codes von Hamming von oben ist die Matrix A offenbar, und die systematische Form von G wird als geschrieben

:

\mathbf {G} =

\left (\left.\begin {Reihe} {cccc }\1 & 0 & 0 & 0 \\0 & 1 & 0 & 0 \\0 & 0 & 1 & 0 \\

0 & 0 & 0 & 1\end {ordnen }\\Recht |\begin {Reihe} {cccc }\

0 & 1 & 1 & 1 \\1 & 0 & 1 & 1 \\1 & 1 & 0 & 1 \\

1 & 1 & 1 & 0\end {ordnen }\\Recht) _ {4,8 }\

. </Mathematik>

Die unsystematische Form von G kann Reihe reduziert (das Verwenden elementarer Reihe-Operationen) sein, um diese Matrix zu vergleichen.

Die Hinzufügung der vierten Reihe schätzt effektiv die Summe aller Kennwort-Bit (Daten und Gleichheit) als das vierte Paritätsbit.

Zum Beispiel, wird darin verschlüsselt, wo blaue Ziffern Daten sind; rote Ziffern sind Gleichheit von Hamming (7,4) Code; und die grüne Ziffer ist die Gleichheit, die von Hamming (8,4) hinzugefügt ist.

Die grüne Ziffer macht die Gleichheit (7,4) Code sogar.

Schließlich kann es gezeigt werden, dass die minimale Entfernung von 3, als mit (7,4) Code, zu 4 mit (8,4) Code zugenommen hat. Deshalb kann der Code als Hamming (8,4,4) definiert werden.

Siehe auch

• Das Codieren der Theorie
• Golay codieren

Code des Rohres-Muller Fehlerkorrektur des Rohres-Solomon Turbocode

• Paritätskontrolle der niedrigen Dichte codiert
• Hamming hat gebunden

Zeichen

Außenverbindungen

• CGI Schrift, für Entfernungen von Hamming (von R. Tervo, UNB, Kanada) zu berechnen