Im Rahmen meiner Vorbereitungen auf die Klausur habe ich mich etwas l\u00e4nger als gew\u00fcnscht mit der Berechnung des Hamming-Codes und des Hamming-Abstands herumschlagen m\u00fcssen. Der Hamming-Code kann dazu benutzt werden, einfache Fehler in Worten zu finden und zu korrigieren. Wir definieren hier mal zun\u00e4chst den Hamming-Abstand wie im Skript:<\/p>\n
Hamming-Abstand<\/strong> (hd) zwischen zwei Worten ist die Anzahl der der Bitstellen, an denen sich zwei Worte\u00a0unterscheiden.<\/p>\n Hamming-Abstand<\/strong> (HD) des gesamten Codes\u00a0ist der Mindestabstand zwischen den einzelnen Worten. D. h. haben wir Worte $$w_1$$,\u00a0$$w_2$$ und\u00a0$$w_1$$, so berechnen wir zun\u00e4chst die Abst\u00e4nde $$hd(w_1, w_2)$$,\u00a0$$hd(w_1, w_3)$$,\u00a0$$hd(w_2, w_3)$$ und\u00a0w\u00e4hlen davon den kleinsten.<\/p>\n Beispiel<\/strong>:\u00a0$$w_1=10110$$,\u00a0$$w_2=11010$$ und\u00a0$$w_1=01010$$. Unser Codewort $$C$$ ist:<\/p>\n $$w_1=10110$$ $$hd(w_1, w_2)=2$$, da sich $$w_1$$ und $$w_2$$ an Stellen 2 und 3 unterscheiden.<\/p>\n $$hd(w_1, w_3)=3$$, da sich\u00a0$$w_1$$ und $$w_3$$ an Stellen 1, 2 und 3 unterscheiden.<\/p>\n $$hd(w_2, w_3)=1$$,\u00a0da sich\u00a0$$w_3$$ und $$w_4$$ nur an Stelle 1 unterscheidet.<\/p>\n Damit ist der Hamming-Abstand des gesamten Codes $$HD(C)=1$$<\/p>\n Wie berechnen wir nun den Hamming-Code eines gegebenen Datenworts? Das ist ebenfalls nicht schwer, l\u00e4dt aber dazu ein, sich zu verrechnen.<\/p>\n Beispiel:<\/strong> Hamming-Code f\u00fcr $$01001101$$<\/p>\n 1.\u00a0Festlegeung wie viele Pr\u00fcfbits ben\u00f6tigt werden: Jedes Bit an Stelle einer Zweierpotenz $$(1,2,4,8,16,32, …)$$ wird ein\u00a0Pr\u00fcfbit. Wir haben 8\u00a0Stellen in unserem Datenwort und brauchen daher 4 Pr\u00fcfbits. Macht also insg. 12 Bits in unserem neuen Codewort.<\/p>\n 2. Damit sieht unser „Platzhalter-Codewort“ wie folgt aus:<\/p>\n mit Platzhaltern f\u00fcr Pr\u00fcfbits $$C_1, C_2, C_4$$ und $$C_8$$.<\/p>\n 3. Nun schauen wir, was der Inhalt der Pr\u00fcfbits wird, denn nicht jedes Datenbit geht in die Berechnung eines jeden\u00a0Pr\u00fcfbits ein. Wir legen folgendes fest (und das wird nun ein komischer Satz, aber keine Sorge, er wird gleich erkl\u00e4rt): Ein Bit aus dem Datenwort auf Postion $$k$$ wird nur dann in die Berechnung des Pr\u00fcfbits $$C_i$$ einbezogen, wenn die bin\u00e4re Darstellung von $$k$$ an Position $$log_2(i)$$ eine $$1$$ hat. Puh!<\/p>\n Aber keine Sorge, das entschl\u00fcsseln wir\u00a0gleich. Frage ist: Welche Datenbits aus unserem Datenwort gehen in die Berechnung von\u00a0$$C_1, C_2, C4$$ und $$C8$$ ein?\u00a0Dazu gehen wir wie folgt vor:<\/p>\n 3a. Wir nummerieren die 12 Bits \/ Stellen unseres „Platzhalter-Codeworts“ von links nach rechts:<\/p>\n Z. B. F\u00fcr Pr\u00fcfbit $$C_1$$ muss lt. Definition an Stelle $$log_2(1)=0$$ der bin\u00e4ren Darstellung der\u00a0Position $$k$$ im\u00a0„Platzhalter-Codeworts“ eine $$1$$ stehen, wenn der Wert von der Position $$k$$ aus dem\u00a0„Platzhalter-Codeworts“ in die Berechnung von $$C_1$$ einflie\u00dfen darf. Die Werte f\u00fcr $$k$$ sind die Positionen der Datenbits (die Pr\u00fcfbits 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\u00e4chst in bin\u00e4r dar.<\/p>\n Da wir nun f\u00fcr alle Codeworte $$C_i$$ pr\u00fcfen m\u00fcssen, ob an der betreffenden Stelle $$log_2(i)$$ eine $$1$$ steht, nummerieren wir diese Auflistung der \u00dcbersichtlichkeit halber (nicht vergessen: hier gilt von rechts nach links):<\/p>\n 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:<\/p>\n Wir berechnen nun die Pr\u00fcfbits.<\/p>\n 4. Nun haben wir unsere Pr\u00fcfbits berechnet uns setzen sie an entsprechender Stelle in unser „Platzhalter-Codewort“ (Pr\u00fcfbits sind fett):<\/p>\n Damit ist unser gesuchtes Hamming-Codewort: $$010010011101$$<\/p>\n Beispiel 2<\/strong>: Versucht es mal selbst mit $$10011010$$<\/p>\n
\n$$w_2=11010$$
\n$$w_3=01010$$<\/p>\nBerechnung des Hamming-Codes<\/h2>\n
_ _ 0 _ 1 0 0 _ 1 1 0 1<\/pre>\n
1 2 3 4 5 6 7 8 9 10 11 12\r\n_ _ 0 _ 1 0 0 _ 1 1 0 1<\/pre>\n
Bin\u00e4r 8 4 2 1\r\n-------------------- \r\nPosition 03: 0 0 1 1\r\nPosition 05: 0 1 0 1\r\nPosition 06: 0 1 1 0\r\nPosition 07: 0 1 1 1\r\nPosition 09: 1 0 0 1\r\nPosition 10: 1 0 1 0\r\nPosition 11: 1 0 1 1\r\nPosition 12: 1 1 0 0\r\n--------------------\r\nStelle 3 2 1 0<\/pre>\n
\n
1 2 3 4 5 6 7 8 9 10 11 12\r\n_ _ 0 _ 1 0 0 _ 1 1 0 1<\/pre>\n
\n
1 2 3 4 5 6 7 8 9 10 11 12\r\n0 1<\/strong> 0 0<\/strong> 1 0 0 1<\/strong> 1 1 0 1<\/pre>\n