Die Hamming-Distanz (auch Hamming-Abstand) zählt, an wie vielen Stellen sich zwei gleich lange Wörter unterscheiden. Sie ist das wichtigste Maß der Kanalcodierung: Aus der minimalen Distanz eines Codes lässt sich direkt ablesen, wie viele Fehler er erkennen und korrigieren kann.
Berechnung
Zwei Wörter gleicher Länge werden Bit für Bit verglichen; die Hamming-Distanz ist die Anzahl der Positionen, an denen sie verschieden sind. Beispiel: 10110 und 11100 unterscheiden sich an den Positionen 2 und 4 – die Distanz ist 2. Rechnerisch entspricht das der Anzahl der gesetzten Bits im XOR der beiden Wörter (Popcount).
Mindestdistanz bestimmt die Korrekturfähigkeit
Entscheidend ist nicht der Abstand einzelner Paare, sondern die Mindestdistanz d eines Codes: der kleinste Abstand zwischen zwei beliebigen gültigen Codewörtern. Es gilt:
- Mit Distanz d lassen sich d − 1 Fehler erkennen.
- Es lassen sich (d − 1) / 2 Fehler korrigieren (abgerundet).
Ein Code mit Mindestdistanz 3 – wie der Hamming-Code – erkennt damit 2 Fehler und korrigiert 1 Fehler. Die Distanz funktioniert wie ein Sicherheitsabstand: Je weiter die Codewörter auseinanderliegen, desto mehr Verfälschungen führen noch zurück zum richtigen Wort.
Die Singleton-Schranke
Die Mindestdistanz ist durch die Coderate begrenzt: Für einen Blockcode mit n gesendeten Bits und k Nutzbits gilt d ≤ n − k + 1. Codes, die diese Schranke erreichen, heißen MDS-Codes (Maximum Distance Separable) – der Reed-Solomon-Code ist ein bekanntes Beispiel, der Hamming(7,4)-Code mit d = 3 liegt mit n − k + 1 = 4 knapp darunter.
Wo die Hamming-Distanz steckt
- Bewertung und Konstruktion von Fehlerkorrektur-Codes in der Fehlererkennung und Vorwärtsfehlerkorrektur
- Suchalgorithmen und Ähnlichkeitsmaße (etwa bei DNA-Sequenzen oder Duplikaterkennung)
- Kryptografie: Avalanche-Effekt von Hashfunktionen als große Distanz zwischen ähnlichen Eingaben
Verwandte Grundlagen: Hamming-Code, Reed-Solomon-Code, Kanalcodierung.