Fehlerkorrigierende Codes erklärt
Kein Kanal ist perfekt. Kosmische Strahlung kippt Bits im Speicher, Kratzer löschen Teile einer Disc, und Funksignale werden schwächer. Statt auf das Beste zu hoffen, fügen digitale Systeme auf geschickte Weise Redundanz hinzu, damit der Empfänger herausfinden kann, was gesendet wurde, selbst wenn ein Teil davon falsch ankommt. Die Mathematik dieser Codes, begonnen Ende der 1940er-Jahre, schützt im Stillen fast jedes Bit, das wir speichern oder senden.
Fehler mit Parität erkennen
Der einfachste Schutz ist ein einzelnes Paritätsbit: Man fügt eine 1 oder eine 0 hinzu, sodass die Gesamtzahl der Einsen gerade ist. Kippt unterwegs ein Bit, wird die Anzahl ungerade, und der Empfänger weiß, dass etwas schiefgelaufen ist. Parität kann nicht sagen, welches Bit falsch ist, und zwei gekippte Bits heben sich unbemerkt auf, aber sie ist billig und wurde jahrzehntelang in Speichern und seriellen Verbindungen eingesetzt. Einen Fehler zu erkennen ist allerdings nur die halbe Arbeit: Danach müssen die Daten erneut gesendet werden.
Korrigieren durch Wiederholung
Um einen Fehler ohne Nachfrage zu korrigieren, braucht der Empfänger genug Redundanz, um ihn zu überstimmen. Wird jedes Bit dreimal gesendet, 000 oder 111, kann der Empfänger der Mehrheit folgen: Ein gekipptes Bit in einem Tripel wird korrigiert. Der Preis ist hoch: drei Bits für jedes Datenbit, und zwei gekippte Bits im selben Tripel setzen sich trotzdem durch. Die Frage, mit der die Codierungstheorie begann, war, ob es besser geht.
Hammings Code
1947 arbeitete Richard Hamming an den Bell Labs an einem Relaisrechner, der Programme von Lochkarten las. Fand der Rechner am Wochenende einen Fehler, hielt er einfach an, und Hamming fand am Montag nur verlorene Rechenläufe vor. Wenn eine Maschine einen Fehler erkennen kann, fragte er sich, warum kann sie ihn dann nicht lokalisieren und korrigieren? Seine Antwort, 1950 veröffentlicht, sendet 4 Datenbits als 7. Drei Paritätsbits an den Positionen 1, 2 und 4 prüfen jeweils eine andere, überlappende Gruppe von Positionen, so gewählt, dass jeder Einzelfehler eine eindeutige Kombination von Prüfungen verletzt.
Das Syndrom
Der Empfänger berechnet die drei Prüfungen neu. Bestehen alle, wird das Wort angenommen. Schlagen einige fehl, schreibt man die fehlschlagenden Prüfungen als Binärziffern, mit Prüfung 4 als höchster Stelle, und erhält eine Zahl von 1 bis 7: das Syndrom, das genau die Position des gekippten Bits angibt. Kippt man es zurück, ist das Codewort wiederhergestellt. Der Trick funktioniert, weil die Positionen so nummeriert sind, dass die Binärdarstellung jeder Position die Prüfungen auflistet, zu denen sie gehört; deshalb sieht der Code so ordentlich aus, wenn man ihn als drei überlappende Kreise zeichnet.
Hamming-Abstand
Der Hamming-Abstand zwischen zwei Wörtern ist die Anzahl der Positionen, an denen sie sich unterscheiden. Im (7,4)-Code haben zwei Codewörter immer mindestens den Abstand 3. Ein Wort mit einem Fehler hat noch den Abstand 1 zum gesendeten Codewort und mindestens 2 zu jedem anderen, also korrigiert es die Decodierung zum nächstgelegenen Codewort. Allgemein erkennt ein Code, dessen Codewörter mindestens d auseinanderliegen, d − 1 Fehler und korrigiert (d − 1)/2 davon, abgerundet. Ein zusätzliches Gesamtparitätsbit erhöht den Abstand auf 4 und ergibt den erweiterten Code, der einen Fehler korrigiert und zwei erkennt.
Shannons Grenze
1948, zwei Jahre vor Hammings Arbeit, bewies Claude Shannon einen verblüffenden Satz. Jeder verrauschte Kanal hat eine Kapazität, und mit jeder Rate unterhalb davon lassen sich Daten mit beliebig wenigen Fehlern senden, wenn man ausreichend lange Codes verwendet; oberhalb davon sind Fehler unvermeidlich. Shannon zeigte, dass solche Codes existieren, aber nicht, wie man sie konstruiert. Praktische Codes zu finden, die seiner Grenze nahekommen, dauerte ein halbes Jahrhundert, von den Reed-Solomon-Codes 1960 über die Turbo-Codes 1993 bis zur Wiederentdeckung der LDPC-Codes (Low-Density-Parity-Check-Codes).
Codes überall um uns herum
Reed-Solomon-Codes lassen CDs trotz Kratzern abspielen und QR-Codes auch dann scannen, wenn bis zu 30 % des Symbols beschädigt sind. Serverspeicher nutzt erweiterte Hamming-Codes, um einzelne, durch kosmische Strahlung gekippte Bits zu beheben. Die Bilder der äußeren Planeten von Voyager wurden durch Golay- und später Reed-Solomon-Codes geschützt, und die LDPC- und Polar-Codes von 5G und WLAN holen fast jedes Bit heraus, das der Kanal zulässt. Sogar der Strichcode auf einem Buch und die letzte Ziffer einer Kontonummer sind einfache fehlererkennende Codes.
Selbst ausprobieren
Öffnen Sie den Simulator für fehlerkorrigierende Codes, um beliebige vier Datenbits mit dem Hamming-(7,4)-Code zu codieren, Bits per Klick in den Kreisen oder in der Zeile zu kippen und zu beobachten, wie die fehlschlagenden Kreise und das Syndrom auf den Fehler zeigen, bevor der Decoder ihn repariert. Schalten Sie das zusätzliche Paritätsbit ein, um zu sehen, wie Doppelfehler erkannt werden, und senden Sie eine Nachricht durch einen verrauschten Kanal, um zu vergleichen, was mit und ohne Code ankommt.
Häufig gestellte Fragen
Was ist der Unterschied zwischen Fehlererkennung und Fehlerkorrektur?
Erkennung sagt dem Empfänger nur, dass etwas nicht stimmt, sodass er die Daten erneut anfordern muss; ein Paritätsbit oder eine Prüfsumme leistet das. Korrektur lässt den Empfänger das Original ohne Nachfrage rekonstruieren, was mehr Redundanz erfordert. Systeme, die nicht nachfragen können, etwa eine Raumsonde in Millionen Kilometern Entfernung oder eine DVD, sind auf Korrektur angewiesen.
Warum nicht einfach alles zweimal senden?
Zwei Kopien zeigen, dass ein Fehler aufgetreten ist, aber nicht, welche Kopie richtig ist, und sie verdoppeln die Kosten. Drei Kopien erlauben eine Mehrheitsentscheidung, verdreifachen die Kosten aber. Hammings Code korrigiert einen Einzelfehler pro Block aus sieben Bits mit weniger als der doppelten Bitzahl, und längere Codes schneiden noch weit besser ab.
Wer war Richard Hamming?
Ein US-amerikanischer Mathematiker, 1915 bis 1998, der am Manhattan-Projekt mitarbeitete und danach dreißig Jahre lang an den Bell Labs. Neben seinen Codes ist er bekannt für das Hamming-Fenster in der Signalverarbeitung, für den Hamming-Abstand und für seinen Vortrag „You and Your Research“. 1968 erhielt er den Turing Award.
Kann ein Code beliebig viele Fehler korrigieren?
Nur mit genügend Redundanz. Ein Code kann bis zu (d − 1)/2 Fehler pro Block korrigieren, wobei d der Mindestabstand zwischen Codewörtern ist, und längere Codes mit mehr Prüfbits erreichen ein größeres d. Shannons Satz setzt die endgültige Grenze: Kein Code kann die Kapazität des Kanals übertreffen.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Simulator für fehlerkorrigierende Codes öffnen