„Reed-Solomon-Code“ – Versionsunterschied

Reed-Solomon-Codes (kurz RS-Codes) sind leistungsfähige Kodierungsverfahren, die beim Lesen oder Empfangen der mit ihnen codierten digitalen Daten erlauben, Fehler zu erkennen und zu korrigieren (Vorwärtsfehlerkorrektur). Bei nach dem DVB-Standard ausgesendeten Fernsehsignalen wird beispielsweise ein RS-Code verwendet, der es dem Empfänger ermöglicht, die Bitfehlerrate des empfangenen Signals um mehr als 6 Zehnerpotenzen zu verbessern.

Diese RS-Codes arbeiten mit Blöcken von Symbolen, die in der Regel jeweils aus 8 Bit bestehen. Sie gehören daher zur Klasse der symbolorientierten Blockcodes. Es handelt sich um eine 1960 von Irving S. Reed und Gustave Solomon gefundene Klasse von Codes, die gute Fehlerkorrektureigenschaften besitzen und für die ein relativ einfacher Decodieralgorithmus existiert. Aufgrund dessen kamen einige Reed-Solomon-Codes bereits in wichtigen Anwendungen zum Einsatz: Die Fehlerkorrektur gewöhnlicher Audio-CDs basiert auf einem Reed-Solomon-Code, und auch im Mobilfunk, im Digital Video Broadcasting (DVB), im Digital Audio Broadcasting (DAB) sowie zur Kommunikation mit Raumsonden (1985 Voyager 2 nach Umprogrammierung, 1989 Galileo zum Jupiter, 1989 Magellan zur Venus und 1990 Ulysses zur Sonne) wurden Reed-Solomon-Codes benutzt.

Definition

Sei $\alpha \in GF(p)$ ein primitives Element aus dem Galoisfeld über p, der Ordnung n und $f(x)\in GF(p)[x]$ ein Polynom vom Grad<k dessen Koeffizienten(aus GF(p)) das Informationswort $(f_{0},..,f_{k-1})$ bilden.

Das Codewort ergibt sich damit zu $a=(a_{0},..,a_{n-1})$ mit $a_{i}=f(\alpha ^{i})$.

Der RS-Code zu $\alpha \in GF(p)$ und n kann also dargestellt werden als $C=\{a|(a_{i}=f(\alpha ^{i});0\leq i\leq (n-1));f\in GF(p)[x]\ mit\ Grad(f)<k\}$

Eigenschaften

Durch die Definition ergeben sich sofort folgende Eigenschaften:

• Codewortlänge: n
• Dimension des Codes: $|C|=|f|=q^{k}$
• Coderate: $R_{c}=k/n$

Die Mindestdistanz beträgt $d_{min}=n-k+1$ und erfüllt damit die Singleton-Schranke. Codes mit dieser Eigenschaft werden auch MDS-Codes genannt.

Erklärung

Da f maximal k-1 Nullstellen besitzen kann(durch den Grad des Polynoms beschränkt) tauchen im korrespondierenden Codewort maximal k-1 Stellen auf die zu 0 werden. Damit ist das Hamming-Gewicht w(C)>=n-k+1 und somit wegen der Linearität auch die Minimaldistanz.

Zusammen mit der Singleton-Schranke d_min<=n-k+1 ergibt sich die Gleichheit.

Zur Einordnung in der Kodierungstheorie

Reed-Solomon-Codes sind zyklische Codes der Länge $q-1$ über einem $q$-nären Zeichenvorrat, sie bilden also eine Unterklasse der BCH-Codes. Außerdem sind sie MDS-Codes und damit optimale Codes.

Literatur

• Reed, I. und G. Solomon, Polynomial codes over certain finite fields, Journal of the Society for Industrial and Applied Mathematics [SIAM J.], 8 (1960) 300-304. Die Originalarbeit

Weblinks

• Codier- und Decodieralgorithmen für Reed-Solomon-Codes in C