Reed-Solomon-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 sogenannter "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 $\backslash alpha\backslash isin\; GF(p)$ ein primitives Element aus dem Galoisfeld über p, der Ordnung n und $f(x)\backslash isin\; GF(p)*$ ein Polynom vom Grad(f_0,..,f_{k-1}) bilden.

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

Der RS-Code zu $\backslash alpha\backslash isin\; GF(p)$ und n kann also dargestellt werden als

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 J., 8 (1960) 300-304. Die Originalarbeit

Weblinks

---

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

Nachrichtentechnik | Diskrete Mathematik | Kodierungstheorie

Reed-Solomon error correction | Reed-Solomon | Code de Reed-Solomon | Reed-Solomoncode