Ich muss mich für eine hausarbeit mit dem Hamming Code beschäftigen und habe eine kleine Frage. Gegeben ist eine 7-Bit Zahlenfolge welche decodiert werden soll und ggf. Fehler berichtigt werden sollen. Geh ich recht in der Annahme, dass eine eindeutige Korrektur nicht möglich ist? D.h. wenn z.B. die Zahlenfolge 0100000 gegeben ist. Am wahrscheinlichsten ist, dass p2 falsch übertragen wurde und die Zahlenfolge eigentlich 0000000 lautet. Aber sie könnte doch auch 0101010, 1100001 usw sein. Ich denke, dass ich es immer so korrigiere, dass möglichst wenig bits verändert werden müssen?
Das kommt auf die Hamming-Distanz dmin Deines Codes an. Das ist die minimale Anzahl an Bits, an denen sich zwei zulässige Codewörter unterscheiden. Somit kannst Du dmin-1 Bitfehler erkennen (Du brauchst mindestens dmin Bitfehler, um von einem gültigen Codewort zu einem anderen Codewort zu kommen). Für die Fehlerkorrektur wird folgende Überlegung angewandt: Stell Dir die zulässigen Codewörter im Raum aller Codewörter vor. Wenn jetzt ein unzulässiges Codewort übertragen wird, so geht man davon aus, daß die Wahrscheinlichkeit der Verfälschung mit jedem weiteren falschen Bit abnimmt, d.h. ein Einzelbitfehler ist wahrscheinlicher als zwei Bitfehler. Deshalb geht man nur von einer geringen Verfälschung aus und korrigiert zum nächstgelegenen zulässigen Codewort. Da dieses im Minimum dmin Bitfehler entfernt liegt, kannst Du somit [(dmin-1)/2] Bitfehler korrigieren. Machst Du mehr Fehler, so liegt das resultierende Codewort näher an einem anderen zulässigen Codewort als dem gesendeten, du korrigierst somit falsch.
Danke für deine schnelle Antwort - soähnlich habe ich mir das schon vorgestellt; dann lag ich ja richtig :-) Mal vom Allgemeinen zum Speziellen: Ich korrigiere grade ein paar Zahlenfolgen; um mien Ergebnis zu überprüfen habe ich unter http://www.ee.unb.ca/cgi-bin/tervo/hamming.pl ein praktisches Tool gefunden. Die Zahlenfolge "1000001" habe ich nicht hinbekommen, ohne 2 bits zu ändern. Das Toll liefert mir als Ergebnis "1100001". Aber wie kann das sein? p3 ist ja = c5 XOR c6 XOR c7. In dem Fall p3 = 0. 0 XOR 0 XOR 1 ist doch aber 1?! Ich dachte schon, ihc hätte es verstanden, nun bin ich aber verwirrt...
Nicht so schnell. Deine Codeworte erhältst Du, indem Du zu Deinem Datenbits c_0...c_(L-D-1) die Paritätsprüfbits p_0...p_D-1 errechnest. Somit enststehen in Deinem Codewortraum von 2^L Binärcodewörtern die 2^(L-D) zulässigen Codewörter. Du hast einen L=7 Code und eine Prüffeldlänge von D=3. Somit hast Du 128 Codewörter insgesamt, von denen aber nur 2^4=16 richtig sind bzw. Du kannst pro 7-Bit-Wort nur 4 Datenbits übertragen. Diese XOR-Kombination gibt Dir an, wie sich die Prüffeldbits aus den Datenbits ergeben. Somit kannst Du zu allen 16 Datenwörtern die gültigen 3 Prüfbits errechnen und erhältst jeweils ein 7-Bit-Codewort. Diese Codewörter sind aber nur eine Untermenge der 128 möglichen Binärcodewörter, die Du empfangen kannst. Empfängst Du etwas anderes als die 16 Codewörter, muß es sich um einen Fehler handeln. Um diesen zu korrigieren, mußt Du das nächstgelegene zulässige Codewort finden. Einfaches Beispiel: 2 Datenbits, zwei Prüfbits, Regel: p_0 = d_0 XOR d_1 (Parität), p_1 = d_1 Datenwörter: 00, 01, 10, 11 daraus errechnen sich die zulässigen Codewörter d0 d1 p0 p1 0 0 0 0 0 1 1 1 1 0 1 0 1 1 0 1 Die "Abstände" zwischen den gültigen Codewörtern sind: 1->2: 3, 2->3: 3, 3->4: 3 der minimale Abstand ist also dmin=3. Damit kannst Du dmin-1=2 Fehler erkennen und [(dmin-1)/2]=1 Fehler korrigieren. Empfängst Du z.B. 0 0 0 1, so hat dieses zum 1. zulässigen Codewort den geringsten Abstand. Du korrigierst also zu 0 0 0 0. Empfängst Du 1 0 0 0, so hat dieses Codewort zum 3. zulässigen Codewort den geringsten Abstand, du korrigierst also zu 1010. Der zugehörige Datenvektor ist 10.
Danke, dass habe ich eigentlich (glaube ich) schon verstanden. Nur verstehe ich nicht, warum "1100001" ein zulässiges Codewort ist. Das dazugehörige Datenwort lautet dann ja "??0?001" (Um verwirrung vorzubeugen: Ich habe immer bei 1 angefangen zu zählen). Wenn ich nun von 0001 das Codewort bilden will gehe ich vor: c1 = p1 = c3 XOR c5 XOR c7 = 1 Also nun "1?0?001" c2 = p2 = c3 XOR c6 XOR c7 = 1 Also nun "110?001" c4 = p3 = c5 XOR c6 XOR c7 = 1 Also nun "1101001" Und das ist der Punkt, den ich nicht verstehe. Also warum 1100001 ein zulässiges Codewort ist - welches Datenwort gehört den dann dazu? Sorry für meine laienhafte Ausdrucksweise; ich habe mich mit der ganzen Thematik noch nie beschäftigt... heute Nachmittag das erste mal und war eigentlich froh es verstanen zu haben nachdem ich zwischenzeitig irgendwelche Matrixen etc. im Zusammenhang it dem Thema sah (bin übrigens in Klasse 11 - da sind die Mathematikkentnisse auch noch nicht soo ausgeprägt).
In meinem obigen Beispiel ist d0 d1 das Datenwort und p0 p1 der Prüfvektor. Diese werden beim Hammingcode hintenangehängt! Mit dem Code aus meinem Beispiel kannst Du ein 2-Bit-Wort in einem 4-Bit-Code senden, d.h. an die 2 Datenbits werden 2 Prüfbits angehängt. Somit ensteht ein 4-Bit-Wort, welches Dir 16 Kombinationen ermöglicht. Aber nur 4 sind davon zulässig!
Nun hast du meine Verwirung perfekt gemacht! Tut mir Leid wenn ich dich nerve aber warum werden die Prüfbits hinten dran gehängt? Sagt diese Grafik nicht etwas anderes aus: http://upload.wikimedia.org/wikipedia/commons/7/72/Hamming_code_parity_bit_position_1.svg
Weil er ein systematischer Code ist. Die Datenbits bleiben z.B. im Gegensatz zu den Faltungscodierern erhalten, die Prüfbits werden angehängt / davorgesetzt. Die Idee ist aber immer gleich: Wenn du an 4 Datenbits (=16 Datenwörter) z.B. 3 Prüfbits anhängst, bekommst Du 16 7-Bit-Gesamtwörter. Das ist eine kleine Untermenge der mit 7 Bit möglichen 128 Binärwörter.
Oder ein noch einfacheres Beispiel: Nimm ein 2 Bit Datenwort mit einem
Paritätsbit. Die Bildungsvorschrift ist p0 = d0 + d1 ("+"=XOR).
Damit ergeben sich für die 4 Datenwörter folgende Gesamtcodes:
0 0 0
0 1 1
1 0 1
1 1 0
Diese 4 3-Bit-Wörter sind die einzigen "korrekten" 3-Bit-Wörter, also
eine Untermenge aller 8 möglichen 3-Bit-Wörter. Empfängst Du etwas
anderes, muß ein Fehler vorliegen.
Übrigens: die Sache mit den Matrizen ist recht einfach. Dieser einfache
Hamming-Code hat die Matrixschreibweise
Wobei wie gesagt "+" die XOR-Verknöpfung darstellt.
Gibts auch einen Matrizenausdruck, der ein ungültiges Datenwort korrigiert, falls es korrigierbar ist?
Man kann zur Generatormatrix G, welche das Codewort aus dem Datenwort gemäß c = G * d bildet, eine Prüfmatrix H berechnen, deren Zeilen (bzw. Spalten in meiner Schreibweise orthogonal zu allen gültigen Codes sind: H*c = 0 wenn c gültig Das übliche Verfahren der Korrektur läuft so ab, daß man im Fehlerfall ein Syndrom s H*c=s != 0-Vektor erhält, aus dem mittels Syndromtabelle ein Korrekturvektor e abgelesen wird, den man dann einfach zum empfangenen Code addiert.
Thread beobachten
Seitenaufteilung abschalten
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.