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!
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.
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.
