Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Hamming-Code
Hallo, ich habe eine kurze Frage zur 4c) vom 14.April 2012:
Gegeben ist eine im (7,4)-Hamming-Code codierte Nachricht:
1101111 1011001 1011100 0101001 1010101
Diese soll man nun auf Fehler untersuchen. Nun hatten wir ja in der Miniklausur und in den Übungen die entsprechende Codeworttabelle vorgegeben mit der man die Prüfbits vergleichen konnte, hier hat man diese aber nicht. Kennt jemand eine schnelle Möglichkeit trotzdem die Fehlerkorrektur durchzuführen?
Geht wohl nicht ohne Huffman-Matrix. Die kann man aber eigentlich recht schnell erstellen und dann die Gleichungen für die Prüfbits auslesen.
An deinem Beispiel:
Huffman-Matrix aufstellen: 7,4-Hamming-Code => #Zeilen = aufgerundet(ld(m+k)), man benötigt also 3 Zeilen. (#Spalten = m+k)
Man arbeitet von rechts nach links und fängt bei der binären 1 an hoch zuzählen, hierbei schreibt man die einzelnen Bitstellen untereinander:
1 1 1 1 0 0 0
1 1 0 0 1 1 0
1 0 1 0 1 0 1
Die Spalten in denen nur eine 1 vorkommt sind die y, die restlichen die x:
x4 x3 x2 y3 x1 y2 y1
1 1 1 1 0 0 0
1 1 0 0 1 1 0
1 0 1 0 1 0 1
Um die y-Gleichungen aufzustellen, schaut man sich die Zeile der Y-Spalte an in der die 1 steht. Alle X, bei denen in der gleichen Zeile ebenfalls eine 1 steht, werden dann verXORt.
Also:
y1 = x1 XOR x2 XOR x4
y2 = x1 XOR x3 XOR x4
y3 = x2 XOR x3 XOR x4
und mit diesen Gleichungen kannst du nun die Nachricht überprüfen.
Erstes Codewort:
x4 x3 x2 x1 y3 y2 y1
1 1 0 1 1 1 1
Wenn man es mit den Gleichungen überprüft, stellt man fest, dass y1 (= 1 XOR 0 XOR 1 = 0) und y3 (= 0 XOR 1 XOR 1 = 0) nicht passen.
Ich schaue deshalb welches X sie gemeinsam haben. → x2
x2 ist fehlerhaft, muss also eine 1 sein.
da in klausuren denken immer so schwer ist, finde ichs schneller, sich schnell die codetabelle aufzustellen ( https://fsi.informatik.uni-erlangen.de/forum/thread/11245-Frage-zu-Uebung-2-Aufgabe-4 ) und dann einfach das wort zu nehmen, was am nächsten dran ist.
Gut, vielen Dank euch beiden. Ich glaube ich schreibe mir dann die Gleichungen für die Prüfbits am besten auf meinen Spicker.