1. Einführung
Der Hamming-Code ist eine Möglichkeit, mit dem Bitfehler bei der Übertragung von Daten detektiert werden können. Es handelt sich um einen linearen Code, mit dem man ein geflipptes Bit erkennen kann, d. h. wenn z. B. bei der Übertragung eine 0 zu einer 1 geworden ist. Mit dem in diesem Artikel vorgestellten Verfahren, kannst du sogar erkennen, wo genau der Fehler aufgetreten ist. Allerdings ist es nicht möglich, mehrere gleichzeitig auftretende Fehler zuverlässig zu erkennen.
2. Berechnung des Hamming-Codes
Stelle dir vor, du willst das ein Byte (also 8-Bit) lange Datenwort
10110100
übertragen. Wie lautet hierfür der Hamming-Code?
Stelle dir vor, du packst die einzelnen Bits in Wagons eines Zugs, den du dann auf seine Reise zum Empfänger schickst. Bestimmte Wagons sind für die Security reserviert, nämlich alle mit einer Zweierpotenz, also
\(2^n\)
Diese Wagons entsprechen im Hamming-Code den sogenannten Paritätsbits, die zur Fehlerkennung herangezogen werden. In diesem Beispiel sind die Wagons mit den Nummern \(2^0=1\), \(2^1=2\), \(2^2=4\) und \(2^3=8\) vorgesehen. Ein weiteres Paritätsbit wird nicht benötigt, da das Datenwort nur \(8\) Bit lang ist und Wagons \(2^4=16\) das nächste Paritätsbit enthalten würde.
Nun teilst du die einzelnen Bits des Datenworts auf die Wagons auf. Wichtig ist dabei, dass die Wagons für die Paritätsbits übersprungen werden, d. h. darin befindet sich am Ende keine Zahl. Die Wagonnummern, in denen sich nun eine 1 befindet, werden in Binärzahlen umgerechnet. Wie du das machst, erfährst du in diesem Artikel.
Für dieses Beispiel musst du \(6\), \(9\), \(10\) und \(12\) in Binärzahlen umrechnen und erhältst \(0110\), \(1001\), \(1010\) und \(1100\). Nun addierst du diese Zahlen binär. Achte aber darauf, dass du den Übertrag hier nicht mitziehst. D. h. du addierst zunächst \(0\), \(1\), \(0\) und \(0\) und erhältst als Ergebnis \(1\). Danach addierst du \(1\), \(0\), \(1\) und \(0\) und erhältst als Ergebnis \(0\). Der Übertrag wird hier nicht mitgezogen! Für die nächste Stelle gilt dann \(1\) plus \(0\) plus \(0\) plus \(1\) und das ergibt \(0\). Als letztes addierst du die führenden Stellen und erhältst als Ergebnis \(1\). Letztendlich prüfst du auf diese Weise für jede Spalte nur, ob die Anzahl der Einsen gerade oder ungerade ist. Ist sie gerade, so trägst du eine \(0\) und ansonsten eine \(1\) ein. Die Bits der so entstandenen Bitsequenz entsprechen den einzelnen Paritätsbits. D. h. du trägst nacheinander \(1\), \(0\), \(0\) und \(1\) in die für die Paritätsbits vorgesehenen Wagons ein. Das, was nun in den Wagons des Zuges steht, ist der Hamming-Code.
3. Die Überprüfung des Hamming-Codes
Dieser Zug wird nun zum Ziel geschickt. Doch wie wird am anderen Ende überprüft, ob die Übertragung fehlerfrei funktioniert hat? Hierfür werden wieder die Wagonnummern, in denen sich eine \(1\) befindet, in Binärzahlen umgerechnet und die Ergebnisse ohne Übertrag addiert. Zu den Wagonnummern \(6\), \(9\), \(10\) und \(12\) kommen diesmal (bedingt durch die Paritätsbits) die Wagons \(1\) und \(8\) hinzu. Die \(1\) entspricht binär \(0001\) und \(8\) dem Ergebnis \(1000\). Du erhältst als Ergebnis \(1+0+0+1+0+0=0\), \(0+1+0+0+1+0=0\), \(0+1+0+0+0+1=0\) und \(0+0+1+1+1+1=0\). Immer dann, wenn alle Bits bei der Überprüfung \(0\) sind, sind die Daten fehlerfrei übertragen worden. Das gilt aber nur, wenn es lediglich einen Bitfehler gab, aber davon gehst du in diesem Fall aus.
Diese Nachricht wird nun an einen weiteren Empfänger weitergeleitet, der dann dieses Ergebnis bekommt: $$101110000001$$ Zur Kontrolle, ob die Nachricht korrekt empfangen wurde, gehst du wie bei dem vorangegangenen Beispiel vor. Zuerst übersetzt du die Nummern aller Wagons, in denen sich eine \(1\) befindet, in Binärzahlen, hier also \(1\), \(8\), \(9\), \(10\) und \(12\). Anschließend addierst du alle übersetzten Zahlen binär ohne Übertrag und erhältst \(1+0+1+0+0=0\), \(0+0+0+1+0=1\), \(0+0+0+0+1=1\) und \(0+1+1+1+1=0\). Wie du siehst, sind in dem Ergebnis Einsen enthalten, d. h. bei der Übertragung ist ein Fehler aufgetreten. Doch wo? Nun, darüber gibt dir die berechnete Binärzahl \(0110\) Auskunft. Wenn du diese ins Dezimalsystem übersetzt, erhältst du die \(6\) und das ist der Wagon, in dem ein Bitflip stattgefunden hat. Vor der zweiten Übertragung stand dort nämlich eine \(1\).
Autor: Florian André Dalwigk
Dieser Artikel hat 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
