EMZETT.
Login

Emzett Wiki

Hamming-Code und Fehlerkorrektur: Wie Daten sich selbst reparieren

Properties1
tagsglossar, grundlagen, daten

2 Min. Lesezeit

Hamming-Code und Fehlerkorrektur: Wie Daten sich selbst reparieren

Kurz: Ein Hamming-Code fügt Prüfbits so ein, dass ein einzelner gekippter Bit-Fehler nicht nur erkannt, sondern auch genau lokalisiert und korrigiert werden kann.

Genauer: Ein Paritätsbit sagt nur „etwas stimmt nicht“. Richard Hamming (1950) entwickelte Codes, die zusätzlich zeigen, welches Bit falsch ist: Dann kann man es einfach zurückkippen. Diese Fehlerkorrektur (FEC) steckt in ECC-RAM, Festplatten, Funkverbindungen und Satelliten.

Im Detail

Idee des Hamming-Codes (7,4)

Von 7 Bit sind 4 Datenbits (d1–d4) und 3 Prüfbits (p1–p3). Die Prüfbits stehen an den Stellen 1, 2 und 4 (Zweierpotenzen); jedes prüft die Parität einer Teilmenge von Stellen:

Position:  1  2  3  4  5  6  7
Bit:      p1 p2 d1 p3 d2 d3 d4
p1 prüft Positionen 1,3,5,7
p2 prüft Positionen 2,3,6,7
p3 prüft Positionen 4,5,6,7

Beim Empfang berechnet man die drei Paritäten neu. Ihr Ergebnis (das Syndrom, als Binärzahl gelesen) ist die Position des fehlerhaften Bits (000 = kein Fehler). Dieses Bit wird invertiert.

Rechenbeispiel

Daten 1011 (d1=1, d2=0, d3=1, d4=1). Prüfbits (gerade Parität):

  • p1 = d1 ⊕ d2 ⊕ d4 = 1⊕0⊕1 = 0
  • p2 = d1 ⊕ d3 ⊕ d4 = 1⊕1⊕1 = 1
  • p3 = d2 ⊕ d3 ⊕ d4 = 0⊕1⊕1 = 0 Codewort (p1 p2 d1 p3 d2 d3 d4) = 0 1 1 0 0 1 1. Wird Bit 6 gekippt → 0110011 wird 0110001. Neu berechnet: p1-Prüfung (1,3,5,7) = 0⊕1⊕0⊕1 = 0 ✓; p2-Prüfung (2,3,6,7) = 1⊕1⊕0⊕1 = 1 ✗; p3-Prüfung (4,5,6,7) = 0⊕0⊕0⊕1 = 1 ✗. Syndrom (p3 p2 p1) = 110 = 6 → Bit 6 ist falsch.

Eigenschaften

  • Hamming-Abstand 3: erkennt 2 Bitfehler, korrigiert 1 Bitfehler. Mit einem zusätzlichen Gesamtparitätsbit (SECDED: Single Error Correction, Double Error Detection) werden 2 Fehler erkannt (nicht korrigiert).
  • Overhead: 3 Prüfbits für 4 Datenbits (75 %), bei längeren Wörtern viel geringer: 8 Prüfbits für 64 Datenbits (ECC-RAM: 72 Bit pro Wort).
  • Grenze: Viele Fehler hintereinander (Bursts) brauchen andere Codes.

Wo Fehlerkorrektur eingesetzt wird

  • ECC-Arbeitsspeicher (Server, Workstations) gegen kosmische Strahlung und Bit-Kipper.
  • Reed-Solomon: CDs, DVDs, QR-Codes, Satelliten, RAID 6.
  • LDPC und Turbo-Codes: WLAN, 5G, SSDs, DVB.
  • RAID-Parität (5/6) rekonstruiert ausgefallene Laufwerke.
  • Fehlerkorrektur (FEC) in Streaming und Funk spart Neuübertragungen. Wenn Korrektur nicht möglich ist, verlangen Protokolle (TCP) erneutes Senden.

Siehe auch: Prüfsummen, Parität und CRC, RAID, QR-Code