Hamming-Code

Der Hamming-Code ist ein linearer, fehlerkorrigierender Blockcode, den Richard Hamming 1950 bei den Bell Labs entwickelte. Anlass war ein sehr praktisches Problem: Die damaligen Lochkarten-Rechenmaschinen erkannten zwar per einfacher Parität, dass ein Fehler aufgetreten war, mussten die Berechnung dann aber komplett abbrechen und neu starten — es gab keine Möglichkeit, den Fehler zu lokalisieren und automatisch zu beheben. Hammings Idee: mehrere, geschickt überlappende Paritätsprüfungen so zu kombinieren, dass ihr gemeinsames Ergebnis nicht nur ob, sondern auch wo ein Fehler steckt.

1. Warum einfache Parität nicht reicht

Ein einzelnes Paritätsbit über einen ganzen Datenblock erkennt einen Bitfehler (die Parität stimmt nicht mehr), sagt aber nichts über die Position aus — von $n$ möglichen Fehlerpositionen bleiben alle gleich wahrscheinlich. Hammings Ansatz verwendet stattdessen mehrere Paritätsbits, von denen jedes nur eine bestimmte Teilmenge der Bitpositionen überwacht. Die Teilmengen sind so gewählt, dass jede Bitposition durch eine eigene, eindeutige Kombination von Paritätsprüfungen abgedeckt wird — die Positionen der fehlschlagenden Prüfungen ergeben zusammen direkt die Fehlerposition als Binärzahl.

2. Aufbau des Hamming(7,4)-Codes

Die kompakteste und am häufigsten zitierte Variante ist Hamming(7,4): aus $k=4$ Nutzdatenbits werden $n=7$ Gesamtbits, also $r = n-k = 3$ Redundanzbits.

Die Paritätsbits $p_1, p_2, p_4$ stehen bewusst auf den Zweierpotenz-Positionen (1, 2, 4) — nur an diesen Stellen hat die Binärdarstellung der Position genau ein gesetztes Bit. Die Regel für die Zuordnung: Paritätsbit an Position $2^i$ überwacht genau die Positionen, deren Binärdarstellung an Bitstelle $i$ eine 1 hat.

Jedes Paritätsbit wird als XOR (gerade Parität) über die von ihm überwachten Datenbits berechnet:

$$p_1 = d_1 \oplus d_2 \oplus d_4 \qquad p_2 = d_1 \oplus d_3 \oplus d_4 \qquad p_4 = d_2 \oplus d_3 \oplus d_4$$

3. Kodierung: ein durchgerechnetes Beispiel

Ausgeschrieben: $d_1{=}1$, $d_2{=}0$, $d_3{=}1$, $d_4{=}1$ liegen an Position 3, 5, 6, 7. Damit:

$$p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0$$
$$p_2 = d_1 \oplus d_3 \oplus d_4 = 1 \oplus 1 \oplus 1 = 1$$
$$p_4 = d_2 \oplus d_3 \oplus d_4 = 0 \oplus 1 \oplus 1 = 0$$

Das vollständige Codewort (Position 1–7) lautet damit $p_1\,p_2\,d_1\,p_4\,d_2\,d_3\,d_4 = 0\,1\,1\,0\,0\,1\,1$.

4. Fehlererkennung und -korrektur per Syndrom

Der Empfänger wiederholt alle drei Paritätsprüfungen über das empfangene Codewort und bildet aus den Ergebnissen das Syndrom $s = p_4\,p_2\,p_1$ (als 3-Bit-Binärzahl gelesen). Der entscheidende Trick der Positionswahl: Ist $s \neq 0$, gibt $s$ direkt die Dezimalposition des fehlerhaften Bits an — keine Suchtabelle, keine weitere Berechnung nötig.

Das ist kein Zufall, sondern folgt direkt aus der Konstruktion: Kippt ein einzelnes Bit an Position $x$, schlagen genau die Paritätsprüfungen fehl, deren überwachte Menge $x$ enthält — und das sind laut Tabelle in Abschnitt 2 genau die Prüfungen, deren Bitmasken zusammen die Binärdarstellung von $x$ ergeben.

5. Hamming-Distanz und Korrekturvermögen

Die Hamming-Distanz zwischen zwei Codewörtern ist die Anzahl der Bitpositionen, in denen sie sich unterscheiden. Für einen Code ist die Minimaldistanz $d_{\min}$ die kleinste Distanz zwischen zwei beliebigen gültigen Codewörtern — sie bestimmt das Korrekturvermögen:

$$t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor \text{ korrigierbare Bitfehler}$$

Hamming(7,4) hat $d_{\min}=3$ (je zwei gültige Codewörter unterscheiden sich in mindestens 3 Bits), also $t = \lfloor 2/2 \rfloor = 1$: genau ein Bitfehler pro Codewort ist korrigierbar. Ein zweiter Bitfehler im selben Codewort erzeugt zwar ein von Null verschiedenes Syndrom, zeigt aber auf die falsche Position — der Standard-Hamming-Code erkennt Doppelfehler nicht zuverlässig als solche und würde sie fälschlich "korrigieren".

6. Erweiterter Hamming-Code: SECDED

Für Anwendungen, die zusätzlich Doppelfehler zuverlässig erkennen (wenn auch nicht korrigieren) müssen, wird ein zusätzliches Gesamtparitätsbit über alle 7 Bits ergänzt — der resultierende Hamming(8,4)-Code heißt SECDED (Single Error Correction, Double Error Detection):

Die Unterscheidung der vier Fälle beim Dekodieren:

7. Referenzimplementierung in Python

def encode74(d1, d2, d3, d4):
    """Hamming(7,4): liefert Codewort als Liste [Bit an Position 1..7]."""
    bits = [0] * 8  # Index 0 ungenutzt, Positionen 1..7
    bits[3], bits[5], bits[6], bits[7] = d1, d2, d3, d4
    bits[1] = bits[3] ^ bits[5] ^ bits[7]   # p1: Positionen 1,3,5,7
    bits[2] = bits[3] ^ bits[6] ^ bits[7]   # p2: Positionen 2,3,6,7
    bits[4] = bits[5] ^ bits[6] ^ bits[7]   # p4: Positionen 4,5,6,7
    return bits[1:8]

def syndrome(code7):
    """Berechnet das 3-Bit-Syndrom; 0 = fehlerfrei, sonst = Fehlerposition."""
    b = [0] + list(code7)
    p1 = b[1] ^ b[3] ^ b[5] ^ b[7]
    p2 = b[2] ^ b[3] ^ b[6] ^ b[7]
    p4 = b[4] ^ b[5] ^ b[6] ^ b[7]
    return p4 * 4 + p2 * 2 + p1

def encode84(d1, d2, d3, d4):
    """SECDED: Hamming(7,4) plus Gesamtparität als Bit 8."""
    code7 = encode74(d1, d2, d3, d4)
    return code7 + [sum(code7) % 2]

# Kodierung
msg = (1, 0, 1, 1)
code = encode74(*msg)
print("Codewort:", code, "Syndrom (fehlerfrei):", syndrome(code))

# Einzelfehler an Position 5 injizieren und korrigieren
corrupted = code[:]
corrupted[5 - 1] ^= 1
s = syndrome(corrupted)
corrected = corrupted[:]
if s != 0:
    corrected[s - 1] ^= 1
print("Fehler an Pos. 5, Syndrom:", s, "korrigiert korrekt:", corrected == code)

# SECDED: Doppelfehler an Position 2 und 5
ext = encode84(*msg)
dbl = ext[:]
dbl[2 - 1] ^= 1
dbl[5 - 1] ^= 1
s2 = syndrome(dbl[:7])
overall_ok = (sum(dbl) % 2 == 0)
print("Doppelfehler erkannt (Syndrom != 0 und Parität passt):", s2 != 0 and overall_ok)

def encode74(d1, d2, d3, d4):
    """Hamming(7,4): liefert Codewort als Liste [Bit an Position 1..7]."""
    bits = [0] * 8  # Index 0 ungenutzt, Positionen 1..7
    bits[3], bits[5], bits[6], bits[7] = d1, d2, d3, d4
    bits[1] = bits[3] ^ bits[5] ^ bits[7]   # p1: Positionen 1,3,5,7
    bits[2] = bits[3] ^ bits[6] ^ bits[7]   # p2: Positionen 2,3,6,7
    bits[4] = bits[5] ^ bits[6] ^ bits[7]   # p4: Positionen 4,5,6,7
    return bits[1:8]

def syndrome(code7):
    """Berechnet das 3-Bit-Syndrom; 0 = fehlerfrei, sonst = Fehlerposition."""
    b = [0] + list(code7)
    p1 = b[1] ^ b[3] ^ b[5] ^ b[7]
    p2 = b[2] ^ b[3] ^ b[6] ^ b[7]
    p4 = b[4] ^ b[5] ^ b[6] ^ b[7]
    return p4 * 4 + p2 * 2 + p1

def encode84(d1, d2, d3, d4):
    """SECDED: Hamming(7,4) plus Gesamtparität als Bit 8."""
    code7 = encode74(d1, d2, d3, d4)
    return code7 + [sum(code7) % 2]

# Kodierung
msg = (1, 0, 1, 1)
code = encode74(*msg)
print("Codewort:", code, "Syndrom (fehlerfrei):", syndrome(code))

# Einzelfehler an Position 5 injizieren und korrigieren
corrupted = code[:]
corrupted[5 - 1] ^= 1
s = syndrome(corrupted)
corrected = corrupted[:]
if s != 0:
    corrected[s - 1] ^= 1
print("Fehler an Pos. 5, Syndrom:", s, "korrigiert korrekt:", corrected == code)

# SECDED: Doppelfehler an Position 2 und 5
ext = encode84(*msg)
dbl = ext[:]
dbl[2 - 1] ^= 1
dbl[5 - 1] ^= 1
s2 = syndrome(dbl[:7])
overall_ok = (sum(dbl) % 2 == 0)
print("Doppelfehler erkannt (Syndrom != 0 und Parität passt):", s2 != 0 and overall_ok)

Ausgabe:

Codewort: [0, 1, 1, 0, 0, 1, 1] Syndrom (fehlerfrei): 0
Fehler an Pos. 5, Syndrom: 5 korrigiert korrekt: True
Doppelfehler erkannt (Syndrom != 0 und Parität passt): True

Codewort: [0, 1, 1, 0, 0, 1, 1] Syndrom (fehlerfrei): 0
Fehler an Pos. 5, Syndrom: 5 korrigiert korrekt: True
Doppelfehler erkannt (Syndrom != 0 und Parität passt): True

8. Praktischer Einsatz

Digitaler Sprechfunk (DMR): Der DMR-Standard (ETSI TS 102 361), einer der verbreiteten Digitalsprech-Modi im Amateurfunk, sichert Teile seiner Steuerkanäle — u. a. das Slot-Type-Feld, das den Burst-Typ jedes Zeitschlitzes angibt — mit Hamming-Codes ab. Für andere Felder kommen je nach benötigter Fehlerkorrekturstärke verwandte Verfahren wie Golay- oder Quadratic-Residue-Codes zum Einsatz — ein Beispiel dafür, dass reale Systeme selten nur einen einzigen Code nutzen, sondern je Datenfeld die passend starke (und passend kurze) Variante wählen.

ECC-Arbeitsspeicher (ECC-RAM): Server- und Enterprise-Speicherbausteine nutzen üblicherweise SECDED-Varianten (häufig Hamming(72,64) für 64-Bit-Speicherworte), um durch kosmische Strahlung oder elektrisches Rauschen verursachte Einzelbitfehler automatisch zu korrigieren und Doppelfehler wenigstens als solche zu melden.

NAND-Flash-Speicher: SSDs und Flash-Controller verwenden Hamming- bzw. davon abgeleitete BCH-Codes, um die mit zunehmender Zellendichte häufiger werdenden Bitfehler beim Auslesen zu korrigieren.

Digitale Übertragung mit Rückkanal-Verzicht: Überall dort, wo eine erneute Anfrage bei fehlerhafter Übertragung teuer oder unmöglich ist (Satellitenkommunikation, Deep-Space-Missionen, Speicherzellen ohne Rückkanal), ist Vorwärtsfehlerkorrektur (FEC) wie der Hamming-Code der einzig praktikable Weg, statt auf Neuübertragung per ARQ zu setzen.

9. Grenzen

• Korrektur ist strikt auf einen Bitfehler pro Codewort begrenzt (Standard-Hamming); Mehrfachfehler werden im schlechtesten Fall fälschlich "korrigiert" — ohne das zusätzliche SECDED-Paritätsbit bleibt das unentdeckt.
• Der relative Overhead sinkt zwar mit wachsendem $k$ (bei Hamming(7,4): 3 von 7 Bits Redundanz = 43 %; bei Hamming(31,26): 5 von 31 = 16 %), doch für viele parallele Bitfehler (Burst-Fehler) ist der Hamming-Code ungeeignet — dafür sind Interleaving-Verfahren oder andere Codes (Reed-Solomon, BCH) die passendere Wahl.
• Die Konstruktion setzt voraus, dass Fehler unabhängig und einzeln auftreten; korrelierte Störungen (z. B. ein kompletter Byte-Ausfall) unterlaufen die Ein-Fehler-Annahme.