Der Reed-Solomon-Code (RS-Code) ist ein fehlerkorrigierender Blockcode, der 1960 von Irving S. Reed und Gustave Solomon entwickelt wurde. Anders als der Hamming-Code arbeitet er nicht auf einzelnen Bits, sondern auf ganzen Symbolen (meist Bytes) – genau das macht ihn extrem robust gegen Bündelfehler wie Kratzer auf einer CD oder Störpulse im Funkkanal.
So funktioniert er
Der Sender fasst die Nutzdaten als Koeffizienten eines Polynoms auf und berechnet daraus zusätzliche Prüfwerte über einem Galois-Feld – bei Byte-orientierten Codes dem Körper GF(256) mit 256 Elementen. Aus k Nutzsymbolen entsteht so ein Codewort aus n Symbolen. Der Empfänger rekonstruiert aus den empfangenen (teils verfälschten) Werten das ursprüngliche Polynom. Solange die Zahl der Fehler eine Grenze nicht überschreitet, kann er jedes falsche Symbol lokalisieren und korrigieren – auch wenn ein ganzer Burst zusammenhängender Bits zerstört wurde.
Leistungsdaten
- Der Standard-Code RS(255,223) erzeugt aus 223 Nutzbytes 32 Prüfbytes und korrigiert damit bis zu 16 Symbolfehler pro Block.
- RS-Codes sind MDS-Codes: Sie erreichen die Singleton-Schranke (siehe Hamming-Distanz) und holen damit das theoretische Maximum aus ihren Parametern heraus.
- Die Coderate lässt sich je nach Anwendung wählen: mehr Prüfbytes = höhere Korrekturfähigkeit, aber geringerer Nutzdatenanteil.
Wo Reed-Solomon steckt
- CD, DVD und Blu-ray: CIRC (Cross-Interleaved Reed-Solomon Code) macht CDs selbst bei Kratzern abspielbar
- QR-Codes: bleiben dank RS-Fehlerkorrektur auch bei Verschmutzung oder Beschädigung lesbar
- Raumfahrt: die Voyager-Sonden übertrugen ihre berühmten Bilder mit RS-codierten Daten
- Satellitenfernsehen (DVB), DSL/ADSL und viele Speichermedien
Reed-Solomon ist damit der Standardvertreter der FEC-Codes aus der Vorwärtsfehlerkorrektur – ein zentrales Verfahren der Kanalcodierung. Für den Löschkanal, auf dem ganze Pakete verloren gehen statt einzelner Bits, gibt es mit dem Fountain-Code eine ratenlose Alternative, die beliebig viele Prüfsymbole erzeugt.
aus der Vorwärtsfehlerkorrektur – ein zentrales Verfahren der Kanalcodierung.Verwandte Grundlagen: Hamming-Code, Hamming-Distanz, Kanalcodierung, Vorwärtsfehlerkorrektur.