www.mikrocontroller.net

Forum: Offtopic Hamming Code - Anfängerfrage


Autor: dau45 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Rüdiger Knörig (sleipnir)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: dau45 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Rüdiger Knörig (sleipnir)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: dau45 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Rüdiger Knörig (sleipnir)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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!

Autor: dau45 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...

Autor: Rüdiger Knörig (sleipnir)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Rudi (nicht eingeloggt) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Uhu Uhuhu (uhu)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gibts auch einen Matrizenausdruck, der ein ungültiges Datenwort 
korrigiert, falls es korrigierbar ist?

Autor: Rudi (nicht eingeloggt) (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

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, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.