Grundlagen der Fehlerkorrigierenden Codierung (Hamming Distanz/Hamming Code)

Hamming-Distanz und Hamming-Codes

Im täglichen Leben mißt man eine Distanz durch Abzählen der Meter, die man mindestens braucht, um von einem Ort zu einem anderen zu gelangen.

In der digitalen Welt der Folge von Nullen und Einsen, also der „Bits“, ist entsprechend die „Hamming-Distanz“ die Anzahl der Bits, die man mindestens ändern muß, um von einer Bitfolge zu einer anderen zu gelangen. Diese Distanz wurde Anfang der 50er Jahre von R. W. Hamming eingeführt, sie wird seitdem von der Informationstechnik bis zur Informatik ausgiebig angewendet. So kann man beispielsweise bei der für die „künstliche Intelligenz“ typischen Aufgabe der Gesichtserkennung die Ähnlichkeit zweier Gesichter über ihre Hamming-Distanz messen.

Die erste Anwendung, für die Hamming dieses Distanzmaß einführte, betraf aber die Sicherung gegen Fehler bei der Übertragung, Speicherung oder Verarbeitung von Bitfolgen. Je größer die Anzahl der Übertragungsfehler ist, desto größer wird auch die Hamming-Distanz zwischen gesendeter und fehlerhaft empfangener Bitfolge. Hamming benutzte daher zur Übertragung nur solche Bitfolgen, die untereinander eine mehr als doppelt so große Hamming-Distanz aufweisen, wie sie durch Übertragungsfehler entstehen können. So läßt sich ein Fehler erkennen und sogar korrigieren. Mehrere Bitfolgen mit großer Hamming-Distanz bilden einen „Hamming-Code“. Diese, mit der Informations-theorie Shannons zeitgleichen Arbeiten Hammings bilden das Fundament der allgemeinen Theorie fehlerkorrigierender Systeme und Codes. Ihre Bedeutung liegt vor allem darin, daß sich beliebig komplexe Systeme mit vorgebbarer Zuverlässigkeit auch aus unzuverlässigeren Teilsystemen aufbauen lassen. Der dazu notwendige Aufwand kann dabei exakt berechnet werden.

Ihre unverzichtbare Anwendung findet die auch mathematisch höchst anspruchsvolle Theorie der fehlerkorrigierenden Codierung heute in jedem CD-Spieler und jedem Handy sowie auch in jedem Großrechner und in den weltumspannenden Nachrichtennetzen. Nur durch solche Codes lassen sich die unvermeidbaren Fehler bei der Übertragung, Speicherung und Verareitung von Informationen korrigieren.
Prof. Dr. Hans Dieter Lüke
RWTH Aachen