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 mit fester Länge (sogenannter Codewörter) kann ermittelt indem man beide in binärer Form hinschreibt Bit für Bit vergleicht und die Stellen die ungleich sind. Rechnerisch lässt sich der durch eine XOR -Operation und das Abzählen der resultierenden Einsen

Bsp.:

x = 00110

y = 00101

Der Hamming-Abstand ist hier 2 da die beiden Wörter x und y an zwei Stellen unterscheiden (nämlich an Stelle 4 5).

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

Bsp.:
ein Code bestet aus folgenden drei

x = 00110

y = 00101

z = 01110

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

Wichtig ist die Hamming-Distanz wenn man entwickeln möchte die Fehler erkennen EDC oder Fehler korrigieren ECC könnnen. Für den Hamming-Abstand h können h-1 Bit Fehler erkannt werden. In dem mit h=2 können somit alle 1-Bit Fehler werden. Um die Fehler auch korrigieren zu muss die Hamming-Distanz vergrößert werden. Bei h=3 alle 1-Bit Fehler erkannt und korrigiert werden. 2-Bit Fehler auf können diese zwar erkannt nicht mehr korrigiert werden.

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

Bücher zum Thema Hamming-Abstand

Dieser Artikel von Wikipedia unterliegt der GNU FDL.