Gekippte Bits
Syndrom
Empfangen
Datenbits pro gesendetem Bit

Mehr über fehlerkorrigierende Codes

Simulator für fehlerkorrigierende Codes

Jede Nachricht, die durch ein Kabel, durch die Luft oder über eine zerkratzte Disc reist, fängt sich Fehler ein: Bits kippen von 0 auf 1 und zurück. Ein fehlerkorrigierender Code fügt einige sorgfältig gewählte zusätzliche Bits hinzu, damit der Empfänger den Schaden finden und reparieren kann, ohne nachzufragen. Geben Sie vier Datenbits ein, sehen Sie, wie Richard Hammings Code daraus sieben macht, kippen Sie ein beliebiges Bit und beobachten Sie, wie drei überlappende Kreise direkt auf den Fehler zeigen. Senden Sie dann eine ganze Nachricht durch einen verrauschten Kanal und vergleichen Sie, was mit und ohne Code ankommt. Geben Sie vier Datenbits ein, etwa 1011, und die App fügt drei Paritätsbits hinzu, sodass ein 7-Bit-Hamming-Codewort entsteht. Klicken Sie auf ein beliebiges Bit, in den Kreisen oder in der Zeile, um es wie durch Rauschen zu kippen; ein zweiter Klick kippt es zurück. Jeder Kreis muss eine gerade Anzahl von Einsen enthalten: Die Kreise, deren Prüfung fehlschlägt, zeigen auf das falsche Bit, und der Decoder kippt es zurück. Schalten Sie das zusätzliche Paritätsbit ein, um zu sehen, wie zwei Fehler erkannt statt falsch korrigiert werden. Weiter unten senden Sie einen Text mit und ohne Code durch einen verrauschten Kanal.

Wie es funktioniert

  1. Geben Sie vier Datenbits ein und sehen Sie das 7-Bit-Codewort mit seinen drei Paritätsbits, in Kreisen und in einer Zeile.
  2. Klicken Sie auf Bits, um sie zu kippen, und beobachten Sie, welche Kreise fehlschlagen, wohin das Syndrom zeigt und ob der Decoder das Wort repariert.
  3. Schalten Sie das zusätzliche Paritätsbit ein, senden Sie dann eine Nachricht durch den verrauschten Kanal und vergleichen Sie die Ergebnisse mit und ohne Code.

Wie der Hamming-Code einen Fehler findet

Die sieben Bits sind von 1 bis 7 nummeriert. Die Bits 1, 2 und 4 sind Paritätsbits, die vier Datenbits stehen an den Positionen 3, 5, 6 und 7. Paritätsbit 1 macht die Anzahl der Einsen unter den Positionen 1, 3, 5 und 7 gerade, also unter den Positionen, deren Nummer im Binärsystem auf 1 endet; Bit 2 tut dasselbe für 2, 3, 6 und 7 und Bit 4 für 4, 5, 6 und 7. Zeichnet man die Prüfungen als drei überlappende Kreise, liegt jedes Bit in genau den Kreisen, die es prüfen. Kippt ein Bit, werden die Kreise, die es enthalten, ungerade. Liest man die fehlschlagenden Prüfungen als Binärzahl, das Syndrom, erhält man die Position des falschen Bits.

Was ein zusätzliches Bit bringt

Bei zwei gekippten Bits zeigt das Syndrom auf ein drittes, unschuldiges Bit, und der Decoder macht alles schlimmer. Ein achtes Bit, das das ganze Wort gerade macht, behebt das: Ein Fehler ändert die Gesamtparität, zwei Fehler lassen sie gerade, während einige Kreise fehlschlagen. Der erweiterte Code, bekannt als SECDED (Single Error Correction, Double Error Detection: Einzelfehlerkorrektur, Doppelfehlererkennung), korrigiert einen Fehler und erkennt zwei zuverlässig, sodass der Empfänger diesen Block erneut anfordern kann. Es ist der Code, der im ECC-Speicher von Servern verwendet wird. Über einen verrauschten Kanal macht der Code aus vielen verstreuten Fehlern wenige, solange zwei gekippte Bits selten im selben Block landen.

Häufig gestellte Fragen

Warum stehen die Paritätsbits an den Positionen 1, 2 und 4?

Weil das die Zweierpotenzen sind und jede von ihnen im Binärsystem eine einzige 1 hat. Paritätsbit 2ᵏ prüft jede Position, deren Binärzahl an Stelle k eine 1 hat. Ein gekipptes Bit an Position 6 = 110 im Binärsystem verletzt die Prüfungen von 2 und 4 und lässt 1 unberührt, und die fehlschlagenden Prüfungen ergeben 110, die Position selbst.

Was kostet der Schutz?

Der (7,4)-Code sendet 7 Bits für je 4 Datenbits, eine Rate von 4/7: 75 % mehr. Der erweiterte Code sendet 8 für 4, das Doppelte. Längere Hamming-Codes sind günstiger: 15 Bits tragen 11 Datenbits, 31 tragen 26. Moderne Codes wie LDPC- und Polar-Codes, die in WLAN und 5G verwendet werden, kommen sehr nahe an die beste Rate heran, deren Erreichbarkeit Claude Shannon 1948 bewiesen hat.

Was passiert bei drei Fehlern?

Der einfache Hamming-Code kann vollständig getäuscht werden: Zwei Codewörter unterscheiden sich in mindestens drei Bits, also können drei gekippte Bits ein gültiges Codewort in ein anderes verwandeln, und keine einzige Prüfung schlägt fehl. Die App meldet das als „Fehler nicht bemerkt“. Reale Systeme halten solche Fälle selten, indem sie einen Code wählen, der für den Rauschpegel stark genug ist.

Wo werden fehlerkorrigierende Codes eingesetzt?

Fast überall, wo digitale Daten übertragen oder gespeichert werden: ECC-Arbeitsspeicher, Festplatten und SSDs, CDs, DVDs und Blu-ray-Discs, QR-Codes, die auch mit einem abgerissenen Stück lesbar bleiben, Mobiltelefone und WLAN, Digitalfernsehen und Nachrichten von Raumsonden wie Voyager, die noch immer Daten von jenseits des Sonnensystems senden.

Wird meine Nachricht irgendwohin gesendet?

Nein. Der verrauschte Kanal wird in Ihrem Browser simuliert, und Ihre Nachricht und Ihre Einstellungen bleiben im lokalen Speicher dieses Browsers.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Zum Editor