Der Hamming-Code ist ein von Richard Wesley Hamming entwickelter linearer fehlerkorrigierender Blockcode, der in der digitalen Signalverarbeitung und der Nachrichtentechnik zur gesicherten Datenübertragung oder Datenspeicherung verwendet wird.
Beim Hamming-Code handelt es sich um eine Klasse von Blockcodes unterschiedlicher Länge, die durch eine allgemeine Bildungsvorschrift gebildet werden. Die Besonderheit dieses Codes besteht in der Verwendung mehrerer Paritätsbits. Diese Bits ergänzen jeweils unterschiedlich gewählte Gruppen von den die Information tragenden Nutzdatenbits. Durch eine geschickte Wahl der Gruppierung, deren mathematische Grundlagen im Folgenden beschrieben sind, ist nicht nur eine Fehlererkennung, sondern auch eine Fehlerkorrektur der übertragenen Datenbits möglich.
Die einzelnen Codewörter des Hamming-Codes weisen einen Hamming-Abstand von 3 auf. Durch diesen Unterschied von jeweils drei Bitstellen kann der Decoder einen oder zwei Bitfehler in einem Datenblock erkennen, aber nur einen Bitfehler korrigieren. Bei zwei Bitfehlern liefert der Decoder ein gültiges, aber falsches Codewort. Der erweiterte Hamming-Code mit einem Hamming-Abstand von 4 kann durch ein zusätzliches Paritätsbit bis zu drei Bitfehler in einem Datenblock erkennen, aber auch nur einen Bitfehler korrigieren. Zwei Bitfehler werden bei dem erweiterten Hamming-Code als fehlerhaftes (ungültiges) Codewort erkannt, das nicht korrigierbar ist. Eigenschaften binärer Hamming-CodeStellenzahl 2k−1, k ≥ 2 und ganzzahligGewicht 3Maximaldistanz 3Hamming-Abstand 3Redundanz kk ist die Anzahl der Paritätsbits pro Codewort
Geschichte In den 1940er Jahren arbeitete Richard Hamming in der Firma Bell Labs an einem Computer namens Bell Model V, der mit fehleranfälligen elektromechanischen Relais mit zwei Maschinenzyklen pro Sekunde ausgestattet war. Die zu Dateneingaben verwendeten Lochkarten konnten durch Abnutzung bei der Leseoperation Fehler aufweisen, die zu den normalen Bürozeiten durch Angestellte der Bell Labs von Hand korrigiert werden mussten. Zu den üblichen Arbeitszeiten von Richard Hamming, außerhalb der Bürozeiten und am Wochenende, führten diese Lesefehler dazu, dass der Computer die fehlerhaften Lochkarten übersprang und an anderen Lochkarten weiterarbeitete.
Hamming war durch diese Fehler und den mehrfachen Aufwand frustriert und entwickelte in Folge einen speziellen Code, durch den die Maschine Lesefehler von Lochkarten in bestimmtem Umfang selbständig erkennen und korrigieren konnte. Im Jahr 1950 publizierte er diesen Hamming-Code,Richard W. Hamming: Error Detection and Error Correction Codes. In: The Bell System Technical Journal, Vol. XXIX 2, 1950, Seite 147–160. der noch heute und in teilweise erweiterten Formen im Bereich der Kanalkodierung verbreitete Anwendung findet.
Aufbau des Codes Im Folgenden werden nur binäre Hamming-Codes dargestellt. Binäre Hamming-Codes basieren auf Paritycodes über einem Datenblock fixer Länge. Der Datenblock, auch als „Datenwort“ oder „Nachrichtenwort“ bezeichnet, umfasst Bits und enthält die eigentliche Nutzinformation. kann bei dem Hamming-Code nur spezifische ganzzahlige Werte annehmen, die sich aus der Bildungsvorgabe dieses Codes ergeben. Die Bitkombinationen in dem Bit umfassenden Datenblock können grundsätzlich beliebig gewählt werden, das heißt, es sind alle beliebigen Bitkombinationen zulässig.
Das Codewort des Hamming-Codes wird aus dem Datenwort durch Integration zusätzlicher Kontrollstellen, der sogenannten Paritätsbits, gewonnen. Dabei wird in jedes Datenwort von Bit Länge eine feste Anzahl von Kontrollstellen eingefügt. Daraus ergibt sich das Codewort mit einer Länge von . Für ein Codewort sind, da die Kontrollstellen redundante aus dem Datenblock abgeleitete Information tragen, nur noch bestimmte Bitkombinationen möglich. Das ermöglicht sowohl Fehlererkennung als auch Fehlerkorrektur.
Die Vorgabe zur Codebildung durch eine weitere Gleichung von zu ist in folgender Form beschrieben:
Dies bedeutet, dass wenn beispielsweise drei binäre Stellen für Kontrollbits (Paritätsbits) zur Verfügung stehen, das Codewort zwangsläufig eine Länge von aufweisen muss. Für das Datenwort ergibt sich dann eine Länge von Bits pro Codewort oder allgemein:
In der folgenden Tabelle sind alle möglichen Hamming-Codes unterschiedlicher Codewortlängen bis zur Blockgröße von 255 Bits dargestellt:
Parameterkombinationen bei Hamming-Codes n k N = n + kn / (n + k)2k – k – 12k – 1(2k – k – 1) / (2k – 1) Datenbits(Datenwort) Paritätsbits(Kontrollstellen) Nachrichtenbits(Gesamtlänge des Codewortes)Datenrate1231/3 ≈ 0,3334374/7 ≈ 0,5711141511/15 ≈ 0,7332653126/31 ≈ 0,8395766357/63 ≈ 0,9051207127120/127 ≈ 0,9452478255247/255 ≈ 0,969
Zur Klassifikation der unterschiedlich langen Hamming-Codes wird in der Literatur meist folgende Schreibweise verwendet: -Code. Die erste Zahl gibt die Anzahl der Nachrichtenbits des Codewortes an, die zweite Zahl die Anzahl der Datenbits pro Codewort. Vor allem in Demonstrationsbeispielen ist der Einfachheit wegen oft der -Hamming-Code anzutreffen. Für reale Anwendungen ist hier der Overhead, d. h. das Verhältnis von Kontrollbits zu Datenbits, zu ungünstig, weshalb längere Hamming-Codes wie der -Hamming-Code verwendet werden.
Manchmal wird bei der Klassifizierungsangabe noch die Distanz des Codes als dritte Stelle angegeben. Wegen der festen Hamming-Distanz wird jedoch zumeist statt „-Hamming-Code“ nur „-Hamming-Code“ geschrieben.
Berechnung der Paritätsstellen Die Paritätsstellen (Kontrollbits) in einem Codewort werden nach einem Verfahren berechnet, wie es auch bei dem einfachen Paritäts-Prüfbit zur Anwendung kommt. Im Regelfall wird vereinbarungsgemäß eine gerade Parität für alle Kontrollstellen gewählt: Ist die Anzahl der logischen- der in die jeweilige Kontrollstelle eingerechneten Datenbitstellen eine gerade Anzahl, ist das jeweilige Paritätsbit logisch-. Ist die Anzahl der logisch- in den Datenbitstellen eine ungerade Anzahl, wird das jeweilige Paritätsbit auf logisch- gesetzt, so dass sich als Summe der Datenbitstellen und der Paritätsbits immer eine gerade Anzahl von logisch- Bits ergibt.
Die einzelnen Paritätsbits eines Codewortes werden nicht über alle Stellen (Bits) des Datenwortes gebildet, sondern nur über einzelne, ausgewählte Datenbits. Zur Konstruktion, welche Datenbitstellen in welche Kontrollbits eingerechnet werden, kann nach einer anschaulichen Methode vorgegangen werden. Zunächst wird dazu der Rahmen des Codewortes aus den Datenbits und den Kontrollstellen gebildet:
Im Codewort befinden sich an denjenigen Positionen, die Zweierpotenzen sind (1, 2, 4, 8, 16, …), die einzelnen Paritäts-Kontrollbits p. Die Datenbits d des zu übertragenden Datenwortes werden dazwischen auf den freien Stellen im Codewort von links aufsteigend eingetragen.
Sind Paritätsbits, Bits des Datenwortes und die Bits des zu bildenden Codewortes, hat ein Codewort des so konstruierten Hamming-Code die folgende Form (diese Darstellung kann für größere Codewortlängen entsprechend erweitert werden):
mini|zentriert|750px|Anordnung der Paritäts-Kontrollstellen p1…pk und der Datenbits d1…dN-k in einem Codewort mit den Stellen c1…cN für die im Folgenden dargestellte Bitanordnung.
In das erste Paritätsbit wird jedes zweite Datenbit, bei angefangen, mit einbezogen. Für das erste Paritätsbit ergeben sich als Folge von Codewortstellen somit alle Datenbits, die an ungerade Position im Codewort stehen:
Das Symbol ist die logische XOR-Funktion und stellt zugleich die Bildungsvorschrift für die Kontrollbits dar. Wie weiter mit Hilfe obiger Tabelle zu erkennen ist, kommen an den angeführten Bitpositionen im Codewort auf der rechten Seite der Gleichung nur Datenbits vor. Dies gilt für alle Paritätsbits.
In das zweite Paritätsbit wird das rechts von p2 im Codewort stehende Bit einberechnet, dann werden zwei Stellen im Codewort übersprungen, die nächsten zwei Bit und einberechnet, wieder zwei Stellen übersprungen, und so weiter. Statt eines Datenbits werden also zwei benachbarte Datenbits genommen und im Codewort zwei Stellen übersprungen. Damit ergibt sich für die Bildungsvorschrift:
In das dritte Paritätsbit p3 werden die rechts im Codewort folgenden drei Stellen einberechnet, es werden vier Stellen des Codewortes übersprungen, dann vier Bit einberechnet, dann vier Stellen übersprungen, und so weiter. Es werden also Gruppen zu je vier Bits für die Bildung des Paritätsbits herangezogen. Damit ergibt sich für :
Das Paritätsbit wird also über alle Stellen cj des Codeworts berechnet, in denen an der -ten Stelle der Binärkodierung des Index j eine logische Eins steht. Nach diesem Verfahren wird für die restlichen Paritätsbits analog fortgefahren, bis alle Paritätsbits des gewählten Hamming-Codes bestimmt sind. Das Bestimmen des Codeworts wird in praktischen Applikationen durch den sogenannten Encoder vorgenommen.
Im konkreten Fall des -Hamming-Code ergibt sich so die nachfolgende Codeworttabelle. Darunter sind in den jeweiligen Spalten die Verknüpfungen der einzelnen Paritätsbits eingetragen, aus denen sich unmittelbar die später dargestellte Kontrollmatrix , auch Prüfmatrix genannt, für dieses Beispiel ergibt. In den Spalten der letzten drei Zeilen sind Pfeile an jenen Stellen eingetragen, wo sich in der Kontrollmatrix dann logisch- finden. Nach diesem Muster kann mit etwas Aufwand die Kontrollmatrix bei jedem Hamming-Code bestimmt werden. Es ist pro Zeile immer ein Paritätsbit mit einem aufwärts gerichteten Pfeil (↑) eingezeichnet, und die Datenbits zur Bestimmung des betreffenden Paritätsbits sind mit einem abwärtsgerichteten Pfeil (↓) markiert.
Bestimmung der Paritätsbits am Beispiel des (7,4)-Hamming-Code c1 c2 c3 c4 c5 c6 c7 p1 p2 d1 p3 d2 d3 d4 ↑ ↓ ↓ ↓ ↑ ↓ ↓ ↓ ↑ ↓ ↓ ↓
Die Anordnung von Paritäts- und Datenbits ist hierbei willkürlich gewählt. Es kann ohne Einschränkung eine andere Abfolge der einzelnen Bits im Codewort gewählt werden, ohne die Eigenschaft des Hamming-Codes zu ändern. Dieser Umstand wird im nachfolgenden systematischen oder auch separierbaren Hamming-Code genutzt, bei dem zur Bildung des Codeworts die Paritätsbits immer ans Ende des Datenwortes angehängt werden. Der separierbare Hamming-Code wird nach der gleichen Bildungsvorschrift gewonnen, ist aber durch eine andere Anordnung der Zeilen in der Generatormatrix und damit verbunden andere Kontrollmatrix gekennzeichnet.
Kürzester Hamming-Code Der kürzeste Hamming-Code ist der -Hamming-Code. Dabei wird ein Nutzdatenbit einem drei Bit langen Codewort zugeordnet. Mit obiger allgemeiner Berechnung ergibt sich, dass die beiden „Paritätsbits“ und nur in diesem Fall direkt dem einen Nutzdatenbit entsprechen. Es kann nur die beiden gültigen Codewörter und geben. Die ungültigen Codewörter , und werden bei der Decodierung mittels des Verfahrens der Mehrheitsentscheidung dem Codewort zugewiesen. , und dem Codewort . Damit ist der -Hamming-Code als ein Spezialfall gleich einem Wiederholungscode mit einer Länge von 3. Der -Hamming-Code ist auch der einzige Hamming-Code, der nur durch die Angabe eindeutig im Aufbau des Codewortes spezifiziert ist.
Eigenschaften Korrekturleistungen Der Hamming-Code weist, unabhängig von der gewählten Blockgröße, immer eine Distanz von drei auf. Dies bedeutet, dass sich benachbarte Codewörter immer um drei Bits unterscheiden. Tritt ein Fehler an einer Stelle eines Codeworts auf, wird dieses als ungültig erkannt und kann eindeutig dem richtigen Codewort zugeordnet, der Übertragungsfehler also korrigiert werden. Treten hingegen zwei Fehler in einem Codewort auf, funktioniert diese Zuordnung nicht mehr – die Korrektur des Decoders ordnet das empfangene Codewort fälschlich einem anderen zu. Dies wird als „Falschkorrektur“ bezeichnet. Eine andere Form des Versagens tritt bei drei Übertragungsfehlern auf: Hier erkennt der Decoder das fehlerhafte Codewort als gültig an.