Reed-Solomon-Code

Übersicht

Reed-Solomon-Codes sind Blockcodes. Das bedeutet, dass ein fester Block von Eingabedaten in einen festen Block von Ausgabedaten verarbeitet wird. Im Falle des am häufigsten verwendeten R-S-Codes (255, 223) werden 223 Reed-Solomon-Eingangssymbole (jeweils acht Bits lang) in 255 Ausgangssymbole kodiert.

• Die meisten R-S ECC-Systeme sind systematisch. Das bedeutet, dass ein Teil des Ausgabe-Codeworts die Eingabedaten in ihrer ursprünglichen Form enthält.
• Es wurde eine Reed-Solomon-Symbolgröße von acht Bits gewählt, weil die Decoder für größere Symbolgrößen mit der derzeitigen Technologie schwer zu implementieren wären. Diese Designwahl zwingt die längste Codewortlänge auf 255 Symbole.
• Der Standard (255, 223) Reed-Solomon-Code ist in der Lage, bis zu 16 Reed-Solomon-Symbol-Fehler in jedem Codewort zu korrigieren. Da jedes Symbol eigentlich aus acht Bits besteht, bedeutet dies, dass der Code aufgrund des inneren Faltungsdecoders bis zu 16 kurze Fehlerbursts korrigieren kann.

Der Reed-Solomon-Code ist wie der Faltungscode ein transparenter Code. Das bedeutet, dass die Decoder auch dann noch funktionieren, wenn die Kanalsymbole irgendwo entlang der Linie invertiert wurden. Das Ergebnis wird die Ergänzung der Originaldaten sein. Der Reed-Solomon-Code verliert jedoch seine Transparenz, wenn eine virtuelle Nullauffüllung verwendet wird. Aus diesem Grund ist es zwingend erforderlich, dass der Sinn der Daten (d.h. wahr oder ergänzt) vor der Reed-Solomon-Dekodierung aufgelöst wird.

Im Fall des Voyager-Programms erreichen R-S-Codes nahezu optimale Leistung, wenn sie mit dem (7, 1/2) inneren Faltungscode (Viterbi) verkettet werden. Da für jeden zu korrigierenden Fehler zwei Prüfsymbole erforderlich sind, ergibt sich eine Gesamtzahl von 32 Prüfsymbolen und 223 Informationssymbolen pro Codewort.

Darüber hinaus können die Reed-Solomon-Kodewörter auf Symbolbasis verschachtelt werden, bevor sie faltend kodiert werden. Da dies die Symbole in einem Codewort voneinander trennt, wird es unwahrscheinlicher, dass ein Burst des Viterbi-Decoders mehr als ein Reed-Solomon-Symbol in einem Codewort stört.

Grundidee

Die Schlüsselidee hinter einem Reed-Solomon-Code ist, dass die kodierten Daten zunächst als Polynom visualisiert werden. Der Code stützt sich auf ein Theorem aus der Algebra, das besagt, dass alle k verschiedenen Punkte ein Polynom mit einem Grad von höchstens k-1 eindeutig bestimmen.

Der Absender bestimmt ein Polynom vom Grad k - 1 {\Anzeigestil k-1} über ein endliches Feld, das die k Datenpunkte vom Typ {\Anzeigestil k} repräsentiert. Das Polynom wird dann durch seine Auswertung an verschiedenen Punkten "kodiert", und diese Werte sind das, was tatsächlich gesendet wird. Während der Übertragung können einige dieser Werte verfälscht werden. Daher werden tatsächlich mehr als k Punkte gesendet. Solange genügend Werte korrekt empfangen werden, kann der Empfänger ableiten, was das ursprüngliche Polynom war, und die ursprünglichen Daten dekodieren.

Im gleichen Sinne, wie man eine Kurve durch Interpolation an einer Lücke vorbei korrigieren kann, kann ein Reed-Solomon-Code eine Reihe von Fehlern in einem Datenblock überbrücken, um die Koeffizienten des Polynoms wiederherzustellen, das die ursprüngliche Kurve gezeichnet hat.

Geschichte

Der Code wurde 1960 von Irving S. Reed und Gustave Solomon erfunden, die damals Mitglieder des MIT-Lincoln-Labors waren. Ihr bahnbrechender Artikel trug den Titel "Polynomial Codes over Certain Finite Fields". Als er geschrieben wurde, war die digitale Technologie noch nicht weit genug fortgeschritten, um das Konzept umzusetzen. Die erste Anwendung von RS-Codes in Massenprodukten im Jahre 1982 war die Compact Disc, bei der zwei verschachtelte RS-Codes verwendet werden. Ein effizienter Dekodieralgorithmus für RS-Codes mit großen Abständen wurde 1969 von Elwyn Berlekamp und James Massey entwickelt. Heute werden RS-Codes in Festplatten-, DVD-, Telekommunikations- und digitalen Rundfunkprotokollen verwendet.