Hamming-Code

Die ${\displaystyle k}$ 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-${\displaystyle 1}$ der in die jeweilige Kontrollstelle eingerechneten Datenbitstellen eine gerade Anzahl, ist das jeweilige Paritätsbit logisch-${\displaystyle 0}$. Ist die Anzahl der logisch-${\displaystyle 1}$ in den Datenbitstellen eine ungerade Anzahl, wird das jeweilige Paritätsbit auf logisch-${\displaystyle 1}$ gesetzt, so dass sich in Summe in den Datenbitstellen und den Paritätsbit, immer eine gerade Anzahl von logisch-${\displaystyle 1}$ 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:

1. Im Codewort befinden sich an denjenigen Positionen, die Zweierpotenzen sind (1, 2, 4, 8, 16, …), die einzelnen Paritäts-Kontrollbits p.
2. Die Datenbits d des zu übertragenden Datenwortes werden dazwischen auf den freien Stellen im Codewort von links aufsteigend eingetragen.

Sind ${\displaystyle p_{1},p_{2},\ldots ,p_{k}}$Paritätsbits, ${\displaystyle d_{1},d_{2},\ldots ,d_{N-k}}$ Bits des Datenwortes und ${\displaystyle c_{1},c_{2},\ldots ,c_{N}}$ 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):

Anordnung der Paritäts-Kontrollstellen p₁…p_k und der Datenbits d₁…d_N-k in einem Codewort mit den Stellen c₁…c_N für die im Folgenden dargestellte Bitanordnung.

In das erste Paritätsbit ${\displaystyle p_{1}}$ wird jedes zweite Datenbit, bei ${\displaystyle c_{3}}$ 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:

${\displaystyle c_{1}=p_{1}=c_{3}\oplus c_{5}\oplus c_{7}\oplus c_{9}\oplus c_{11}\oplus c_{13}\oplus c_{15}\oplus c_{17}\oplus c_{19}\oplus \cdots }$

Das Symbol ${\displaystyle \oplus }$ 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 ${\displaystyle p_{2}}$ wird das rechts von p₂ im Codewort stehende Bit ${\displaystyle c_{3}}$ einberechnet, dann zwei Stellen im Codewort übersprungen, die nächsten zwei Bit ${\displaystyle c_{6}}$ und ${\displaystyle c_{7}}$ 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 ${\displaystyle p_{2}}$ die Bildungsvorschrift:

${\displaystyle c_{2}=p_{2}=c_{3}\oplus c_{6}\oplus c_{7}\oplus c_{10}\oplus c_{11}\oplus c_{14}\oplus c_{15}\oplus c_{18}\oplus c_{19}\oplus \cdots }$

In das dritte Paritätsbit p₃ 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 ${\displaystyle p_{3}}$:

${\displaystyle c_{4}=p_{3}=c_{5}\oplus c_{6}\oplus c_{7}\oplus c_{12}\oplus c_{13}\oplus c_{14}\oplus c_{15}\oplus c_{20}\oplus \cdots }$

Das Paritätsbit ${\displaystyle p_{i}}$ wird also über alle Stellen c_j des Codeworts berechnet, in denen an der ${\displaystyle i}$-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 ${\displaystyle (7,4)}$-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 ${\displaystyle H}$, 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 ${\displaystyle H}$ dann logisch-${\displaystyle 1}$ 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.

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 ${\displaystyle G}$ und damit verbunden andere Kontrollmatrix ${\displaystyle H}$ gekennzeichnet.

Der kürzeste Hamming-Code ist der ${\displaystyle (3,1)}$-Hamming-Code. Dabei wird ein Nutzdatenbit einem drei Bit langen Codewort zugeordnet. Mit obiger allgemeiner Berechnung ergibt sich, dass die beiden „Paritätsbits“ ${\displaystyle p_{1}}$ und ${\displaystyle p_{2}}$ nur in diesem Fall direkt dem einen Nutzdatenbit entsprechen. Es kann nur die beiden gültigen Codewörter ${\displaystyle 000}$ und ${\displaystyle 111}$ geben. Die ungültigen Codewörter ${\displaystyle 001}$, ${\displaystyle 010}$ und ${\displaystyle 100}$ werden bei der Decodierung mittels des Verfahrens der Mehrheitsentscheidung dem Codewort ${\displaystyle 000}$ zugewiesen. ${\displaystyle 110}$, ${\displaystyle 101}$ und ${\displaystyle 011}$ dem Codewort ${\displaystyle 111}$. Damit ist der ${\displaystyle (3,1)}$-Hamming-Code als ein Spezialfall gleich einem Wiederholungscode mit einer Länge von 3. Der ${\displaystyle (3,1)}$-Hamming-Code ist auch der einzige Hamming-Code, der nur durch die Angabe ${\displaystyle (3,1)}$ eindeutig im Aufbau des Codewortes spezifiziert ist.

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).

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:

${\displaystyle \mathbf {c} =\mathbf {G} \cdot \mathbf {d} }$

Aus dieser Gleichung ergibt sich mit der im vorherigen Abschnitt dargestellten Bildungsvorschrift, und den Rechenregeln für Matrizen für einen nicht separierbaren ${\displaystyle (7,4)}$-Hamming-Code, die folgende Generatormatrix ${\displaystyle G}$:

${\displaystyle \mathbf {G}$ :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\{\color {Brown}1}&{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}0}\\0&1&1&1\\{\color {Brown}0}&{\color {Brown}1}&{\color {Brown}0}&{\color {Brown}0}\\{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}1}&{\color {Brown}0}\\{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}0}&{\color {Brown}1}\\\end{pmatrix}}}

Die ersten beiden Zeilen der Matrix bilden die ersten beiden Paritätsbits ${\displaystyle p_{1}}$ und ${\displaystyle p_{2}}$ 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 ${\displaystyle d_{n}}$ im Codewort ab. Die vierte Zeile bildet das dritte Paritätsbit ${\displaystyle p_{3}}$.

Aus der Generatormatrix lässt sich direkt die Kontrollmatrix ${\displaystyle H}$ 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 ${\displaystyle c}$ ist:

${\displaystyle \mathbf {H} \cdot \mathbf {c} =\mathbf {0} }$

Für obige Generatormatrix ${\displaystyle G}$ lässt sich die folgende Kontrollmatrix ${\displaystyle H}$ ermitteln:

${\displaystyle \mathbf {H}$ :={\begin{pmatrix}{\color {Brown}1}&{\color {Brown}0}&1&{\color {Brown}0}&1&0&1\\{\color {Brown}0}&{\color {Brown}1}&1&{\color {Brown}0}&0&1&1\\{\color {Brown}0}&{\color {Brown}0}&0&{\color {Brown}1}&1&1&1\\\end{pmatrix}}}

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:

${\displaystyle \mathbf {H} \cdot \mathbf {c} \neq \mathbf {0} }$

Durch den Wert dieser Gleichung kann über eine Syndromtabelle die fehlerhafte Bitstelle eindeutig bestimmt und durch Invertieren korrigiert werden.

Eine spielerische Anwendung speziell des ${\displaystyle (7,4)}$-Hamming-Codes findet man bei der Lösung von Eberts Hutproblem.

Aufgrund der Linearität können beliebige Zeilen der Generatormatrix ${\displaystyle G}$ 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 d_n und nachfolgend alle Paritätsbits p_n 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 ${\displaystyle G}$ kann durch Umstellen der Zeilen auf folgende Generatormatrix ${\displaystyle G}$′ so umgeformt werden, dass der ${\displaystyle (7,4)}$-Hamming-Code ein systematischer Code wird. Eine mögliche Generatormatrix des systematischen ${\displaystyle (7,4)}$-Hamming-Codes lautet:

${\displaystyle \mathbf {G'}$ :={\begin{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}}}

Die assoziierte Kontrollmatrix ${\displaystyle H}$′ kann leichter bestimmt werden, denn bei systematischer Blockcodes gilt mit Modulo-2-Operationen:

${\displaystyle \mathbf {H'} \cdot \mathbf {G'} =\mathbf {0} }$

Damit bestimmt sich ${\displaystyle H}$′ zu:

${\displaystyle \mathbf {H'}$ :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\\\end{pmatrix}}}

Die ersten 4 Spalten der Kontrollmatrix ${\displaystyle H}$′ bestehen dabei aus den letzten drei Zeilen der Generatormatrix ${\displaystyle G}$′. Der rechte Teil der Kontrollmatrix ist mit der Einheitsmatrix aufgefüllt.

Damit ist dargestellt, dass nur die Angabe ${\displaystyle (7,4)}$-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.

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:

Bemerkungen:

• z ist eine alternative Schreibweise für z¹: z⁶ + z + 1  →  z⁶ + z¹ + 1
• 1 ist eine alternative Schreibweise für z⁰: z⁶ + z + 1  →  z⁶ + z¹ + z⁰
• Die Anzahl der Terme ist immer ungerade und enthält immer die Potenzen z^k und 1: z⁶ + z + 1
• Man kann immer die Exponenten spiegeln, d. h. alle x^l durch x^k−l ersetzen, es entsteht ein anderer, aber genau funktionierender zyklischer Blockcode: z⁶ + z + 1  →  z⁶ + z¹ + z⁰  →  z⁰ + z⁵ + z⁶  →  z⁶ + z⁵ + 1

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 ${\displaystyle c}$ und der Kontrollmatrix bei einem Fehler einen Wert ungleich 0 annimmt:

${\displaystyle \mathbf {H} \cdot \mathbf {c} \neq \mathbf {0} }$

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 ${\displaystyle (7,4)}$-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 ${\displaystyle G}$ 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 ${\displaystyle G}$ vorgenommen werden.

Zur Decodierung des oben dargestellten separierbaren ${\displaystyle (7,4)}$-Hamming-Code mit seiner Kontrollmatrix ${\displaystyle H}$′ 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 ${\displaystyle (7,4)}$-Hamming-Code muss der ROM-Speicher folgenden Dateninhalt haben: