Fehlerkorrekturcodes: Zuverlässige Kommunikation über verrauschte Kanäle

simulation intermediate ~12 min
Simulation wird geladen...

Formel

\text{Hamming}(7,4): \text{syndrome} = H \cdot r^T
R = \frac{k}{n} = \frac{4}{7} \approx 0.571
P_{\text{block error}} = 1 - (1-p)^n - n \cdot p \cdot (1-p)^{n-1}
d_{\min} = 3 \implies \text{corrects } \lfloor(3-1)/2\rfloor = 1 \text{ error}
Jedes digitale Kommunikationssystem steht vor demselben fundamentalen Problem: Rauschen verfälscht Daten. Bits kippen, Signale verblassen, und Störungen dringen ein. Fehlerkorrekturcodes lösen dieses Problem, indem sie strukturierte Redundanz hinzufügen, die es dem Empfänger ermöglicht, Fehler zu erkennen und zu beheben, ohne eine erneute Übertragung anzufordern. Der einfachste Ansatz ist die Wiederholung: Jedes Bit dreimal senden und per Mehrheitsentscheid abstimmen. Dies korrigiert einzelne Bitfehler pro Dreiergruppe, verschwendet aber zwei Drittel der Kanalkapazität. Richard Hamming, frustriert von fehleranfälligen Lochkartenlesern bei den Bell Labs, erfand 1950 eine weitaus elegantere Lösung. Hamming(7,4) codiert 4 Datenbits in 7 Codebits, indem 3 Paritätsbits an sorgfältig gewählten Positionen hinzugefügt werden. Jedes Paritätsbit deckt eine bestimmte überlappende Teilmenge der Datenbits ab. Wenn ein einzelner Bitfehler während der Übertragung auftritt, berechnet der Empfänger das Syndrom — das Ergebnis der Überprüfung aller drei Paritätsgleichungen. Das Syndrom ist eine 3-Bit-Zahl, die direkt die Position des Fehlers angibt (0 bedeutet kein Fehler). Der Empfänger kippt einfach dieses Bit, um die Originaldaten wiederherzustellen. Dieser Simulator lässt Sie Hunderte von Datenblöcken durch einen verrauschten Kanal senden und drei Strategien vergleichen: keine Codierung (Rohübertragung), Wiederholungscodierung und Hamming-Codierung. Beobachten Sie, wie Fehler (in Rot dargestellt) die übertragenen Bits verfälschen, Paritätsbits (in Cyan dargestellt) die Erkennung ermöglichen und der Decoder den Schaden korrigiert. Die tiefere Lehre ist Shannons Kanalcodierungstheorem: Für jeden verrauschten Kanal existiert ein Codierungsschema, das zuverlässige Kommunikation mit jeder Rate unterhalb der Kanalkapazität erreicht. Hamming-Codes sind ein früher, praktischer Schritt in Richtung dieses theoretischen Versprechens. Moderne Codes wie LDPC und Turbo-Codes kommen Shannons Grenze bemerkenswert nahe.

Häufige Fragen

Was ist ein Hamming-Code?

Ein Hamming-Code ist ein linearer fehlerkorrigierender Code, den Richard Hamming 1950 erfand. Die gängigste Variante, Hamming(7,4), codiert 4 Datenbits in 7 Codebits, indem 3 Paritätsbits an den Positionen 1, 2 und 4 hinzugefügt werden. Jedes Paritätsbit deckt eine bestimmte Teilmenge der Datenbits ab. Das Syndrom — berechnet durch Prüfung aller Paritätsgleichungen — identifiziert die Position eines einzelnen Bitfehlers und ermöglicht die Korrektur ohne erneute Übertragung.

Wie hängt Fehlerkorrektur mit Shannons Kanalcodierungstheorem zusammen?

Shannons Kanalcodierungstheorem (1948) beweist, dass für jeden Kanal mit Kapazität C zuverlässige Kommunikation mit jeder Rate unterhalb von C möglich ist, wenn ausreichend lange Codes verwendet werden. Hamming-Codes sind kurze, einfache Codes, die Einzelfehler korrigieren. Moderne Codes wie Turbo-Codes und LDPC-Codes nähern sich Shannons Grenze viel stärker an, indem sie längere Blocklängen und iterative Decodierung verwenden.

Was ist der Unterschied zwischen Fehlererkennung und Fehlerkorrektur?

Fehlererkennung identifiziert, dass ein Fehler aufgetreten ist, aber nicht wo. Ein einfaches Paritätsbit kann jeden einzelnen Bitfehler erkennen. Fehlerkorrektur erkennt und lokalisiert den Fehler, sodass der Empfänger ihn beheben kann. Hamming(7,4) kann jeden Einzelbitfehler korrigieren und jeden Zwei-Bit-Fehler erkennen (aber nicht korrigieren). Korrektur erfordert mehr Redundanz als bloße Erkennung.

Wo werden Fehlerkorrekturcodes in der Praxis eingesetzt?

Fehlerkorrekturcodes sind allgegenwärtig: ECC-RAM verwendet Hamming-Codes zur Behebung von Speicher-Bitkippern; QR-Codes verwenden Reed-Solomon-Codes für Schadenstoleranz; Festplatten, SSDs und optische Datenträger nutzen LDPC- und Reed-Solomon-Codes; 5G-Mobilfunknetze verwenden Polar- und LDPC-Codes; Weltraumkommunikation nutzt Faltungs- und Turbo-Codes, um über Milliarden Kilometer Kontakt zu halten.

Quellen

Weitere Simulationen: Informationstheorie

simulation

Kanalkapazität-Explorer
simulation

Datenkompression-Simulator
simulation

Shannon-Entropie-Rechner
View source on GitHub