Reed-Solomon-Code


Reed-Solomon-Code

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 sechs Zehnerpotenzen zu verbessern. Reed-Solomon-Codes sind besonders zur Korrektur von Burstfehlern bei der Datenübertragung geeignet. Bei Burstfehlern erscheinen fehlerhafte („gekippte“) Bits häufig als eine zusammenhängende Kette von Fehlern im Datenstrom. Beispielsweise werden durch einen Kratzer auf einer CD mit jeder Umdrehung viele aufeinanderfolgende Bits nicht richtig gelesen.

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, der Berlekamp-Massey-Algorithmus, 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. Auch im Checksummenformat PAR2 wird der Code benutzt.

Inhaltsverzeichnis

Motivation

Es soll eine Nachricht aus k Zahlen (zum Beispiel ein Textfragment in ASCII-Kodierung) fehlerfrei übertragen werden. Auf dem Übertragungsweg kann es aber zur Auslöschung oder Verfälschung einiger der Zahlen kommen (im ersten Fall weiß man, dass ein Fehler auftrat, im zweiten nicht). Um nun Redundanz zur Nachricht hinzuzufügen, werden die Zahlen der Nachricht als Werte eines Polynoms an k fest vereinbarten Stützstellen interpretiert. Ein Polynom des Grades k − 1 oder kleiner kann als Summe von k Monomen dargestellt werden. Die Koeffizienten dieser Monome ergeben sich als Lösung eines linearen Gleichungssystems. Aufgrund der speziellen Form dieses Systems gibt es eine Lösungsformel, die Lagrange-Interpolation. Das so erhaltene Polynom wird nun auf weitere Stützstellen extrapoliert, so dass die kodierte Nachricht insgesamt aus n > k Zahlen besteht.

Werden bei der Übertragung nun einige wenige Zahlen ausgelöscht, so dass immer noch mehr als k der Zahlen erhalten bleiben, so kann das Polynom wiederum durch Interpolation aus den korrekt übertragenen Zahlen rekonstruiert werden, und damit auch die ursprüngliche Nachricht durch Auswerten in den ersten k Stützstellen. Im Falle einer fehlerbehafteten Übertragung mit Fehlern an nur wenigen Stellen kann mit einem etwas komplizierteren Ansatz immer noch die ursprüngliche Nachricht sicher rekonstruiert werden.

Die in der Interpolation auftretenden Ausdrücke enthalten Divisionen, müssen also über einem Körper durchgeführt werden. Werden die Zahlen – oder Symbole – der Nachricht aus den ganzen Zahlen gewählt, so finden die Rechnungen also in den rationalen Zahlen statt. Außerdem können die extrapolierten Werte sehr groß werden, was eventuell im vorliegenden Übertragungskanal nicht übermittelt werden kann. Um diese Nachteile zu beheben, führt man die Rechnungen in einem endlichen Körper durch. Dieser hat eine endliche Anzahl von Elementen, die durchnummeriert werden können, um sie mit den Symbolen der Nachricht zu verknüpfen. Die Division – außer durch Null – ist uneingeschränkt durchführbar, und somit auch die Interpolation.

Definition

Sei \mathbb F_p ein endlicher Körper mit p Elementen (p = qm ist dann notwendigerweise eine Primzahlpotenz, q prim). Es werden nun n paarweise verschiedene Elemente u_1,\dots,u_n\in\mathbb F_p ausgewählt und fixiert.

Die Menge der Kodewörter eines Reed-Solomon-Kodes RS(p,k,n) der Länge n für Nachrichten der Länge k über \mathbb F_p ergibt sich nun durch die Wertetupel aller Polynome aus \mathbb F_p[x] mit Grad kleiner k an den gewählten Stützstellen:

C=\left\{
  a=(a_1,\dots,a_n)\in\mathbb F_p{}^n
  \;\Big|\;
  a_j=f(u_j),\;j=1,\dots,n;\ 
  \mathsf{wobei}\  f\in\mathbb F_p[x]\ \mathsf{mit}\ \deg(f)<k
\right\}

Stützstellenmengen

RS-Codes zu verschiedenen zulässigen Stützstellenmengen sind linear isomorph. Die bijektive lineare Abbildung, die die Isomorphie vermittelt, ergibt sich durch Lagrange-Interpolation bezüglich der ersten Stützstellenmenge und Auswertung in der zweiten Stützstellenmenge. Dabei werden im ersten Schritt Kodewörter in Polynome kleiner k-ten Grades umgewandelt, so dass der zweite Schritt wieder ein Kodewort ergibt.

Ist \alpha\in \mathbb F_p ein Element der Ordnung n oder größer, so kann zum Beispiel

u_1=1,\,u_2=\alpha,\,\dots,u_j=\alpha^{j-1},\dots,u_n=\alpha^{n-1}

gewählt werden. Jeder endliche Körper enthält ein erzeugendes oder primitives Element der multiplikativen Gruppe \mathbb F_p{}^*=\mathbb F_p\setminus\{0\}, das heißt ein Element der Ordnung p − 1. Daher ist diese spezielle Wahl für n = p − 1 immer möglich.

Sind die Stützstellen genau die Potenzen u_1=1,\;u_j=\alpha^{j-1}\ne 1,\;j=2,\dots,n, eines Elementes \alpha\in\mathbb F_p der Ordnung n, αn = 1, so ist der RS-Kode ein zyklischer Kode. Denn das Kodewort zum Polynom fj(x) = fjx) ergibt sich durch Rotation des Kodewortes zu f(x) um j Stellen nach links. Wegen der einfacheren Implementierbarkeit zyklischer Kodes wird diese Variante im Allgemeinen bevorzugt.

Kodieren von Nachrichten

Man kann eine Nachricht (a_1,a_2,\dots,a_k)\in\mathbb F_p{}^k direkt in ein Kodewort verwandeln, indem man die Komponenten als Koeffizienten eines Polynoms

f(x)=a_1 + a_2\,x + a_3\,x^2 + \dots + a_k\,x^{k-1} = \sum_{i=1}^k a_i\,x^{i-1} \in\mathbb F_p[x]

einsetzt und dieses an den Stützstellen auswertet. Es ergibt sich damit ein Kodewort

c=(c_1,c_2,\dots,c_n)=\Big(f(u_1),f(u_2),\dots,f(u_n)\Big)\in\mathbb F_p{}^n

der Länge n.

Man erhält eine systematische Kodierung, in der die Nachricht in den ersten k Komponenten im „Klartext“ enthalten ist, durch eine vorbereitende Transformation der Nachricht. Das zum Kodewort führende Polynom f(x) ergibt sich hier als Interpolationspolynom der Paare

\Big((u_1,a_1),\,(u_2,a_2),\,\ldots,\,(u_k,a_k)\Big),

nach der Formel der Lagrange-Interpolation also

f(x)=\sum_{j=1}^k \left( a_j \cdot \prod_{i\ne j}\frac{x-u_i}{u_j-u_i} \right) .

Wegen f(uj) = aj für j=1,\dots,k ergibt sich aus f(x) das Kodewort

c=(c_1,c_2,\dots,c_n)=\Big(a_1,a_2,\ldots,a_k,f(u_{k+1}),\dots,f(u_n)\Big).

Beide Varianten benutzen dieselbe Menge von Kodewörtern und haben damit dieselben Fehlerkorrektureigenschaften.

Eigenschaften

Durch die Definition ergeben sich sofort folgende Eigenschaften:

  • Codewortlänge: n
  • Dimension des Codes: | C | = | f | = qk
  • Coderate: Rc = k / n

Die Mindestdistanz beträgt dmin = nk + 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 wt(C) \geqq n-k+1 und somit wegen der Linearität auch die Minimaldistanz.
Zusammen mit der Singleton-Schranke d_\text{min} \leqq 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

  • Irving S. Reed, Gustave Solomon: Polynomial codes over certain finite fields. In: Journal of the Society for Industrial and Applied Mathematics. [SIAM J.], 8, 1960, ISSN 0036-1399, S. 300–304, Die Originalarbeit.

Weblinks


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Reed-Solomon Code — 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… …   Deutsch Wikipedia

  • Cross-Interleave Reed-Solomon code — Der Cross Interleaved Reed Solomon Code (CIRC) ist ein Fehlerkorrekturcode, der bei aktuellen Speichermedien wie CD ROM und DVD eingesetzt wird. Digitale Speichermedien haben eine immer höhere Datendichte und werden so immer anfälliger für Fehler …   Deutsch Wikipedia

  • Cross Interleave Reed-Solomon-Code — Der Cross Interleaved Reed Solomon Code (CIRC) ist ein Fehlerkorrekturcode, der bei aktuellen Speichermedien wie CD ROM und DVD eingesetzt wird. Digitale Speichermedien haben eine immer höhere Datendichte und werden so immer anfälliger für Fehler …   Deutsch Wikipedia

  • Cross-Interleaved Reed Solomon Code —   [dt. »kreuzversetzter Reed Solomon Code«], CIRC …   Universal-Lexikon

  • Cross Interleaved Reed-Solomon-Code — Der Cross Interleaved Reed Solomon Code (CIRC) ist ein Fehlerkorrekturcode, der bei aktuellen Speichermedien wie CD ROM und DVD eingesetzt wird. Digitale Speichermedien haben eine immer höhere Datendichte und werden so immer anfälliger für Fehler …   Deutsch Wikipedia

  • Reed–Muller code — Reed Muller codes are a family of linear error correcting codes used in communications. They are named after their discoverers, Irving S. Reed and D. E. Muller. Muller discovered the codes, and Reed proposed the majority logic decoding for the… …   Wikipedia

  • Reed–Solomon error correction — Reed Solomon error correction is an error correcting code that works by oversampling a polynomial constructed from the data. The polynomial is evaluated at several points, and these values are sent or recorded. Sampling the polynomial more often… …   Wikipedia

  • Code De Reed-Solomon — Le code de Reed Solomon est un code correcteur basé sur les corps de Galois dont le principe est de construire un polynôme formel à partir des symboles à transmettre et de le suréchantillonner. Le résultat est alors envoyé, au lieu des symboles… …   Wikipédia en Français

  • Code de reed-solomon — Le code de Reed Solomon est un code correcteur basé sur les corps de Galois dont le principe est de construire un polynôme formel à partir des symboles à transmettre et de le suréchantillonner. Le résultat est alors envoyé, au lieu des symboles… …   Wikipédia en Français

  • 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… …   Deutsch Wikipedia