Deutsch
Menü

Was ist Hamming-Abstand?

Die Zahl der Positionen, an denen sich zwei Bitfolgen (oder Zeichenketten) gleicher Länge unterscheiden. Sie ist gleich der Zahl der Einsen im XOR der beiden Bitfolgen. Der Hamming-Abstand zwischen 1011010 und 0110011 beträgt zum Beispiel 4. Der kleinste Abstand zwischen 2 Codewörtern eines Codes heißt minimaler Hamming-Abstand; ein Code mit dem minimalen Hamming-Abstand d kann Fehler bis zu d − 1 Bit erkennen und Fehler bis zu (d − 1) ÷ 2 Bit (abgerundet) korrigieren.

Japanische Bezeichnung: ハミング距離

„Hamming-Abstand“ kommt in 3 Übungsfragen aus 1 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung.

Fachgebiet: Grundlagen der Informationstheorie und Kodierung

Fähigkeit zur Fehlererkennung und -korrektur

Je weiter die Codewörter auseinanderliegen, desto unwahrscheinlicher macht ein Fehler aus einem Codewort ein anderes. Bei einem Code mit dem minimalen Hamming-Abstand d erzeugt ein Fehler von höchstens d − 1 Bit kein anderes Codewort und wird daher erkannt; ist der Fehler höchstens (d − 1) ÷ 2 Bit groß, ist das dem empfangenen Wort nächstgelegene Codewort das ursprüngliche, sodass er korrigiert werden kann. Der Wiederholungscode, der jedes Bit 3-mal sendet, hat zum Beispiel d = 3 und korrigiert einen 1-Bit-Fehler durch Mehrheitsentscheidung.

Bestimmung bei linearen Codes

Bei einem linearen Code, in dem das XOR zweier beliebiger Codewörter wieder ein Codewort ist, ist der Abstand zweier Codewörter gleich der Zahl der Einsen in dem Codewort, das ihr XOR ist. Der minimale Hamming-Abstand lässt sich daher als kleinste Zahl von Einsen (Gewicht) eines Codeworts ungleich 0 bestimmen, ohne alle Paare zu vergleichen.

Anwendungen in anderen Bereichen

Der Hamming-Abstand dient allgemein als Maß, das die Unterschiede zwischen zwei Datensätzen zählt. Bei der Bewertung einer PUF (Physical Unclonable Function) gelten die einzelnen Chips als umso besser unterscheidbar, je näher der Hamming-Abstand zwischen den Antworten verschiedener Chips an 50 % aller Bits liegt. Bei der Kodierung von Zustandsautomaten verringert ein Hamming-Abstand von 1 zwischen benachbarten Zuständen die Zahl der Bits, die sich bei einem Übergang ändern.

Jetzt üben: Fragen zu Hamming-Abstand

Der minimale Hamming-Abstand eines Codes (der kleinste Hamming-Abstand zwischen zwei beliebigen Codewörtern) beträgt 5. Betrachtet werden die Verwendung nur zur Fehlererkennung und die Verwendung nur zur Fehlerkorrektur. Welche Kombination aus der Zahl der Bitfehler, die sicher erkannt werden, und der Zahl der Bitfehler, die sicher korrigiert werden, ist richtig?

  1. AErkennung bis 4 Bit, Korrektur bis 2 Bit
  2. BErkennung bis 5 Bit, Korrektur bis 2 Bit
  3. CErkennung bis 4 Bit, Korrektur bis 4 Bit
Antwort und Erläuterung anzeigen

Antwort: A. Erkennung bis 4 Bit, Korrektur bis 2 Bit

Bei einem Code mit dem minimalen Hamming-Abstand d kann ein Fehler von bis zu d − 1 Bit kein anderes Codewort erzeugen und wird daher erkannt. Bei der Korrektur wird das empfangene Wort zum nächstgelegenen Codewort korrigiert; ist der Fehler höchstens (d − 1) ÷ 2 Bit (abgerundet) groß, bleibt das ursprüngliche Codewort das nächstgelegene. Für d = 5 ergibt sich Erkennung bis 4 Bit und Korrektur bis 2 Bit.

Häufige Fragen

Sind Hamming-Abstand und Hamming-Code dasselbe?

Nein. Der Hamming-Abstand ist ein Maß, das die Unterschiede zwischen zwei Bitfolgen zählt, während ein Hamming-Code ein Code mit dem minimalen Hamming-Abstand 3 ist, der einen 1-Bit-Fehler korrigieren kann. Beide sind nach Hamming benannt.

Lässt sich der Hamming-Abstand zwischen Bitfolgen unterschiedlicher Länge bestimmen?

Der Hamming-Abstand ist nur zwischen Folgen gleicher Länge definiert. Um Unterschiede einschließlich eingefügter und gelöschter Zeichen zu zählen, verwendet man die Editierdistanz (Levenshtein-Distanz).

„Hamming-Abstand“ in den Erläuterungen

Fragen mit „Hamming-Abstand“ (3)

  1. Wie groß ist der Hamming-Abstand der beiden 7-Bit-Codewörter 1011010 und 0110011?
  2. Der minimale Hamming-Abstand eines Codes (der kleinste Hamming-Abstand zwischen zwei beliebigen Codewörtern) beträgt 5. Betrachtet werden die Verwendung nur zur Fehlererkennung und die Verwendung nur zur Fehlerkorrektur. Welche Kombination aus der Zahl der Bitfehler, die sicher erkannt werden, und der Zahl der Bitfehler, die sicher korrigiert werden, ist richtig?
  3. Welche Kombination aus dem minimalen Hamming-Abstand des Codes mit den 4 Codewörtern 00000, 01011, 10101 und 11110 und der Zahl der Bitfehler, die er sicher korrigiert, ist richtig?

Verwandte Begriffe

Binärer symmetrischer Kanal Hamming-Code Huffman-Kodierung Informationsentropie Informationsgehalt Kraft-Ungleichung Lauflängenkodierung Mittlere Codewortlänge Paritätsbit Präfixcode

Zur Glossarübersicht