Hamming-Distanz

[walnuss0815]

Hallo zusammen,

zurzeit schreibe ich eine wissenschaftliche Ausarbeitung zum Thema fehlererkennende und fehlerkorrigierende Codes. Als ein Beispiel für einen solchen Code habe ich mir den Hamming-Code herausgesucht. Anhand dieses Videos habe ich verstanden, wie die Codierung und Decodierung mit dem Hamming-Code funktioniert: https://www.youtube.com/watch?v=sANR9nA-8rA

Nun befasse ich mich aktuell damit, die viele Fehler korrigiert bzw. nur erkannt werden können. Dabei stoße ich immer wieder auf das Thema Hamming-Distanz und darauf, dass die Anzahl davon abhängt. Leider kann ich die Verständnislücke zwischen dem Hamming-Code und der Hamming-Distanz nicht schließen, da mir nicht bekannt ist auf was ich die Hamming-Distanz anwende.

Ich hoffe, dass ihr mir bei dem Verständnis des Themas helfen könnt.

Mit freundlichen Grüßen
​walnuss0815

 

[Saphirim]

Hi walnuss,

bei solchen "Informatik/Coding" Fragen empfiehlt sich meistens eins der StackExchange Foren, in dem Fall StackOverflow.

From: https://stackoverflow.com/questions/12741613/finding-hamming-distance-of-code

"The Hamming distance of a code is defined as the minimum distance between any 2 codewords. So, in your case, finding the Hamming distance between any 2 of the listed codewords, no one is less than 2."

Vielleicht bringt dich das auf die richtige Spur

Gruß,

Saphirim

 

[ph4nt0m]

Die Hamming-Distanz sagt aus, wie viele verschiedene Bits eines gültigen Codeworts mindestens "gekippt" werden müssen, damit ein anderes gültiges Codewort entsteht. Daraus folgt, dass der Code zumindest (Hamming-Distanz - 1) Bitfehler erkennen kann.

 

[walnuss0815]

Erst einmal danke für eure Antworten!

Vielleicht bringt dich das auf die richtige Spur

Leider nicht. Wie die Hamming-Distanz berechnet wird, ist sogar im deutschsprachigen Wikipedia verständlich erklärt. Mir fehlt die Verbindung zum Hamming-Code.
​

Die Hamming-Distanz sagt aus, wie viele verschiedene Bits eines gültigen Codeworts mindestens "gekippt" werden müssen, damit ein anderes gültiges Codewort entsteht. Daraus folgt, dass der Code zumindest (Hamming-Distanz - 1) Bitfehler erkennen kann.

Wenn ich also ein mit dem Hamming-Code codiertes Codewort habe, in dem ein Bit gekippt ist, dann ist die Hamming-Distanz zu einem gültigen Codewort 1.
1 - 1 = 0
Somit könnte ich einen Fehler gar nicht erkennen. Oder habe ich etwas falsch verstanden?

 

[ph4nt0m]

Wenn ich also ein mit dem Hamming-Code codiertes Codewort habe, in dem ein Bit gekippt ist, dann ist die Hamming-Distanz zu einem gültigen Codewort 1.

Was ich vorhin als Hamming-Distanz bezeichnet habe, heißt eigentlich korrekterweise "minimale Hamming-Distanz" (ich habe mich da etwas vom Zitat aus Saphirims Beitrag ablenken lassen).

Die minimale Hamming-Distanz ist eine allgemeine Eigenschaft eines Codes und ergibt sich wie oben beschrieben aus allen Codewörtern des Codes.

Normale Hamming-Codes haben z.B. immer eine minimale Hamming-Distanz von 3, denn zwei beliebige Codewörter unterscheiden sich hier immer an mindestens drei Stellen.

Wenn du also ein mit dem Hamming-Code codiertes Codewort hast, in dem ein Bit gekippt ist, dann ist die Hamming-Distanz zu dem unverfälschten Codewort 1. Da die minimale Hamming-Distanz des gesamten Codes aber 3 ist, weiß du sicher, dass du durch das Kippen eines einzigen Bits kein anderes gültiges Codewort erzeugt haben kannst (welches dann fälschlicherweise als korrekt erkannt würde). Also können maximal zwei gekippte Bits erkannt werden.