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, welche 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, welches nicht korrigierbar ist.
| Eigenschaften binärer Hamming-Code | |
|---|---|
| Stellenzahl | 2k−1, k ≥ 2 und ganzzahlig |
| Gewicht | 3 |
| Maximaldistanz | 3 |
| Hamming-Abstand | 3 |
| Redundanz | k |
| k ist die Anzahl der Paritätsbits pro Codewort |
Geschichte Bearbeiten
In den 1940er Jahren arbeitete Richard Hamming in der Firma Bell Labs an einem Computer namens Bell Model V, welcher 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, der noch heute und in teilweise erweiterten Formen im Bereich der Kanalkodierung verbreitete Anwendung findet.
Aufbau des Codes Bearbeiten
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 + k | n / (n + k) |
| 2k – k – 1 | 2k – 1 | (2k – k – 1) / (2k – 1) | |
| Datenbits (Datenwort) | Paritätsbits (Kontrollstellen) | Nachrichtenbits (Gesamtlänge des Codewortes) | Datenrate |
| 1 | 2 | 3 | 1/3 ≈ 0,333 |
| 4 | 3 | 7 | 4/7 ≈ 0,571 |
| 11 | 4 | 15 | 11/15 ≈ 0,733 |
| 26 | 5 | 31 | 26/31 ≈ 0,839 |
| 57 | 6 | 63 | 57/63 ≈ 0,905 |
| 120 | 7 | 127 | 120/127 ≈ 0,945 |
| 247 | 8 | 255 | 247/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 Bearbeiten
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 in Summe in den Datenbitstellen und den Paritätsbit, 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):
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 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-Code 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ätsbit 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 Bearbeiten
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 Bearbeiten
Korrekturleistungen Bearbeiten
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.
Hamming-Codes können also nur einen Bitfehler pro Datenwort korrekt korrigieren. Wegen seiner Fähigkeit, alle empfangenen Codewörter einem validen Codewort zuordnen zu können, ist der Hamming-Code ein perfekter Code. Die meisten anderen Binärcodes – etwa der erweiterte Hamming-Code – sind nicht perfekt. Bei diesen Codes können durch Übertragungsfehler Codewörter auftreten, die der Decoder zwar als falsch erkennen kann, jedoch keinem gültigen Wort zuordnen kann (Dekodierversagen).
Linearität Bearbeiten
Hamming-Codes sind grundsätzlich lineare Codes. Bei diesen – auch als binäre Gruppencodes bezeichneten – Codierungen führt jede Modulo-2-Addition (XOR-Verknüpfung) zweier Codewörter wieder zu einem gültigen Codewort. Zu den Voraussetzungen eines linearen Code zählt die Existenz eines neutralen Elements. Im Falle eines Hamming-Codes bedeutet dies, dass das Nullwort – dessen Stellen sämtlich logisch-'0' sind – gültig sein muss. Das sogenannte „Codegewicht“ entspricht somit bei Hamming-Codes dem Hamming-Abstand von drei.
Eine weitere allgemeine Eigenschaft von Gruppencodes besteht darin, dass sich die einzelnen gültigen Codewörter c aus einer Generatormatrix G und den Datenwörtern d nach folgender Form erzeugen lassen:
Aus dieser Gleichung ergibt sich mit der im vorherigen Abschnitt dargestellten Bildungsvorschrift, und den Rechenregeln für Matrizen für einen nicht separierbaren -Hamming-Code, die folgende Generatormatrix :
Die ersten beiden Zeilen der Matrix bilden die ersten beiden Paritätsbits und des Codewortes. Die Einsen der Zeilen geben hierbei an, welche Datenbitstellen in das jeweilige Paritätsbit eingerechnet werden. Die dritte Zeile, ebenso wie alle nachfolgenden Zeilen mit nur einer Eins pro Zeile, bilden die Datenbits im Codewort ab. Die vierte Zeile bildet das dritte Paritätsbit .
Aus der Generatormatrix lässt sich direkt die Kontrollmatrix ableiten, die vom Decoder verwendet wird, um fehlerhafte Bitstellen mittels Matrixmultiplikation zu erkennen. Die Prüfmatrix muss so gewählt sein, dass sie orthogonal zu allen gültigen Codewörtern ist:
Für obige Generatormatrix lässt sich die folgende Kontrollmatrix ermitteln:
Der Inhalt der Matrix kann hierbei beispielsweise über das im vorigen Abschnitt vorgestellte, tabellarische Verfahren zur Bestimmung der Paritätsbits aus der Generatormatrix gewonnen werden.
Tritt ein einzelner Bitfehler auf, so gilt für das entstehende, ungültige Codewort:
Durch den Wert dieser Gleichung kann über eine Syndromtabelle die fehlerhafte Bitstelle eindeutig bestimmt und durch Invertieren korrigiert werden.
Eine spielerische Anwendung speziell des -Hamming-Codes findet man bei der Lösung von Eberts Hutproblem.
Systematischer Hamming-Code Bearbeiten
Aufgrund der Linearität können beliebige Zeilen der Generatormatrix vertauscht werden, ohne die Codeeigenschaften zu verändern. Die jeweilige Form der Generatormatrix muss nur zwischen Encoder und Decoder abgestimmt sein. Ein systematischer Code liegt vor, wenn im Codewort zuerst alle Datenbits dn und nachfolgend alle Paritätsbits pn angeordnet sind. Durch die Separierbarkeit können Encoder und Decoder schaltungstechnisch in elektronischen digitalen Schaltungen wie ASICs oder FPGAs mit weniger Speicheraufwand und mit geringerer Latenzzeit realisiert werden. Separierbare Codes werden auch als „systematische Codes“ bezeichnet.
Obige Generatormatrix kann durch Umstellen der Zeilen auf folgende Generatormatrix ′ so umgeformt werden, dass der -Hamming-Code ein systematischer Code wird. Eine mögliche Generatormatrix des systematischen -Hamming-Codes lautet:
Die assoziierte Kontrollmatrix ′ kann leichter bestimmt werden, denn bei systematischer Blockcodes gilt mit Modulo-2-Operationen:
Damit bestimmt sich ′ zu:
Die ersten 4 Spalten der Kontrollmatrix ′ bestehen dabei aus den letzten drei Zeilen der Generatormatrix ′. Der rechte Teil der Kontrollmatrix ist mit der Einheitsmatrix aufgefüllt.
Damit ist dargestellt, dass nur die Angabe -Hamming-Code für eine konkrete Implementierung nicht eindeutig den genauen Codierungsvorgang und Decodierungsvorgang beschreibt. Dies ist erst durch Angabe der jeweiligen Generatormatrix, oder bei zyklischen Hamming-Codes durch das Generatorpolynom, gewährleistet.
Zyklischer Hamming-Code Bearbeiten
Bei der praktischen Anwendung spielen zyklische Codes, insbesondere zyklische separierbare Hamming-Codes, eine bedeutende Rolle. Mit diesen kann die Berechnung der einzelnen Prüfbits im Encoder und die Decodierung im Decoder mit minimalen Speicheraufwand in Form von linear rückgekoppelten Schieberegistern (LFSR) realisiert werden. Zyklische Codes sind lineare Codes, bei denen zusätzlich noch die Forderung gilt, dass eine Rotation oder zyklische Verschiebung eines Codewortes wiederum auf ein gültiges Codewort führen muss.
Der zyklische Hamming-Code kann allgemein in der Beschreibung äquivalent auch als eine Untergruppe der BCH-Codes (Bose-Chaudhuri-Hocquenghem-Codes) aufgefasst werden. BCH-Codes sind eine sehr große Gruppe von zyklischen Blockcodes, die in ihren Parametern und Aufbau stärker als die Hamming-Codes variiert werden können.
Die Erzeugung zyklischer Hamming-Codes wird je nach Blocklänge durch primitive Generatorpolynome von entsprechendem Grad vorgenommen. Das Generatorpolynom kann direkt im LFSR zum Berechnen der Paritätsbits abgebildet werden.
In folgender Tabelle sind beispielhaft übliche Generatorpolynome angeführt. Es können in konkreten Implementierungen aber auch andere Generatorpolynome gewählt werden, ohne die Eigenschaften des Hamming-Codes zu ändern, so das gewählte Polynom nur primitiv ist und zwischen Encoder und Decoder vereinbart ist:
| Zyklische Hamming-Codes | |||
|---|---|---|---|
| k | N | n | Generatorpolynom G(z) |
| 2 | 3 | 1 | z2 + z + 1 |
| 3 | 7 | 4 | z3 + z + 1 |
| 4 | 15 | 11 | z4 + z + 1 |
| 5 | 31 | 26 | z5 + z2 + 1 |
| 6 | 63 | 57 | z6 + z + 1 |
| 7 | 127 | 120 | z7 + z3 + 1 |
| 8 | 255 | 247 | z8 + z7 + z2 + z + 1 |
| 9 | 511 | 502 | z9 + z4 + 1 |
Bemerkungen:
- z ist eine alternative Schreibweise für z1: z6 + z + 1 → z6 + z1 + 1
- 1 ist eine alternative Schreibweise für z0: z6 + z + 1 → z6 + z1 + z0
- Die Anzahl der Terme ist immer ungerade und enthält immer die Potenzen zk und 1: z6 + z + 1
- Man kann immer die Exponenten spiegeln, d. h. alle xl durch xk−l ersetzen, es entsteht ein anderer, aber genau funktionierender zyklischer Blockcode: z6 + z + 1 → z6 + z1 + z0 → z0 + z5 + z6 → z6 + z5 + 1
Praktische Realisierung eines Hamming-Encoders Bearbeiten
Zyklische separierbare Hamming-Codes lassen sich schaltungstechnisch in digitalen elektrischen Schaltungen einfach realisieren. In nebenstehender Abbildung ist zur Veranschaulichung ein -Hamming Encoder mit Generatorpolynom dargestellt.
In der Darstellung werden die Datenbits als serieller Datenstrom in der Mitte oben eingelesen und rechts das Codewort seriell ausgegeben. Die Schalter befinden sich zunächst in Stellung : Damit werden im Codewort zunächst die Datenbits direkt ausgegeben und gleichzeitig in das LFSR geschoben. Sind alle Datenbits eines Datenwortes eingelesen, wechseln die beiden Schalter in Stellung : Es wird nun bitweise der Inhalt des LFSR ausgegeben, der den Paritätsbits entspricht. Sind alle Prüfstellen ausgegeben, wiederholt sich der Vorgang. Zur Vereinfachung sind die nötigen Taktleitungen und Synchronisationsschaltungen nicht dargestellt.
Der Hamming-Decoder gestaltet sich ähnlich: Der empfangene, serielle Bitdatenstrom von den Codewörtern wird in ein entsprechendes LFSR geschoben und gleichzeitig in einer separaten Schieberegisterkette zwecks Latenzanpassung geschoben. Der Inhalt des LFSR beim Decoder dient nach dem kompletten Empfang eines Codewortes als Adresszeiger in einem Syndromspeicher, welcher meist als eine fixe ROM-Tabelle in der Schaltung realisiert ist. Der Datenausgang des Syndromspeichers wirkt dabei direkt auf den seriellen Datenstrom der Datenbits ein und korrigiert bei Bedarf fehlerhaft erkannte Datenbitstellen durch Invertieren.
Decodierung Bearbeiten
Bei der Decodierung können verschiedene Verfahren angewendet werden, die sich in der Komplexität des Decoders und Decoderleistung unterscheiden. Ein wesentliches Verfahren basiert auf der oben ermittelten Syndromtabelle, die Aufschluss darüber gibt, welche Stelle im Codewort falsch ist. Dies ist bei empfangenen oder gelesenen binären Symbolen ein relativ einfaches Verfahren. Allerdings ist kein allgemeines Verfahren bekannt, mit dem ein linearer Blockcode beliebiger Codewortlänge deterministisch in Polynomialzeit decodierbar wäre. Bei einem (N,n)-Hamming-Code ist der Decodierungsaufwand von der Codewortlänge abhängig und steigt exponentiell. Durch Verwendung des Syndroms bei der Decodierung lässt sich die Anzahl der möglichen Fehlerkombinationen von 2N auf 2n reduzieren. In der Komplexitätstheorie wird die Zeitklasse jener Entscheidungsprobleme als NP-schwer bezeichnet.
Eine weitere Möglichkeit, die Decodierungsleistung zu verbessern, besteht in dem Umstand, dass in realen Nachrichtensystemen der Decoder die einzelnen Codewörter im Regelfall nicht als binäre, sondern als mehrstufige Signale erhält. Die empfangenen analogen Signale werden von einem vorgeschalteten Analog-Digital-Umsetzer zunächst quantisiert. Die entstehenden Abstufungen des Signals zwischen logisch- und logisch- werden vom Decoder als Wahrscheinlichkeiten aufgefasst und das Codewort anhand dieser iterativ konstruiert. Diese Verfahrensweise wird in der meist englischsprachigen Fachliteratur als Soft-Decision bezeichnet und bewirkt einen höheren Codegewinn.
Das Gegenstück dazu ist die sogenannte Hard Decision, die als ein Extremfall der Soft Decision aufgefasst werden kann. Dabei wird das analoge Empfangssignal vor der Decodierung mittels 1-Bit breiten Analog-Digital-Umsetzer, einem „Komparator“, als ein digitales Eingangssignal für die Codewörter abgebildet. Damit ist bereits vor der Decodierung festgelegt, ob ein bestimmtes Bit des empfangenen Codewortes logisch-'1' oder logisch-'0' ist.
Decodierung mittels Hard Decision Bearbeiten
In diesem Fall liegen die empfangenen Codewörter bereits als digitale Folgen vor, weshalb sich der Decodierprozess in einem einstufigen Prozess auf die Auswertung der Syndromtabelle reduziert. Dieses Verfahren wird großteils dann verwendet, wenn der Decoder möglichst einfach gestaltet sein soll und keine „verketteten Codes“, d. h. aus Kombinationen unterschiedlicher Hamming-Codes bestehende, zum Einsatz kommen.
Bei der oben eingeführten Darstellung mittels Kontrollmatrix wurde bereits erläutert, dass das Produkt aus empfangenen Codewort und der Kontrollmatrix bei einem Fehler einen Wert ungleich 0 annimmt:
Durch entsprechende Anordnung der Parity-Stellen, und damit infolge der Form der Kontrollmatrix, lässt sich im einfachsten Fall der Wert dieser Gleichung als Syndrom direkt zur Korrektur der betreffenden Bitstelle verwenden. Wenn diese Gleichung bei -Hamming-Code den Wert 1 liefert, ist genau das erste Bit des empfangenen Codewortes falsch. Bei dem Wert 2 der Gleichung das zweite Bit, und so weiter. Durch Negation der betreffenden Bitstelle im Codewort kann der Fehler korrigiert werden. Im fehlerfreien Fall liefert obige Gleichung den Wert 0, und keine Bitstelle wird korrigiert.
Diese einfache Übereinstimmung von Syndromwert zu fehlerhafter Bitstelle ist bei einem Hamming-Code nur dann der Fall, wenn sich die einzelnen Paritätsbits genau an den Positionen im Codewort befinden, welche Zweierpotenzen darstellen. Dies ist bei der eingangs dargestellten Generatormatrix der Fall. Damit entfällt eine Syndromtabelle (ROM-Tabelle), die erst den jeweiligen Wert der Gleichung von Kontrollmatrix und Codewort auf eine bestimmte Bitposition umsetzt. Diese Vereinfachung für die Decodierung ist auch der Grund, warum Hamming-Codes in Beispielen meistens in der oben dargestellten Form der Generatormatrix vorgenommen werden.
Zur Decodierung des oben dargestellten separierbaren -Hamming-Code mit seiner Kontrollmatrix ′ ist hingegen zur Ermittlung der fehlerhaften Stelle im Codewort eine Umsetzung des Wertes aus der Prüfgleichung notwendig. Im fehlerfreien Fall liefert die Prüfgleichung, so wie bei allen Hamming-Codes, den Wert 0. Im Fehlerfall liefert sie einen Wert ungleich 0, welcher nicht der fehlerhaften Bitstelle im Codewort entsprechen zu entsprechen braucht. Die Umsetzung auf die fehlerhafte Bitstelle kann mittels eines ROM-Speichers erfolgen, dessen Adressen den Wert der Prüfmatrix erhält, und die Datenausgänge angeben, welche Bitstelle durch Invertierung zu korrigieren ist. Im Fall des oben angegebenen, separierbaren -Hamming-Code muss der ROM-Speicher folgenden Dateninhalt haben:
| Eingabewert (ROM-Speicheradresse) | Ausgabewert (Fehlerhafte Bitposition im Codewort) |
|---|---|
| 0 | 0 |
| 1 | 5 |
| 2 | 6 |
| 3 | 1 |
| 4 | 7 |
| 5 | 2 |
| 6 | 3 |
| 7 | 4 |
Pseudocode Bearbeiten
Das folgende Beispiel in Pseudocode zeigt eine Funktion, die den Hamming-Code für das gegebene Datenwort der Länge n erzeugt und gibt ihn als Array zurück. Der Hamming-Code hat n Datenbits und k Paritätsbits.
/** * hammingCode // Array für den Hamming-Code * index // Position des Paritätsbits * numberOfSetBits // Anzahl der gesetzten Bits */ function createHammingCode(dataWord, n, k) { for i := 0 to k - 1 do // for-Schleife, die die Position der Paritätsbits ermittelt { index := 2 ^ i - 1 hammingCode[index] := -1 // Setzt die Paritätsbits auf -1, um sie identifizieren zu können } j := 0 for i := 0 to k + n - 1 do // for-Schleife, die die Bits des Hamming-Code durchläuft { if (hammingCode[i] <> -1) // Wenn Datenbit, also kein Paritätsbit { hammingCode[i] := dataWord[j] // Setzt die Datenbits des Hamming-Code j := j + 1 } } for i := 0 to k + n - 1 do // for-Schleife, die die Bits des Hamming-Code durchläuft { if (hammingCode[i] <> -1) // Wenn Paritätsbit { index := log2(i + 1) // Logarithmus zur Basis 2 numberOfSetBits := 0 for j := i + 2 to k + n do { if (das Bit von j an der Position index ist gesetzt) { if (das Bit des Hamming-Code ist ebenfalls gesetzt) { numberOfSetBits := numberOfSetBits + 1 // Variable für die Anzahl der gesetzten Bits um 1 erhöhen } } } hammingCode[i] := numberOfSetBits mod 2 // Setzt die Paritätsbits des Hamming-Code für gerade Parität } } return hammingCode // Gibt den Array mit dem Hamming-Code zurück } Erweiterter Hamming-Code Bearbeiten
Da der Hamming-Code nur einen Bitfehler pro Datenwort erkennen und korrigieren kann und zwei Bitfehler pro Datenwort bei dem Decoder zu einem falschen Codewort führen, besteht der Wunsch, diese Eigenschaften zu verbessern. Dieser Code wird als „erweiterter Hamming-Code“ (englisch extended Hamming Code) bezeichnet. Dazu wird bei dem Hamming-Code ein weiteres Paritätsbit angefügt, in das alle binären Stellen des nicht erweiterten Hamming-Code einfließen. Damit wird beispielsweise aus dem -Hamming-Code ein erweiterter -Hamming-Code.
Die Erweiterung eines allgemeinen Blockcodes um eine zusätzliche Kontrollstelle ist nur sinnvoll, wenn das „Codegewicht“ ungerade ist, da nur dann zusätzliche Information in diesem zusätzlichen Kontrollbit vorhanden ist. Dies ist bei Hamming-Codes mit einem Codegewicht von 3 immer erfüllt. Damit wird der Hamming-Abstand bei dem erweiterten Hamming-Code von 3 auf 4 erhöht, und der erweiterte Hamming-Code kann folgende Fehler pro Codewort erkennen bzw. korrigieren:
- Er kann beliebig positionierte einzelne Bitfehler erkennen und korrigieren. In diesem Fall ist der Syndromwert ungleich und das zusätzliche Paritätsbit .
- Er kann beliebig positionierte zweifache Bitfehler erkennen, aber nicht mehr korrigieren. In diesem Fall ist der Syndromwert ungleich und das zusätzliche Paritätsbit .
- Er kann alle dreifachen Bitfehler entweder als ungültiges Codewort erkennen und weist bei der Decodierung ein gültiges Codewort zu, das nicht gesendet wurde, oder erkennt dreifache Bitfehler, die nicht korrigiert werden können. Welcher Fall eintritt, hängt von den Positionen der drei Bitfehler im Codewort ab. Im ersten Fall ist der Syndromwert ungleich und das zusätzliche Paritätsbit , im zweiten Fall ist der Syndromwert und das zusätzliche Paritätsbit .
- Vierfache Bitfehler eines Codewortes werden entweder als ungültiges und korrigierbares Codewort, wie im ersten Punkt erkannt, und einem gültigen Codewort zugewiesen, das nicht gesendet wurde. Oder es wird unmittelbar ein gültiges Codewort, welches gar nicht gesendet wurde, empfangen. Welcher Fall eintritt, hängt auch in diesem Fall davon ab, an welchen Bitpositionen im Codewort die Bitfehler auftreten. Im ersten Fall ist der Syndromwert ungleich und das zusätzliche Paritätsbit . Im zweiten Fall ist der Syndromwert und das zusätzliche Paritätsbit , was einem gültigen Codewort entspricht. In allen Fällen werden bei vierfachen Bitfehlern andere als die gesendeten Codewörter ausgegeben, was als Decodierversagen bezeichnet wird.
Für den Decoder von erweiterten Hamming-Codes, welcher nur mittels Hard-Decision arbeitet, lässt sich damit folgende Wahrheitstabelle aufstellen, nach deren Eingangsgrößen in Form des Syndromvektors und der zusätzlichen Parity-Prüfung der Decoder entscheiden kann, ob kein Fehler, ein korrigierbarer Fehler oder ein nicht korrigierbarer Fehler vorliegt:
| Syndromvektor | zusätzliche Parity-Prüfung | Aktion des Decoders | Empfangenes Codewort |
|---|---|---|---|
| = 0 | 0 | kein Fehler | gültig |
| ≠ 0 | 1 | korrigierbarer Fehler | ungültig |
| = 0 | 1 | korrigierbarer Fehler (im Paritätsbit) | ungültig |
| ≠ 0 | 0 | erkannter, nicht korrigierbarer Fehler | ungültig |
Der erweiterte Hamming-Code ist kein perfekter Code, da nicht mehr alle ungültigen Codewörter eindeutig gültigen Codewörtern zugeordnet werden können. Was in den Fällen mit erkannten aber nicht korrigierbaren Datenfehlern passiert, müssen weitere Verarbeitungsebenen nach dem Hamming-Decoder entscheiden. Weiterhin kann bei drei oder mehr Bitfehlern pro Codewort ein „Decodierversagen“ auftreten. Das heißt, diese Mehrfachfehler werden entweder nicht erkannt oder nicht gesendeten gültigen Codewörtern zugewiesen. Dies ist vor allem bei Hamming-Codes mit langen Codewörtern zu beachten, da sich dieses Verhalten durch Wahl der Codewortlänge nicht verändert.
Anwendung findet der erweiterte Hamming-Code beispielsweise als sogenannter „innerer Blockcode“ in Turbo-Product-Codes, wie sie in drahtlosen Funknetzen zur Datenübertragung nach dem Standard IEEE 802.16 im Rahmen von WiMAX auf der Funkschnittstelle verwendet werden.
Codeverkürzung Bearbeiten
Sowohl der Hamming-Code als auch der erweiterte Hamming-Code können in der Länge ihrer Codewörter verkürzt werden, um in Anwendungen Codewörter mit bestimmter, fester Länge zu erhalten. Dies wird als Codeverkürzung bezeichnet. Alle Hamming-Codes weisen, wie dargestellt, nur vergleichsweise wenige wählbare Codewortlängen in groben Schrittweiten zu auf, wobei ganzzahlig und größer 1 gewählt werden muss. Dazwischenliegende Codewortlängen sind bei dem Hamming-Code nicht möglich.
Durch das Verfahren der Codeverkürzung werden Codewortlängen zwischen diesen einzelnen groben Stufen wählbar, allerdings wird dieser Vorteil je nach Verfahren entweder durch ein schlechteres Verhältnis von Datenbitstellen (Nutzdaten) zur Anzahl der Kontrollstellen im Codewort erkauft, oder es wird durch das Verfahren die Mindestdistanz des Codes und damit seine Korrekturleistung reduziert.
Zur Codeverkürzung können grundsätzlich bei allen Codes folgende Verfahren zur Anwendung kommen:
- Es werden auf Seite des Encoders nur jene möglichen Codewörter ausgewählt und anschließend als gültige Codewörter verwendet, die an den ersten oder letzten Stellen des Codewortes immer logisch- sind. Je nach gewünschter resultierender Codewortlänge wird eine entsprechende Anzahl an Stellen ausgewählt, zwischen Encoder und Decoder vereinbart und im Verfahren nicht mehr geändert. Durch den Umstand, dass die weggelassenen Stellen immer bekannte Werte aufweisen, brauchen sie nicht mehr übertragen bzw. gespeichert zu werden: Das resultierende Codewort ist in seiner Länge verkürzt. Bei diesem Verfahren bleibt die Mindestdistanz des Hamming-Code von drei und somit seine Korrekturleistung erhalten. Es stellt sich allerdings ein ungünstigeres Verhältnis von Datenbitanteil zum Kontrollbitanteil im Codewort ein. Dies bedeutet, dass jene verkürzten Hamming-Codes einen größeren Anteil von Kontrollstellen (Paritätsbits) im Codewort aufweisen, als im Optimum bei Hamming-Codes mit unverkürzten Codewortlänge nötig wäre.
- Es werden ausgewählte Stellen des Codewortes auf Seite des Encoder punktiert, das heißt gelöscht und auf einen festen Wert von entweder logisch- oder logisch- gesetzt. Durch den Umstand des festen Wertes brauchen die entsprechenden Binärstellen nicht mehr übertragen bzw. gespeichert zu werden, es ergibt sich eine entsprechende Längenreduktion des resultierenden Codewortes. Je nach Wahl der Stellen im Codewort ergeben sich unterschiedlich starke Reduktionen der Mindestdistanz des Codes. Da bei Hamming-Codes der Mindestabstand immer drei ist, würde eine Punktierung zu einem vollständigen Verlust der Korrekturleistung führen. Punktierungen haben daher bei Blockcodes wie dem Hamming-Code keine praktische Bedeutung und finden sich typischerweise bei Faltungscodes mit entsprechend hohen Mindestabstand.
Praktische Anwendungen von verkürzten und erweiterten Hamming-Codes finden sich beispielsweise bei der Korrektur von einfachen Speicherfehlern und der sicheren Detektion von zweifachen Speicherfehlern pro Adresse bei DRAM-Speichern. Diese kostengünstigen Speicher benötigen pro Bit nur einen kleinen Kondensator zur Datenspeicherung, und es kann durch Störeffekte relativ leicht zur Bitfehlern kommen. Handelsübliche Speichermodule weisen pro Speicheradresse eine Datenbusbreite von typischerweise 36 Bit oder 72 Bit auf – beides sind Werte, die nicht direkt durch entsprechende Codewortlängen des Hamming-Codes erreicht werden können.
Durch die Codeverkürzung nach dem ersten Verfahren kann relativ einfach ein verkürzter Hamming-Code mit genau passender Codewortlänge konstruiert werden. In Applikationsschriften der Firma Xilinx zur Fehlerkorrektur mittels Hamming-Codes wird von einem erweiterten Hamming-Code mit den Parametern als Basis ausgegangen. Daraus wird ein verkürzter Hamming-Code gebildet, dessen Codewortlänge exakt der Datenbusbreite des DRAM-Speichermoduls entspricht und 64 Nutzdatenbits pro Adresse speichern kann. Dabei werden alle Paritätsbits des Hamming-Codes in das auf 72 Stellen verkürzte Codewort übernommen. Die Datenbitstellen 65 bis 120 sind immer auf logisch- gesetzt und werden nicht gespeichert.
Weitere Zahlensysteme Bearbeiten
Bei dem im Artikel vorgestellten binären Hamming-Code gibt es nur zwei mögliche Zustände pro Stelle des Datenwortes oder Codewortes (genau das bedeutet „binär“). In der Zahlentheorie wird dieser Umstand mittels Galois-Körpern der Charakteristik zwei, abgekürzt GF(2), ausgedrückt. Besondere Eigenschaft aller binärer, fehlerkorrigierender Codes ist, dass bereits die Ermittlung der Fehlerposition zur Fehlerkorrektur ausreicht: Da nur zwei mögliche Zustände pro Stelle existieren, kann ein Fehler mit ermittelter Position immer durch Inversion (0 ↔ 1) der betreffenden Stelle korrigiert werden.
Neben den binären Hamming-Code gibt es auch Verallgemeinerungen auf weitere, höhere Zahlensysteme wie beispielsweise den ternären Hamming-Code in GF(3). Der ternäre Hamming-Code weist pro Stelle drei Zustände auf: . Zur Fehlerkorrektur ist bei allen nicht-binären Codes, neben der Lokalisierung der Fehlerposition, auch eine zusätzliche Information nötig, auf welche der anderen Möglichkeiten eine bestimmte Stelle geändert werden muss.
Allgemein lassen sich auch Hamming-Codes auf Galois-Körpern bilden, wobei eine Primzahlpotenz sein muss, d. h. mit eine Primzahl und .
Vereinfachte Variation mit Beispiel Bearbeiten
Eine starke Vereinfachung bietet die folgende Hamming-Code-Variante, hier werden die benötigten Hamming-Bits einfach angehängt, auch entfällt das Umdrehen der Binärzahl.
Beispiel Übertragung: Dezimalzahl 86 (gespeichert in 8 Bits) soll übertragen werden. 86 = 01010110
→ Hamming-Bits werden benötigt.
01010110 hat 1er Bits an den Stellen (von rechts gezählt): 2, 3, 5 und 7
Aufschreiben der Stellen der 1er Bits binär untereinander und mit Parität ergänzen. D.h. jede Spalte muss eine gerade Anzahl an 1er Bits haben.
0010 (= 2. Stelle)
0011 (= 3. Stelle)
0101 (= 5. Stelle)
0111 (= 7. Stelle)
......
0011 (ergänzt, so dass in jeder Spalte eine gerade Anzahl 1er ist)
Übertragene Daten mit Hamming-Code:
01010110|0011
Binärzahl|Hamming-Bits
Beispiel Fehlersuche: Empfangen wurde 01000110|0011
Hamming-Code neu berechnen: 01000110 hat 1er an Stellen: 2,3,7
0010 (= 2. Stelle)
0011 (= 3. Stelle)
0111 (= 7. Stelle)
0011 (= übertragener Hamming-Code)
......
0101 → da nicht 0000, sondern 0101 = 5 → 5. Bit falsch
01010110|0011 = 86 von oben [der Hamming-Code konnte den 1 Bit Fehler korrigieren]
Vergleich mit dem originalen Hamming-Code:
Beim ursprünglichen Hamming-Code funktioniert das Aufschreiben der Stellen zur Feststellung der Parität genauso, allerdings müssen die Bits vorher an die richtige Stelle gesetzt werden. Zum Beispiel von oben:
86 = 01010110 -> 0101?011?0?? (die ? stehen jeweils für das Hamming-Bit)
1er Bits haben wir an den Stellen: 5, 6, 9, 11
0101 (= 5. Stelle)
0110 (= 6. Stelle)
1001 (= 9. Stelle)
1011 (= 11. Stelle)
......
0001 (ergänzt, so dass in jeder Spalte eine gerade Anzahl 1er ist)
Hamming-Code original [ohne umdrehen der Bitfolge]:
010100110001
Die vereinfachte Variation hat allerdings eine Schwäche, die der originale Hamming Code nicht hat: Sie kann einen Fehler in den Datenbits nicht von einem Fehler in den Hamming-Code-Bits unterscheiden, vgl. die folgenden 2 Beispiele:
Beispiel Fehlersuche mit Fehler im 4. Datenbit: Empfangen wurde 01011110|0011
Hamming-Code neu berechnen: 01011110 hat 1er an Stellen: 2,3,4,5,7
0010 (= 2. Stelle)
0011 (= 3. Stelle)
0100 (= 4. Stelle)
0101 (= 5. Stelle)
0111 (= 7. Stelle)
0011 (= übertragener Hamming-Code)
......
0100 → da nicht 0000, sondern 0100 = 4 → Hier wird das 4. Bit als falsch erkannt.
01010110|0011 = 86 von oben [der Hamming-Code konnte den 1 Bit Fehler korrigieren]
Beispiel Fehlersuche mit Fehler im 3. Hamming-Code-Bit: Empfangen wurde 01010110|0111
Hamming-Code neu berechnen: 01010110 hat 1er an Stellen: 2,3,5,7
0010 (= 2. Stelle)
0011 (= 3. Stelle)
0101 (= 5. Stelle)
0111 (= 7. Stelle)
0111 (= übertragener Hamming-Code)
......
0100 → da nicht 0000, sondern 0101 = 4 → 4. Hier erkennt der Algorithmus ebenfalls einen Fehler im 4. Datenbit.
01011110|0111 = 94 Die Anwendung des Korrekturalgorithmus führt hier zu einem Fehler im Datenbit an Stelle zu einer Korrektur des Hamming-Code-Bits.
Literatur Bearbeiten
- Martin Bossert: Kanalcodierung. 2. vollständig neubearbeitete und erweiterte Auflage. Teubner, Stuttgart 1998, ISBN 3-519-16143-5 (Informationstechnik).
- Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms. John Wiley & Sons, Hoboken NJ 2005, ISBN 0-471-64800-0.
- André Neubauer: Kanalcodierung. Eine Einführung für Ingenieure, Informatiker und Naturwissenschaftler. J.Schlembach Fachverlag, Wilburgstetten 2006, ISBN 3-935340-51-6.
- Hermann Rohling: Einführung in die Informations- und Codierungstheorie. Teubner, Stuttgart 1995, ISBN 3-519-06174-0 (Teubner Studienbücher – Elektrotechnik).
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- Richard W. Hamming: Error Detection and Error Correction Codes. In: The Bell System Technical Journal, Vol. XXIX 2, 1950, Seite 147–160.
- Fehlererkennung mittels verkürztem Hamming-Code. (PDF; 184 kB) Firmenschrift (englisch)