Was ist die Hamming-Distanz?

Hamming-Distanz

Die Hamming-Distanz ist eine Metrik zum Vergleich zweier binärer Datenketten. Beim Vergleich zweier gleich langer binärer Zeichenketten ist die Hamming-Distanz die Anzahl der Bitpositionen, in denen sich die beiden Bits unterscheiden.

Die Hamming-Distanz zwischen zwei Zeichenketten, a und b, wird als d(a,b) bezeichnet.

Sie wird zur Fehlererkennung oder Fehlerkorrektur verwendet, wenn Daten über Computernetze übertragen werden. Sie wird auch in der Codierungstheorie zum Vergleich von Datenwörtern gleicher Länge verwendet.

Berechnung der Hamming-Distanz

Um die Hamming-Distanz zwischen zwei Zeichenfolgen und zu berechnen, führen wir ihre XOR-Verknüpfung durch (a⊕ b) und zählen dann die Gesamtzahl der 1en in der resultierenden Zeichenfolge.

Beispiel

Angenommen, es gibt zwei Zeichenketten 1101 1001 und 1001 1101.

11011001 ⊕ 10011101 = 01000100. Da dies zwei 1en enthält, ist die Hamming-Distanz d(11011001, 10011101) = 2.

Minimale Hamming-Distanz

In einer Menge von Zeichenfolgen gleicher Länge ist die minimale Hamming-Distanz die kleinste Hamming-Distanz zwischen allen möglichen Paaren von Zeichenfolgen in dieser Menge.

Beispiel

Angenommen, es gibt vier Zeichenfolgen 010, 011, 101 und 111.