Hamming-Code und Hamming-Abstand

Im Rahmen meiner Vorbereitungen auf die Klausur habe ich mich etwas länger als gewünscht mit der Berechnung des Hamming-Codes und des Hamming-Abstands herumschlagen müssen. Der Hamming-Code kann dazu benutzt werden, einfache Fehler in Worten zu finden und zu korrigieren. Wir definieren hier mal zunächst den Hamming-Abstand wie im Skript:

Hamming-Abstand (hd) zwischen zwei Worten ist die Anzahl der der Bitstellen, an denen sich zwei Worte unterscheiden.

Hamming-Abstand (HD) des gesamten Codes ist der Mindestabstand zwischen den einzelnen Worten. D. h. haben wir Worte $w_1$, $w_2$ und $w_1$, so berechnen wir zunächst die Abstände $hd(w_1, w_2)$, $hd(w_1, w_3)$, $hd(w_2, w_3)$ und wählen davon den kleinsten.

Beispiel: $w_1=10110$, $w_2=11010$ und $w_1=01010$. Unser Codewort $C$ ist:

$w_1=10110$
$w_2=11010$
$w_3=01010$

$hd(w_1, w_2)=2$, da sich $w_1$ und $w_2$ an Stellen 2 und 3 unterscheiden.

$hd(w_1, w_3)=3$, da sich $w_1$ und $w_3$ an Stellen 1, 2 und 3 unterscheiden.

$hd(w_2, w_3)=1$, da sich $w_3$ und $w_4$ nur an Stelle 1 unterscheidet.

Damit ist der Hamming-Abstand des gesamten Codes $HD(C)=1$

Berechnung des Hamming-Codes

Wie berechnen wir nun den Hamming-Code eines gegebenen Datenworts? Das ist ebenfalls nicht schwer, lädt aber dazu ein, sich zu verrechnen.

Beispiel: Hamming-Code für $01001101$

1. Festlegeung wie viele Prüfbits benötigt werden: Jedes Bit an Stelle einer Zweierpotenz $(1,2,4,8,16,32, ...)$ wird ein Prüfbit. Wir haben 8 Stellen in unserem Datenwort und brauchen daher 4 Prüfbits. Macht also insg. 12 Bits in unserem neuen Codewort.

2. Damit sieht unser "Platzhalter-Codewort" wie folgt aus:

_ _ 0 _ 1 0 0 _ 1  1  0  1

mit Platzhaltern für Prüfbits $C_1, C_2, C_4$ und $C_8$.

3. Nun schauen wir, was der Inhalt der Prüfbits wird, denn nicht jedes Datenbit geht in die Berechnung eines jeden Prüfbits ein. Wir legen folgendes fest (und das wird nun ein komischer Satz, aber keine Sorge, er wird gleich erklärt): Ein Bit aus dem Datenwort auf Postion $k$ wird nur dann in die Berechnung des Prüfbits $C_i$ einbezogen, wenn die binäre Darstellung von $k$ an Position $log_2(i)$ eine $1$ hat. Puh!

Aber keine Sorge, das entschlüsseln wir gleich. Frage ist: Welche Datenbits aus unserem Datenwort gehen in die Berechnung von $C_1, C_2, C4$ und $C8$ ein? Dazu gehen wir wie folgt vor:

3a. Wir nummerieren die 12 Bits / Stellen unseres "Platzhalter-Codeworts" von links nach rechts:

1 2 3 4 5 6 7 8 9 10 11 12
_ _ 0 _ 1 0 0 _ 1  1  0  1

Z. B. Für Prüfbit $C_1$ muss lt. Definition an Stelle $log_2(1)=0$ der binären Darstellung der Position $k$ im "Platzhalter-Codeworts" eine $1$ stehen, wenn der Wert von der Position $k$ aus dem "Platzhalter-Codeworts" in die Berechnung von $C_1$ einfließen darf. Die Werte für $k$ sind die Positionen der Datenbits (die Prüfbits gehen ja nicht in die Berechnung ein), d. h. $3,5,6,7,9,10,11$ und $12$. Wir stellen also Positionen 3, 5, 6, 7, 9, 10, 11, 12 zunächst in binär dar.

Da wir nun für alle Codeworte $C_i$ prüfen müssen, ob an der betreffenden Stelle $log_2(i)$ eine $1$ steht, nummerieren wir diese Auflistung der Übersichtlichkeit halber (nicht vergessen: hier gilt von rechts nach links):

Binär        8 4 2 1
-------------------- 
Position 03: 0 0 1 1
Position 05: 0 1 0 1
Position 06: 0 1 1 0
Position 07: 0 1 1 1
Position 09: 1 0 0 1
Position 10: 1 0 1 0
Position 11: 1 0 1 1
Position 12: 1 1 0 0
--------------------
Stelle       3 2 1 0

• Wir prüfen für alle Positionen nun für $C_1$, ob an Stelle $log_2(1) = 0$ eine $1$ steht: bei Position 3, 5, 7, 9, 11 steht das. Also gehen Positionen 3, 5, 7, 9 und 11 des "Platzhalter-Codeworts" in die Berechnung von $C_1$ ein.
• Nun ist $C_2$ dran. Die zu prüfende Stelle ist $log_2(2) = 1$. Positiv für Position: 3,6,7,10,11.
• Für $C_4$: Die zu prüfende Stelle ist $log_2(4) = 2$. Positiv für Position: 5,6,7,12.
• $C_8$: Die zu prüfende Stelle ist $log_2(4) = 3$. Positiv für Position: 9,10,11,12.

Ist die Summer der Positionen gerade, so ist $C_i=0$. Ist sie ungerade, so ist $C_i=1$. Hier noch einmal unser "Platzhalter-Codewort" mit nummerierten Stellen:

1 2 3 4 5 6 7 8 9 10 11 12
_ _ 0 _ 1 0 0 _ 1  1  0  1

Wir berechnen nun die Prüfbits.

• $C_1=0$, da $P_3+P_5+P_7+P_9+P_{11}=0+1+0+1+0=2$ (gerade)
• $C_2=1$, da $P_3+P_6+P_7+P_{10}+P_{11}=0+0+0+1+0=1$ (ungerade)
• $C_4=0$, da $P_5+P_6+P_7+P_{12}=1+0+0+1=2$ (gerade)
• $C_8=1$, da $P_9+P_10+P_{11}+P_{12}=1+1+0+1=3$ (ungerade)

4. Nun haben wir unsere Prüfbits berechnet uns setzen sie an entsprechender Stelle in unser "Platzhalter-Codewort" (Prüfbits sind fett):

1 2 3 4 5 6 7 8 9 10 11 12
0 1 0 0 1 0 0 1 1  1  0  1

Damit ist unser gesuchtes Hamming-Codewort: $010010011101$

Beispiel 2: Versucht es mal selbst mit $10011010$

Lösung zeigen

0 1 1 1 0 0 1 0 1 0 1 0

Und wieder zurück

Stellt sich die Frage, wie wir eingeschlichene Fehler wieder beseitigt bekommen. Wir bleiben bei unserem ersten Beispiel und nehmen an, das obige Codewort sei falsch übertragen worden:

1 2 3 4 5 6 7 8 9 10 11 12
0 1 0 0 1 0 0 1 1  1  0  1 (korrektes Codewort)
0 1 0 0 1 0 0 1 0  1  0  1 (falsch übertragenes Codewort, Fehler rot markiert)

1. Wir empfangen das fehlerhafte Codewort und schreiben uns zunächst die Prüfbits $C_i$ und die zugehörigen Bitpositionen zum Prüfbit raus:

• $C_1=0$, es ist aber $P_3+P_5+P_7+P_9+P_{11}=0+1+0+0+0=1$ (ungerade) - Fehler!
• $C_2=1$, es ist $P_3+P_6+P_7+P_{10}+P_{11}=0+0+0+1+0=1$ (ungerade) - OK!
• $C_4=0$, es ist $P_5+P_6+P_7+P_{12}=1+0+0+1=2$ (gerade) - OK!
• $C_8=1$, es ist aber $P_9+P_10+P_{11}+P_{12}=0+1+0+1=2$ (gerade) - Fehler!

2. Wir haben damit in $C_8$ und $C_1$ einen Fehler. $8+1=9$. Der Fehler im Codewort ist also auf in Bit 9!

Gar nicht so schwer, oder?

Datum: 19. Februar 2016
Kategorie: Fernuni
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url