TU Wien:Technische Grundlagen der Informatik VU (Kastner)/UE2 2016W Lösung

Aufgabe 8

Ein Hamming-Code hat 4 Prüfbit.

a) Wie lange (in Bit) können die Codewörter maximal sein? Wieviele Bit stehen maximal für Daten zur Verfügung?
b) Wie lauten die Gleichungen für die nötigen Prüfbits dieses Codes?
c)Listen Sie alle gültigen Codewörter eines Hamming-Code mit 7 Codebit auf!
Hinweis: Es werden möglicherweise nicht alle Zeilen benötigt.
d) Überprüfen Sie anhand von zwei Beispielen exemplarisch, ob es sich bei dem Code aus c) um einen linearen Code handeln könnte!
e) Decodieren und ggf. korrigieren sie das empfangene Codewort $c_{1}c_{2}c_{3}c_{4}c_{5}c_{6}c_{7}=1101110$ unter der Annahme, dass es sich beim Absenden um ein Codewort aus dem code aus c) hendelte und maximal ein Bit gestört wurde!

Lösungsvorschlag zu a):

Prüfbits $p_{1}p_{2}p_{3}p_{4}$ sind jeweils an der Stelle $c_{1}c_{2}c_{4}c_{8}$(2er Potenzen), daraus ergibt sich das Codewort $c_{1}c_{2}c_{3}c_{4}c_{5}c_{6}c_{7}c_{8}c_{9}c_{10}c_{11}c_{12}c_{13}c_{14}c_{15}$ mit folgenden Stellen (p = Prüfbit, d = Datenbit):$p_{1}p_{2}d_{1}p_{3}d_{2}d_{3}d_{4}p_{4}d_{5}d_{6}d_{7}d_{8}d_{9}d_{10}d_{11}$.
Die maximale Länge Codewörter ist 15 Bit, die maximale Anzahl der Bits für Daten ist 11 (15 Länge gesamt minus 4 Prüfbits).


Lösungsvorschlag zu b):

Etwas Theorie:
Um zu erkennen, welches Codebit $c_{k}$ mit Index k zu welchen Prüfbits gehört, muss man Index k in 2er Potenzen aufteilen:
zB bei $c_{15}$ ist Index $15=8+4+2+1$, oder $23=16+4+1$.

$c_{1}=p_{1}=(c_{3}+c_{5}+c_{7}+c_{9}+c_{11}+c_{13}+c_{15})mod2=c_{3}\otimes c_{5}\otimes c_{7}\otimes c_{9}\otimes c_{11}\otimes c_{13}\otimes c_{15}$
$c_{2}=p_{2}=...=c_{3}\otimes c_{6}\otimes c_{7}\otimes c_{10}\otimes c_{11}\otimes c_{14}\otimes c_{15}$
$c_{4}=p_{3}=...=c_{5}\otimes c_{6}\otimes c_{7}\otimes c_{12}\otimes c_{13}\otimes c_{14}\otimes c_{15}$
$c_{8}=p_{4}=...=c_{9}\otimes c_{10}\otimes c_{11}\otimes c_{12}\otimes c_{13}\otimes c_{14}\otimes c_{15}$
$\otimes$ ... XOR


Lösungsvorschlag zu c):

Bei einem lineareren Code ergibt die Kombination (Summe) von zwei Codewörtern ebenfalls ein Codewort:

0010110 + 0011001 = 0001111 ... lt. Tabelle aus c) ist das Ergebnis darin enthalten.


Lösungsvorschlag zu d):

Beim Codewort 1101110 sind folgende Stellen Prüfbits: $c_{1}c_{2}c_{4}$
Daraus folgt:

$p_{1}=c_{3}\otimes c_{5}\otimes c_{7}=0\otimes 1\otimes 0=1$ korrekt
$p_{2}=c_{3}\otimes c_{5}\otimes c_{7}=0\otimes 1\otimes 0=1$ korrekt
$p_{3}=c_{5}\otimes c_{6}\otimes c_{7}=1\otimes 1\otimes 0=0\neq 1$
Da Prüfbit $p_{3}$ 0 sein sollte, in der Übertragung 1 aufscheint, liegt hier der Fehler. $p_{3}=c_{4}$ dadurch ist Index 4 gestört und gehört auf 1 korrigiert, das Ergebnis ist 1100110.

Anmerkung: Wären zB $p_{1}=c_{1}$ und $p_{2}=c_{2}$ anders als in der Übertragung, wäre Index $1+2=3$, also $c_{3}$ gestört und gehört korrigiert.