Reed-Solomon-Code

Reed-Solomon-Codes (kurz RS-Codes) sind eine Klasse zyklischer Blockcodes. Sie werden im Rahmen der Kanalkodierung zum Erkennen und Korrigieren von Übertragungs- oder Speicherfehlern als Teil einer Vorwärtsfehlerkorrektur eingesetzt. Sie bilden eine Unterklasse der allgemeinen Klasse der BCH-Codes. RS-Codes sind MDS-Codes, womit sie im Rahmen der Kodierungstheorie als optimale Codes gelten.

Reed-Solomon-Codes wurden um 1960 von Irving S. Reed und Gustave Solomon am Lincoln Laboratory, einer Forschungseinrichtung des Verteidigungsministeriums der Vereinigten Staaten entwickelt. Zu dieser Zeit war die praktische Verwendbarkeit dieser Codes allerdings eingeschränkt, da keine effiziente Methode zur Decodierung bekannt war. Einen effizienten Decodieralgorithmus stellten 1969 Elwyn Berlekamp und James Massey in Form des auch für BCH-Codes verwendbaren Berlekamp-Massey-Algorithmus vor.

Erstmals angewandt wurden Reed-Solomon-Codes im Voyager-Programm der NASA im Jahr 1977. Erste kommerzielle Anwendung fanden sie 1982 bei der Fehlerkorrektur von Compact Disks. Heutige Anwendungen erstrecken sich über einen großen Bereich wie den DVB-Standard zur Aussendung digitaler Fernsehsignale, verschiedene Mobilfunkstandards, Digital Audio Broadcasting (DAB), RAID-6-Systeme und Dateiformate wie PAR2 zur Datenspeicherung. Weitere Anwendungsbeispiele sind zweidimensionale Barcodes; so setzen z. B. der QR-Code, DataMatrix, Aztec-Code und der PDF417 Reed-Solomon zur Fehlerkorrektur von Lesefehlern ein. In neueren Anwendungsbereichen werden RS-Codes zunehmend durch leistungsfähigere Codes wie die Low-Density-Parity-Check-Codes (LDPC) oder Turbo-Codes (TPC) abgelöst. Dies ist beispielsweise im Fernsehstandard DVB-S2 der Fall, der LDPC zur Vorwärtsfehlerkorrektur einsetzt.

Motivation

Jede Nachricht, zum Beispiel ein Textfragment, kann als Folge aus $k$ Zahlen kodiert und übertragen werden. Ein typisches Beispiel für die Kodierung von Texten ist der ASCII-Standard. Wird eine kodierte Nachricht von einem Sender zu einem Empfänger übertragen, besteht die Gefahr, dass es zu Übertragungsfehlern kommt. Das bedeutet, dass einige Zahlen der Nachricht ausgelöscht oder verfälscht werden. Der Empfänger der Nachricht hat keine Möglichkeit, den Übertragungsfehler zu bemerken, da man einer Zahl per se nicht ansehen kann, ob sie richtig oder falsch ist. Einem Übertragungsfehler kann aber auf Sender-Seite entgegengewirkt werden, indem zusätzlich zur Nachricht redundante Informationen übertragen werden. Der Empfänger kann dann durch den Vergleich der erhaltenen Nachricht mit den redundant übertragenen Informationen nicht nur die Integrität der übertragenen Nachricht verifizieren, sondern zusätzlich erkannte Fehler in der Nachricht korrigieren.

Um 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 auf weitere Stützstellen extrapoliert, sodass die kodierte Nachricht insgesamt aus $n>k$ Zahlen besteht.

Werden bei der Übertragung nun einige wenige Zahlen ausgelöscht, sodass immer noch mehr als $k$ der Zahlen erhalten bleiben, 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. Bei einer fehlerbehafteten Übertragung mit Fehlern an nur wenigen Stellen kann mit einem etwas komplizierteren Ansatz immer noch die ursprüngliche Nachricht sicher rekonstruiert werden. Je mehr Redundanz gewählt wurde, desto mehr Fehler können korrigiert werden. Es können doppelt so viele Auslöschungen (nämlich $n-k$) korrigiert werden wie Verfälschungen $(n-k)/2$, daher führen Lesesysteme, die Auslöschungen beim Empfang der Nachricht erkennen und mit den Nutzdaten ausgeben, in der Regel zu einer verbesserten Korrekturfähigkeit.

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.

Reed-Solomon-Codes sind 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. Bei der CD werden die Daten allerdings noch verschränkt, damit die Korrekturfähigkeit auch bei Burstfehlern möglichst hoch bleibt.

Definition

Sei ${𝔽}_p$ ein endlicher Körper mit $p$ Elementen ($p=q^m$ ist dann notwendigerweise eine Primzahlpotenz, $q$ prim). Es werden nun $n$ paarweise verschiedene Elemente $u_1,\dots ,u_n\in {𝔽}_p$ ausgewählt und fixiert.

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

$C=\{a=(a_1,\dots ,a_n)\in {𝔽}_p{}^n|a_j=f(u_j),j=1,\dots ,n\}$

wobei $f\in {𝔽}_p[x]$ mit $\mathrm{deg}(f)<k$.

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 {𝔽}_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 ${𝔽}_p{}^{*}={𝔽}_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 {𝔽}_p$ der Ordnung $n$, ${\alpha }^n=1$, so ist der RS-Kode ein zyklischer Code. Denn das Kodewort zum Polynom $f_j(x)=f({\alpha }^{j}x)$ ergibt sich durch Rotation des Kodewortes zu $f(x)$ um $j$ Stellen nach links. Wegen der einfacheren Implementierbarkeit zyklischer Codes wird diese Variante im Allgemeinen bevorzugt.

Kodieren von Nachrichten

Man kann eine Nachricht $(a_1,a_2,\dots ,a_k)\in {𝔽}_p{}^k$ mit $k$ Symbolen 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 {𝔽}_p[x]$

einsetzt und dieses an den Stützstellen $u_1,u_2,\dots ,u_n\in \{0,1,...,p-1\}$ auswertet. Es ergibt sich damit ein Kodewort

$c=(c_1,c_2,\dots ,c_n)=(f(u_1),f(u_2),\dots ,f(u_n))\in {𝔽}_p{}^n$

der Länge $n$.

Für die Anzahl $k$ der Symbole der Nachricht und die geforderte Minimaldistanz $d$ gilt $k\le n-d+1$. Weil ein beliebiges Polynom $f(x)$ vom Grad kleiner oder gleich $k$ maximal $k$ Nullstellen haben kann, ist gewährleistet, dass jedes gültige Kodewort mindestens $d$ Symbole enthält, die ungleich 0 sind. Daher hat der gebildete Code die Minimaldistanz $d$ und ist in der Lage, maximal $t=\frac{d-1}{2}$ Fehler zu korrigieren.

Statt die Nachricht $(a_1,\dots ,a_k)$ als Polynomkoeffizienten zu kodieren, kann man sie alternativ auch in die ersten $k$ Stützstellen des Polynoms kodieren. Dadurch erhält man eine systematische Kodierung. Das zum Kodewort führende Polynom $f(x)$ ergibt sich dabei als Lagrange-Polynom

$f(x)=\sum _{i=1}^k(a_i\cdot \prod _{j\ne i}^k\frac{x-u_j}{u_i-u_j})$

der Paare $((u_1,a_1),(u_2,a_2),\dots ,(u_k,a_k))$. Wegen $f(u_i)=a_i$ für $i=1,\dots ,k$ ergibt sich aus $f(x)$ das Kodewort

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

mit der Nachricht in den ersten $k$ Stellen des Kodeworts im „Klartext“.

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

Aus den Koeffizienten des Polynoms $f(x)=a_1+a_{2}x+a_3{x}^2+\dots +a_k{x}^{k-1}$ erhält man die Erzeugendenmatrix für den Reed-Solomon-Code:

$G=\left(\begin{array}{cccccccc}{a}_1& a_2& \dots & a_k& 1& 0& \dots & 0\\ 0& a_1& a_2& \dots & a_k& 1& \ddots & ⋮\\ ⋮& \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & 0\\ 0& \dots & 0& a_1& a_2& \dots & a_k& 1\end{array}\right)\in M(k\times n,{𝔽}_p)$

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_{\text{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 $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.

Beispiel

Gegeben ist die Nachricht $(a_1,a_2,a_3,a_4,a_5,a_6)=(2,6,8,12,15,13,1)$ über ${𝔽}_{2^4}$. Daraus erhält man das Polynom $f(x)=2+6\cdot x+8\cdot x^2+12\cdot x^3+15\cdot x^4+13\cdot x^5+x^6$. Die Elemente von ${𝔽}_{2^4}$werden als Potenzen des primitiven Elements $\alpha$ berechnet:

Exponentendarstellung	Komponentendarstellung	binäre Darstellung	dezimale Darstellung
${\alpha }^0$	${\alpha }^0$	$[0001{]}_2$	1
${\alpha }^1$	${\alpha }^1$	$[0010{]}_2$	2
${\alpha }^2$	${\alpha }^2$	$[0100{]}_2$	4
${\alpha }^3$	${\alpha }^3$	$[1000{]}_2$	8
${\alpha }^4$	${\alpha }^3+{\alpha }^0$	$[1001{]}_2$	9
${\alpha }^5$	${\alpha }^3+{\alpha }^1+{\alpha }^0$	$[1011{]}_2$	11
${\alpha }^6$	${\alpha }^3+{\alpha }^2+{\alpha }^1+{\alpha }^0$	$[1111{]}_2$	15
${\alpha }^7$	${\alpha }^2+{\alpha }^1+{\alpha }^0$	$[0111{]}_2$	7
${\alpha }^8$	${\alpha }^3+{\alpha }^2+{\alpha }^1$	$[1110{]}_2$	14
${\alpha }^9$	${\alpha }^2+{\alpha }^0$	$[0101{]}_2$	5
${\alpha }^{10}$	${\alpha }^3+{\alpha }^1$	$[1010{]}_2$	10
${\alpha }^{11}$	${\alpha }^3+{\alpha }^2+{\alpha }^0$	$[1101{]}_2$	13
${\alpha }^{12}$	${\alpha }^1+{\alpha }^0$	$[0011{]}_2$	3
${\alpha }^{13}$	${\alpha }^2+{\alpha }^1$	$[0110{]}_2$	6
${\alpha }^{14}$	${\alpha }^3+{\alpha }^2$	$[1100{]}_2$	12

Daraus ergeben sich die Werte über ${𝔽}_{2^4}$ für die Symbole

$\begin{array}{cc}{c}_1=f({\alpha }^0)& =2\cdot {\alpha }^0+6\cdot {\alpha }^0+8\cdot {\alpha }^0+12\cdot {\alpha }^0+15\cdot {\alpha }^0+13\cdot {\alpha }^0+{\alpha }^0\\ & =2+6+8+12+15+13+1\\ & =[0010{]}_2+[0110{]}_2+[1000{]}_2+[1100{]}_2+[1111{]}_2+[1101{]}_2+[0001{]}_2\\ & =[0011{]}_2=3\\ c_2=f({\alpha }^1)& =2\cdot {\alpha }^0+6\cdot {\alpha }^1+8\cdot {\alpha }^2+12\cdot {\alpha }^3+15\cdot {\alpha }^4+13\cdot {\alpha }^5+{\alpha }^6\\ & ={\alpha }^1\cdot {\alpha }^0+{\alpha }^{13}\cdot {\alpha }^1+{\alpha }^3\cdot {\alpha }^2+{\alpha }^{14}\cdot {\alpha }^3+{\alpha }^6\cdot {\alpha }^4+{\alpha }^{11}\cdot {\alpha }^5+{\alpha }^0\cdot {\alpha }^6\\ & ={\alpha }^1+{\alpha }^{14}+{\alpha }^5+{\alpha }^2+{\alpha }^{10}+{\alpha }^1\cdot {\alpha }^6\\ & =2+12+11+4+10+2+15\\ & =[0010{]}_2+[1100{]}_2+[1011{]}_2+[0100{]}_2+[1010{]}_2+[0010{]}_2+[1111{]}_2\\ & =[0110{]}_2=6\\ & \cdots \\ c_{15}=f({\alpha }^{14})& =2\cdot {\alpha }^0+6\cdot {\alpha }^{14}+8\cdot {\alpha }^{28}+12\cdot {\alpha }^{42}+15\cdot {\alpha }^{56}+13\cdot {\alpha }^{70}+{\alpha }^{84}\\ & ={\alpha }^1\cdot {\alpha }^0+{\alpha }^{13}\cdot {\alpha }^{14}+{\alpha }^3\cdot {\alpha }^{13}+{\alpha }^{14}\cdot {\alpha }^{12}+{\alpha }^6\cdot {\alpha }^{11}+{\alpha }^{11}\cdot {\alpha }^{10}+{\alpha }^0\cdot {\alpha }^9\\ & ={\alpha }^1+{\alpha }^{12}+{\alpha }^1+{\alpha }^{11}+{\alpha }^2+{\alpha }^6\cdot {\alpha }^9\\ & =2+3+2+13+4+15+5\\ & =[0010{]}_2+[0011{]}_2+[0010{]}_2+[1101{]}_2+[0100{]}_2+[1111{]}_2+[0101{]}_2\\ & =[0000{]}_2=0\end{array}$

und das Kodewort $c=(c_1,c_2,\dots ,c_{15})=(f({\alpha }^0),f({\alpha }^1),\dots ,f({\alpha }^{14}))=(3,6,15,6,6,3,13,14,3,12,15,2,11,1,0)$.

Literatur

• Vorlage:Literatur

Weblinks

• Kodier- und Dekodieralgorithmen für Reed-Solomon- und andere Kodes in C (Robert Morelos-Zaragoza) (en)
• James S. Plank: A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems, Software – Practice & Experience, 27(9), September, 1997, S. 995–1012