Hamming-Abstand

Der Hamming-Abstand oder Hamming-Distanz ist ein grundlegender Begriff der Codierungstheorie, benannt nach dem Mathematiker Richard Wesley Hamming (1915 - 1998). Der Hamming-Abstand zweier Blöcke von binären Daten mit fester Länge (so genannter Codewörter) kann ermittelt werden, indem man beide in binärer Form hinschreibt, diese Bit für Bit vergleicht und die Stellen zählt, die ungleich sind. Rechnerisch lässt sich der Vergleich durch eine XOR-Operation und das Abzählen der resultierenden Einsen realisieren.

Bsp.:

x = 00110

y = 00101

Der Hamming-Abstand ist hier 2, da sich die beiden Wörter x und y an genau zwei Stellen unterscheiden (nämlich die beiden Stellen ganz rechts).

Unter dem Hamming-Abstand eines kompletten Codes versteht man das Minimum aller Abstände zwischen Wörtern innerhalb des Codes.

Bsp.:
ein Code bestet aus folgenden drei Wörtern

x = 00110

y = 00101

z = 01110

Der Hamming-Abstand zwischen x und y ist 2;
Der Hamming-Abstand zwischen x und z ist 1;
Der Hamming-Abstand zwischen y und z ist 3;
Der kleinste der drei Abstände ist 1, also ist der Hamming-Abstand des Codes ebenfalls gleich 1.

Wichtig ist die Hamming-Distanz, wenn man Codes entwickeln möchte, die Fehler erkennen EDC oder Fehler korrigieren ECC könnnen. Für den Hamming-Abstand h können jeweils h-1 Bit Fehler erkannt werden. In dem Beispiel mit h=2 können somit alle 1-Bit Fehler erkannt werden. Um die Fehler auch korrigieren zu können, muss die Hamming-Distanz auf mindestens (2*r)+1 vergrößert werden, wobei r für die Anzahl der Bit Fehler steht. Bei h=3 können alle 1-Bit Fehler erkannt und korrigiert werden. Treten 2-Bit Fehler auf, können diese zwar erkannt, aber nicht mehr korrigiert werden.

Der Hamming-Abstand eines Codes ist notwendigerweise eine positive Ganzzahl >=1. Ein Code mit Hamming-Abstand 0 ist nicht möglich, da sich in diesem Fall zwei Codewörter nicht unterscheiden lassen.

Repräsentation der Bit-Strings in einem Hypercube

Die Idee der Hamming-Distanz kann gut mit Hilfe von Hypercubes dargestellt werden. Ein Hypercube ist die Generalisierung eines dreidimensionalen Würfels auf die Dimension d. Jeder Knoten der Figur entspricht einer Bitkombination, die auch als Koordinatenangabe im Raum verstanden werden kann. Die minimale Anzahl der Kanten, die traversiert werden muss, um von einem gültigen Wort eines Codes zu einem anderen gültigen Wort des Codes zu gelangen, entspricht der Hamming-Distanz.

Beispiel

Hypercubes mit d=1 bis d=4

Wenn im nebenstehenden Würfel mit d=3, die beiden Worte {101,010} für einen Code gewählt werden, so beträgt die minimale Hamming-Distanz 3. Damit können in einer Sphäre mit dem Abstand 1 um einen Punkt mit einem gültigen Wort (z.B. für das gültige Code-Wort 010) alle Fehler (1-Bit Fehler) erkannt und korrigiert werden {000,110,011}.

Wird ein Code mit den Worten {000,101,110,011} gewählt, so beträgt die minimale Hamming-Distanz 2. Mit einem Hamming-Abstand von 2 lassen sich 1-Bit Fehler lediglich erkennen, aber nicht korrigieren (Beispielsweise lässt sich zwar erkennen, dass 111 einen fehlerhaften Wert darstellt, jedoch nicht, ob er nach 110 oder 011 oder 101 korrigiert werden soll).