Stille Post

Es gibt keine perfekten Übertragungs- oder Speichermedien. Früher oder später kommt ein gesendetes Bit falsch beim Empfänger an, oder die Platte liest statt einer 0 eine 1. Man kann lediglich versuchen, die Häufigkeit solcher Fehler – üblicherweise pro Zeiteinheit (Bit Error Rate) oder bezogen auf die Gesamtdatenmenge (Bit Error Ratio) angegeben – auf ein tolerierbares Maß zu senken.

Viele Datenübertragungsverfahren verwenden Prüfsummen, etwa CRC (cyclic redundancy check). Stellt der Empfänger eine Diskrepanz zwischen Daten und Prüfsumme fest, verwirft er das Datenpaket und signalisiert gegebenenfalls dem Absender, dass er es noch einmal schicken muss. Lässt sich diese sogenannte Backward Error Correction nicht verwenden – etwa beim Speichern von Daten –, fügt man redundante Bits hinzu, die es erlauben, eine gewisse Zahl von Bitfehlern zu korrigieren (Forward Error Correction, kurz FEC).

Solche fehlerkorrigierenden Codes (Error Correcting Codes, ECC) kommen bei praktisch allen modernen Speichermedien zum Einsatz. Dabei wägen die Hersteller Aufwand und Einsatzzweck gegeneinander ab: Bei einer typischen Desktop- oder Notebook-Festplatte etwa kann die Bit Error Ratio um den Faktor 100 höher sein als bei einem Modell für Server.

Weniger Fehler durch redundante Bits

Sowohl beim Speichern als auch beim Übertragen von Daten kann man die Bit Error Ratio senken, indem man eine zusätzliche Fehlerkorrektur einbaut. Ein probates Mittel sind die nach ihren Entdeckern benannten Reed-Solomon-Codes. Wer sich mit der zugrunde liegenden Mathematik nicht abmühen möchte, kann sich einer der Implementierungen bedienen, die im Netz zu finden sind.

Die Bibliothek Schifra etwa bietet eine Umsetzung in C++. Leider enthält die freie, unter der GPL erhältliche Version bis auf einige Beispiele keinerlei Dokumentation. Wer das komplette Paket mit allen Features haben möchte, muss eine kommerzielle Lizenz erwerben. Die enthält neben SSE- und AltiVec-optimierten Routinen eine Version in VHDL für den Einsatz in einem FPGA (Field Programmable Gate Array).

Für einfache Anwendungen und für Experimente sollte RSCODE genügen. Die in C geschriebene Bibliothek kann jedoch nur bis zu 255 Byte lange Blöcke erzeugen; die Zahl der Parity-Bytes – und damit die der korrigierbaren Fehler – muss der Entwickler beim Übersetzen angeben. Mit der Compiler-Option -DNPAR=4 etwa lassen sich bis zu zwei Fehler beseitigen.

Flexibler ist die Implementierung in Phil Karns fec-Bibliothek. Sie unterstützt Symbole und Datenblöcke unterschiedlicher Länge und enthält außerdem eine optimierte Version des von der CCSDS (Consultative Committee for Space Data Systems) für Weltraumanwendungen standardisierten RS(255,223)-Codes. Falls vorhanden, macht der Quellcode Gebrauch von den MMX-, SSE(2)- oder AltiVec-Befehlen des Prozessors.

Eine Umsetzung in Python bietet py_ecc. Zwar muss der Programmierer auf maschinenspezifische Optimierungen verzichten. Dafür kann er ähnlich wie bei fec die Codierungs-Parameter frei einstellen. Insbesondere bietet py_ecc die Wahl zwischen systematischen und unsystematischen RS-Codes. Erstere enthalten die eigentlichen Daten im Klartext und werden zum Beispiel beim RAID 6 zur Berechnung der zweiten Prüfsumme verwendet. Eine interessante Anwendung für einen unsystematischen RS-Code hat Cleversafe entwickelt: Der sogenannte Dispersed Storage teilt die verschlüsselten und RS-codierten Daten in mehrere Häppchen und legt sie auf unterschiedlichen Speichersystemen ab. Regenerieren lassen sich die Originaldaten nur, wenn eine ausreichende Zahl der Fragmente zur Verfügung steht.

Eine modernere Alternative zu RS-Codes sind Low-Density-Parity-Check-Codes (LDPC). Sie kommen unter anderem bei DVB-S2, 10-Gigabit-Ethernet und (optional) WLAN nach IEEE 802.11n zum Einsatz, weil sie sich relativ schnell erzeugen und decodieren lassen. Das LDPC-Verfahren arbeitet mit Paritätsbits, in deren Berechnung nur jeweils ein kleiner Teil der Daten eingeht. Implementierungen gibt es in verschiedenen Sprachen, darunter C/C++ und Python.

Alternativen zu Reed-Solomon-Codes

Für serielle Datenübertragung, insbesondere per Funk, bieten sich Faltungscodes (Convolutional Codes) an. Im Gegensatz zu RS- und LDPC-Codes arbeiten sie nicht block-, sondern bitweise. Ist die Fehlerrate zu hoch, kann man zusätzlich einen RS- oder LDPC-Code verwenden – bei der Saturn-Sonde Cassini etwa setzte die NASA den RS(255,223)-Code ein und erreichte damit immerhin eine Bit Error Ratio von weniger als 10^-6.

Zum Decodieren von Faltungscodes nutzt man üblicherweise den Viterbi-Algorithmus, der im Netz in zahlreichen Versionen kursiert – etwa in der fec-Bibliothek. Auf Phil Karns Implementierung beruht auch der Codegenerator des Spiral-Projekts, der Viterbi-Decoder für verschiedene Anwendungen wahlweise in portablem C oder als optimierte SSE-Variante für x86-kompatible Prozessoren erzeugt.

Alle Links: www.ix.de/ix1108131 (mr)