Hamming code?
Wie finde ich beim Hamming Code die Position des falschen bits heraus? Danke im vorraus
3 Antworten
Du siehst doch die leeren dunklen Felder im Bit Nr. 1,2,4, und 8. Das sind die sogenannten Paritätsbits. Beim Ausfüllen der Data achtest du darauf, dass du die Daten nur in die Datenbits (einfach NICHT die Paritätsbits), also 3,5,6,7,9,10,11 schreibst. Jetzt gibt es ein Schema, was bei dir in den "adding" Zeilen angewendet wird.
Gehen wir zur Zeile "Adding r1". Mit dem Schema (der Linie) fangen wir von links an, die Bits die 1 sind zu zählen: 11 ist 1, 7 ist 1, 3 ist 1. Drei Einser also, das ist ungerade, deshalb schreiben wir in das Paritätsbit, mit dem auch das Schema verbunden ist die 1. Eins bei ungerade, Null bei gerade.
Bei "Adding r2" dasselbe. In dem Schema gibt es 4 Einsen, also schreiben wir in das Paritätsbit Nr.2 eine 0 (weil 4 gerade ist). Das ganze geht so weiter bis r8, also 4 Schemas.
Angenommen wir ändern jetzt einen Databit (z.B. weil es beim Verschicken umgesprungen ist).
10111100101. Ich habe etwas geändert. Versuch nicht durch vergleichen herauszufinden welches anders ist, wir machen das jetzt zusammen:
Wir nehmen das erste Schema und erwarten dort eine ungerade Anzahl von 1er, weil im Paritätsbit eine 1 ist. Wir zählen also die 1er in den Feldern 3,5,7,9,11. Ich zähle 4 Einser, ein Fehler, wir erwarten eine ungerade Anzahl von Einsern. Der Fehler liegt also im Feld 3,5,7,9 oder 11.
Wir gehen zum zweiten Schema. Dort steht eine 0, wir erwarten eine gerade Anzahl von Einsern in den Feldern 3,6,7,10 und 11. Ich zähle 4 Einser, das stimmt, deshalb ist der Fehler nicht dort. Der Fehler kann jetzt noch in den Feldern 5 und 9 sein (die anderen können wir ausschließen).
Wir gehen ins dritte Schema. Wegen der 0 im Paritätsbit Nr. 4 erwarten wir in den Feldern 5,6,7 eine gerade Anzahl an Einsern. Ich zähle 2 Einser, das stimmt also! Der Fehler kann jetzt nur noch im Feld 9 sein!
Der Vollständigkeit halber machen wir noch das vierte Schema: Im Paritätsbit Nr. 8 steht eine 1, deshalb erwarten wir in den Feldern 9,10,11 eine ungerade Anzahl an Einsern. Ich zähle aber 2! Dort liegt also der Fehler.
Wegen des Aussschlussverfahrens sind wir aber vorher schon darauf gekommen, das der Fehler im Feld 9 liegt.
10111100101 Falsch
9
10011100101 Richtig
Danke für die ausführliche antwort aber geht das nicht auch irgendwie mit addieren der Paritätsbits vor dem Fehler und danach müsste das eben in Python programmieren und da suche ich gerade die einfachste lösung...
Im wesentlichen berechnest du den Hamming Code der Daten erneut und addierst den Empfangenen Hamming Code ohne Übertrag.
Wenn alles passt kommt da 0 raus, ansonsten kommt die Stelle des Fehlerhaften Bits raus.
Ein Beispiel findest du hier
https://de.wikipedia.org/wiki/Hamming-Code#Vereinfachte_Variation_mit_Beispiel
Eine andere Möglichkeit ist die Syndrom Dekodierung. Die aber im Hamming Code im wesentlichen auf das selbe raus läuft.
Man multipliziert das Empfangene Codewort mit der Checkmatrix und je nach falschen Bit erhält man einen anderen Vektor, der als Syndrom bezeichnet wird. Man macht dann eine Tabelle von Bitfehler sucht in dieser nach dem Syndrom und wenn man es gefunden hat kann man die falschen Stellen direkt ablesen.
Der Hamming Code ist so gemacht, dass das Syndrom direkt der Binärrepräsentation der Stelle des Bitfehlers ist was oben beschrieben wird.
Die Syndromdekodierung von Blockcodes findest du hier:
https://en.wikipedia.org/wiki/Decoding_methods#Syndrome_decoding
Asoo da hab ich mich verschrieben du addierst die Stellen an denen ein 1er ist so wie es im Wikiartikel drinnen steht den ich verlinkt habe.
Genauer gesagt bildest du die Parität von den diesen Stellen.
Sry habs im wiki artikel nicht verstanden also einfach wenn du 1001+1001 nur eins am anfang und am ende addieren?
Ohne Übertrag also
1001
1001
1+1=2=0 was hier
0000 ergibt
1101
1001
Würde hingen 0100 ergeben weil das dritte Bit in einer ungeraden Anzahl vorkommt.
Hab jetzt bei meinem beitrag noch ein bild hinzugefügt könntest du mir da den Fehler sagen?
Die unterstrichenen sind die Paritätsbits
Bräuchte die antwort schnell wenns gehen würde
Ich sehe das Bild nicht. Aber ein Beispiel nehmen wir das Empfangen Datenwort
11010110|0011
Dann zählen wir jetzt die Position der 1en , also 2,3,5,7,8 die schreiben wir jetzt binär an:
0010
0011
0101
0111
1000
0011 < Das ist die empfangene Parität
Die Rechnung ergibt jetzt
1000 was umgerechnet 8 bedeutet sprich, das Bit Nummer 8 ist falsch. Das Richtige Codewort ist also
01010110.
Zum prüfen rechnen wir nochmal nach Bits an den Stellen 2, 3,5,7 mit der übtragenen Parität liefert 0 und damit stimmts.
Ich sehe aber gerade, dass du die ursprüngliche Variante verwendest. Die von mir in diesem Beisspiel ist eine vereinfachte Variante des Hamming Codes.
In deinem Fall wird glaub ich die Bildung der Checkmatrix und die Berechnung des Syndromvektors vermutlich am besten sein. Eine Methode mit dem Berechnen der Parität so wie hier kenne ich da nicht wirklich.
invader7 hat eine genannt, die dürfte aber schwerer zu implementieren sein.
Stimmt das liegt daran, dass du eine andere Variante des Hamming Codes verwendest. In dem Fall muss du es glaub ich über die Syndrom Dekodierung machen
Für deinen Code kannst du die Daten mit der Checkmatrix multiplizieren und der Syndromvektor sollte in Binärdarstellung der Fehlerstelle entsprechen.
Indem Du das nächstegelegene Codewort findest und vergleichst. Bei einem einzelnen Fehler ist die Distanz 1.
Wie hast du das gemeint mit addieren nur die prüfbits addieren? Weil da kann ja nie 0 herauskommen...