f.fritze

In diesem Beitrag wird der Hamming-Code zunächst mit sieben Münzen und ohne Computer aufgebaut und praktisch erprobt. Dabei lernst du, wie Prüfbits Fehler in einer übertragenen Bitfolge erkennen und die fehlerhafte Position bestimmen können. Anschließend wird das Verfahren in einem Jupyter Notebook mit Python programmiert.

Wenn Daten unterwegs verändert werden

Bei der Übertragung digitaler Daten kann es passieren, dass sich einzelne Bits verändern. Aus einer 0 wird eine 1 oder umgekehrt, ohne dass der Empfänger dies zunächst bemerkt. Der Hamming-Code ergänzt die eigentlichen Daten deshalb um zusätzliche Prüfbits. So lässt sich nicht nur erkennen, dass ein Fehler aufgetreten ist, sondern auch, an welcher Stelle er sich befindet.

Den Hamming-Code aufbauen

Der Hamming-Code besteht in der hier verwendeten Variante aus sieben Bits: vier Datenbits und drei Prüfbits. Die Datenbits stehen an den Positionen 3, 5, 6 und 7, während die Prüfbits an den Positionen 1, 2 und 4 platziert werden. Jedes Prüfbit kontrolliert eine bestimmte Gruppe von vier Positionen und wird so gewählt, dass diese Gruppe eine gerade Anzahl von Einsen enthält. Wird später ein Bit verändert, zeigt das Muster der fehlerhaften Prüfungen die Position des falschen Bits an.

Material: Hamming-Code mit Münzen

Für die Durchführung werden sieben Hamming-Münzen und eine passende Vorlage benötigt. Die Münzen sind für den 3D-Druck vorgesehen; die Druckdateien stehen als ZIP-Datei im STL- und 3MF-Format zum Download bereit.

Die Vorlage mit den Positionen und Prüfgruppen kann als PDF-Datei heruntergeladen und ausgedruckt werden.

Für den Aufbau des Hamming-Codes werden sieben Münzen benötigt. Die vier Datenbits $d_0$ bis $d_3$ werden durch blaue Münzen dargestellt, die drei Prüfbits $p_0$ bis $p_2$ durch orange Münzen. Jede Münze zeigt auf einer Seite eine 0 und auf der anderen Seite eine 1.

Lege zunächst die vier blauen Datenmünzen auf die Positionen 3, 5, 6 und 7. Wähle für jede Münze zufällig eine Seite und notiere damit die Datenbits $d_0$ bis $d_3$.

Die drei orangefarbenen Prüfmünzen werden anschließend auf die Positionen 1, 2 und 4 gelegt.

Jedes Prüfbit kontrolliert eine bestimmte Gruppe von Positionen. $p_0$ prüft die Positionen 1, 3, 5 und 7, $p_1$ die Positionen 2, 3, 6 und 7 und $p_2$ die Positionen 4, 5, 6 und 7.

Wähle die Seiten der orangefarbenen Münzen so, dass in jeder dieser Prüfgruppen eine gerade Anzahl von Einsen liegt. Dabei wird das jeweilige Prüfbit immer mitgezählt.

Damit ist ein gültiger Hamming-Code aufgebaut. Die sieben Münzen enthalten nun vier Datenbits und drei Prüfbits. Wird später eine Münze umgedreht, lässt sich anhand der Prüfgruppen feststellen, ob ein Fehler aufgetreten ist und an welcher Position sich das veränderte Bit befindet.

Fehler erkennen, lokalisieren und korrigieren

Nachdem der Hamming-Code auf der Vorlage aufgebaut wurde, wird zunächst überprüft, ob alle drei Prüfgruppen eine gerade Anzahl von Einsen enthalten. $p_0$ umfasst die Positionen 1, 3, 5 und 7, $p_1$ die Positionen 2, 3, 6 und 7 sowie $p_2$ die Positionen 4, 5, 6 und 7. Das jeweilige Prüfbit wird bei der Kontrolle mitgezählt.

Nun wird heimlich eine beliebige Münze umgedreht. Anschließend werden die drei Prüfgruppen erneut kontrolliert. Enthält eine Prüfgruppe eine ungerade Anzahl von Einsen, zeigt dies, dass sich an einer der zugehörigen Positionen ein Fehler befindet.

Das Muster der fehlerhaften Prüfgruppen gibt schließlich die genaue Position des veränderten Bits an. Sind beispielsweise die Prüfgruppen von $p_0$ und $p_1$ fehlerhaft, liegt der Fehler an Position 3, da diese Position in beiden Prüfgruppen enthalten ist.

Wird keine fehlerhafte Prüfgruppe gefunden, wurde keine Münze verändert. Ist die fehlerhafte Position bestimmt, wird die entsprechende Münze erneut umgedreht. Damit ist der einzelne Bitfehler korrigiert und der ursprüngliche Hamming-Code wiederhergestellt. Anschließend kann untersucht werden, wie sich das Verfahren bei mehreren gleichzeitig veränderten Bits verhält.

Grenzen des Verfahrens

Der Hamming-Code kann in dieser Form einen einzelnen Bitfehler erkennen, lokalisieren und korrigieren. Bei mehreren gleichzeitig veränderten Bits oder Zahlendrehern ist eine zuverlässige Fehlerkorrektur jedoch nicht mehr garantiert.

Drei Prüfblicke zeigen den Weg zum Fehler

Das Verfahren funktioniert, weil jede der sieben Positionen eine eigene dreistellige Binärdarstellung besitzt: Position 1 entspricht 001, Position 2: 010, Position 3: 011 und so weiter bis Position 7 mit 111. Die drei Prüfbits kontrollieren jeweils eine Stelle dieser Binärdarstellungen. Dabei prüft $p_0$ die letzte Stelle, $p_1$ die mittlere Stelle und $p_2$ die erste Stelle.

Wird eine Münze umgedreht, verändert sich die Anzahl der Einsen in genau den Prüfgruppen, zu denen diese Position gehört. Die betroffenen Prüfgruppen liefern dadurch die einzelnen Stellen der Binärdarstellung der Fehlerposition. Sind beispielsweise $p_0$ und $p_1$ fehlerhaft, während $p_2$ korrekt bleibt, ergibt sich 011 – also die Binärdarstellung der Position 3.

Die drei Prüfergebnisse bilden somit gemeinsam ein sogenanntes Prüfmuster. Dieses Prüfmuster ist nichts anderes als die Binärzahl der fehlerhaften Position. Deshalb kann der Hamming-Code einen einzelnen Bitfehler nicht nur erkennen, sondern auch eindeutig lokalisieren und durch erneutes Umdrehen der entsprechenden Münze korrigieren.

Implementierung mit Python

Das bisher mit Münzen und der Vorlage durchgeführte Verfahren lässt sich auch mit Python umsetzen. In einem Jupyter Notebook werden die Datenbits, Prüfbits und Prüfgruppen durch Listen und Berechnungen dargestellt.

Anschließend kann ein einzelner Bitfehler simuliert, anhand des Prüfmusters lokalisiert und automatisch korrigiert werden. Das Jupyter Notebook zum Hamming-Code enthält die entsprechende Python-Implementierung und kann direkt im Browser ausgeführt werden.

Hamming-Code mit mehr Bits

Der Hamming-Code lässt sich auch auf längere Bitfolgen erweitern.

Dazu werden zusätzliche Prüfbits an den Positionen eingefügt, die Potenzen von 2 entsprechen, also an den Positionen 1, 2, 4, 8, 16 und so weiter. Je mehr Datenbits übertragen werden, desto mehr Prüfbits sind erforderlich: Aus 11 Datenbits entsteht beispielsweise ein 15-Bit-Code mit vier Prüfbits, aus 26 Datenbits ein 31-Bit-Code mit fünf Prüfbits.

Auch bei diesen längeren Codes können die Prüfergebnisse die Binärdarstellung der fehlerhaften Position bilden, sodass ein einzelner Bitfehler erkannt und korrigiert werden kann.

Fazit

Der Hamming-Code zeigt anschaulich, wie zusätzliche Prüfbits dabei helfen, Fehler in digitalen Daten zu erkennen und zu korrigieren. Mit den 3D-gedruckten Münzen lässt sich das Verfahren zunächst ganz ohne Computer aufbauen und praktisch nachvollziehen.

Die anschließende Umsetzung im Jupyter Notebook verdeutlicht, wie aus diesem unplugged Verfahren ein Algorithmus entsteht, der Fehler automatisch lokalisiert und korrigiert.