+2 Daumen
212 Aufrufe


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.
geschlossen: Stack-Artikel
von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

0 Daumen
1 Antwort
+2 Daumen
0 Antworten
+3 Daumen
0 Antworten

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community