imported>HICUM: Änderungen von \cdot in +. Leicht nachvollziehbar, da vorher die Anzahl der Summanden nicht gestimmt hatte.

2026-03-18T11:52:00Z

Änderungen von \cdot in +. Leicht nachvollziehbar, da vorher die Anzahl der Summanden nicht gestimmt hatte.

Neue Seite

'''Reed-Solomon-Codes''' (kurz '''RS-Codes''') sind eine Klasse [[Zyklischer Code|zyklischer]] [[Blockcode]]s. 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-Code]]s. RS-Codes sind [[MDS-Code]]s, womit sie im Rahmen der [[Kodierungstheorie]] als [[Optimaler Code|optimale Codes]] gelten.

Reed-Solomon-Codes wurden um 1960 von [[Irving S. Reed]] und [[Gustave Solomon]] am [[Lincoln Laboratory]], einer Forschungseinrichtung des [[Verteidigungsministerium der Vereinigten Staaten|Verteidigungsministeriums der Vereinigten Staaten]] entwickelt.<ref name="irvi1" /> Zu dieser Zeit war die praktische Verwendbarkeit dieser Codes allerdings eingeschränkt, da keine [[Effizienz (Informatik)|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 Disk]]s. Heutige Anwendungen erstrecken sich über einen großen Bereich wie den [[Digital Video Broadcasting|DVB]]-Standard zur Aussendung digitaler Fernsehsignale, verschiedene [[Mobilfunk]]standards, [[Digital Audio Broadcasting|Digital Audio Broadcasting (DAB)]], [[RAID#RAID_6:_Block-Level_Striping_mit_doppelt_verteilter_Paritätsinformation|RAID-6]]-Systeme und Dateiformate wie [[PAR2]] zur Datenspeicherung. Weitere Anwendungsbeispiele sind [[2D-Code|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-Code]]s (LDPC) oder [[Turbo-Code]]s (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 <math>k</math> Zahlen kodiert und übertragen werden. Ein typisches Beispiel für die Kodierung von Texten ist der [[American Standard Code for Information Interchange|ASCII-Standard]]. Wird eine kodierte Nachricht von einem Sender zu einem Empfänger übertragen, besteht die Gefahr, dass es zu [[Bitfehler|Ü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 <math>k</math> fest vereinbarten [[Stützstelle]]n interpretiert. Ein [[Polynom]] des Grades <math>k-1</math> oder kleiner kann als Summe von <math>k</math> [[Monom]]en dargestellt werden. Die [[Koeffizient]]en dieser Monome ergeben sich als Lösung eines [[Lineares Gleichungssystem|linearen Gleichungssystems]]. Aufgrund der speziellen Form dieses Systems gibt es eine Lösungsformel, die Lagrange-[[Polynominterpolation|Interpolation]]. Das so erhaltene Polynom wird auf weitere Stützstellen [[extrapoliert]], sodass die kodierte Nachricht insgesamt aus <math>n>k</math> Zahlen besteht.

Werden bei der Übertragung nun einige wenige Zahlen ausgelöscht, sodass immer noch mehr als <math>k</math> 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 <math>k</math> 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 (Informationstheorie)|Redundanz]] gewählt wurde, desto mehr Fehler können korrigiert werden. Es können doppelt so viele Auslöschungen (nämlich <math>n-k</math>) korrigiert werden wie Verfälschungen <math>(n-k)/2</math>, 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 (Mathematik)|Interpolation]] auftretenden Ausdrücke enthalten Divisionen, müssen also über einem [[Körper (Algebra)|Körper]] durchgeführt werden. Werden die Zahlen – oder Symbole – der Nachricht aus den [[Ganze Zahl|ganzen Zahlen]] gewählt, so finden die Rechnungen also in den [[Rationale Zahl|rationalen Zahlen]] statt. Außerdem können die [[Extrapolation|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 [[Endlicher Körper|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 [[Burstfehler]]n 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 [[Cross-interleaved Reed-Solomon Code|verschränkt]], damit die Korrekturfähigkeit auch bei Burstfehlern möglichst hoch bleibt.

== Definition ==
Sei <math>\mathbb F_p</math> ein [[endlicher Körper]] mit <math>p</math> Elementen (<math>p=q^m</math> ist dann notwendigerweise eine [[Primzahl]]potenz, <math>q</math> prim). Es werden nun <math>n</math> [[paarweise verschieden]]e Elemente <math>u_1,\dots,u_n\in\mathbb F_p</math> ausgewählt und fixiert.

Die Menge der Kodewörter eines Reed-Solomon-Codes <math>\text{RS}(p,k,n)</math> der Länge <math>n</math> für Nachrichten der Länge <math>k</math> über <math>\mathbb F_p</math> ergibt sich nun durch die Wertetupel aller [[Polynom]]e aus <math>\mathbb F_p[x]</math> mit Grad kleiner <math>k</math> an den gewählten Stützstellen:
:<math>C=\left\{
a=(a_1,\dots,a_n)\in\mathbb F_p{}^n
\;\Big|\;
a_j=f(u_j),\;j=1,\dots,n
\right\}</math>
wobei <math>f \in \mathbb F_p[x]</math> mit <math>\deg(f) < k</math>.

=== Stützstellenmengen ===
RS-Codes zu verschiedenen zulässigen Stützstellenmengen sind linear isomorph. Die [[Bijektive Funktion|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 <math>k</math>-ten Grades umgewandelt, so dass der zweite Schritt wieder ein Kodewort ergibt.

Ist <math>\alpha\in \mathbb F_p</math> ein Element der Ordnung <math>n</math> oder größer, so kann zum Beispiel
:<math>u_1=1,\,u_2=\alpha,\,\dots,u_j=\alpha^{j-1},\dots,u_n=\alpha^{n-1}</math>
gewählt werden. Jeder endliche Körper enthält ein [[Erzeuger einer Gruppe|erzeugendes]] oder [[Primitivwurzel|primitives Element]] der multiplikativen Gruppe <math>\mathbb F_p{}^*=\mathbb F_p\setminus\{0\}</math>, das heißt ein Element der Ordnung <math>p-1</math>. Daher ist diese spezielle Wahl für <math>n=p-1</math> immer möglich.

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

=== Kodieren von Nachrichten ===
Man kann eine Nachricht <math>(a_1,a_2,\dots,a_k)\in\mathbb F_p{}^k</math> mit <math>k</math> Symbolen direkt in ein Kodewort verwandeln, indem man die Komponenten als Koeffizienten eines [[Polynom]]s
:<math>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]</math>
einsetzt und dieses an den Stützstellen <math>u_1,u_2,\dots,u_n \in \{0, 1, ..., p-1\}</math> auswertet. Es ergibt sich damit ein Kodewort
:<math>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</math>
der Länge <math>n</math>.

Für die Anzahl <math>k</math> der Symbole der Nachricht und die geforderte Minimaldistanz <math>d</math> gilt <math>k \leq n - d + 1</math>. Weil ein beliebiges [[Polynom]] <math>f(x)</math> vom Grad kleiner oder gleich <math>k</math> maximal <math>k</math> [[Nullstelle]]n haben kann, ist gewährleistet, dass jedes gültige Kodewort mindestens <math>d</math> Symbole enthält, die ungleich 0 sind. Daher hat der gebildete Code die Minimaldistanz <math>d</math> und ist in der Lage, maximal <math>t = \frac{d - 1}{2}</math> Fehler zu korrigieren.<ref name=":0">Eduard Jorswieck, Anne Wolf, Technische Universität Dresden: [https://tu-dresden.de/ing/elektrotechnik/ifn/itml/ressourcen/dateien/lehre/vl/codth/A2_RSC.pdf?lang=de Reed-Solomon-Coder und -Decoder]</ref>

Statt die Nachricht <math>(a_1,\dots,a_k)</math> als Polynomkoeffizienten zu kodieren, kann man sie alternativ auch in die ersten <math>k</math> Stützstellen des Polynoms kodieren. Dadurch erhält man eine ''systematische Kodierung''. Das zum Kodewort führende [[Polynom]] <math>f(x)</math> ergibt sich dabei als [[Polynominterpolation#Lagrangesche Interpolationsformel|Lagrange-Polynom]]

<math>f(x)=\sum_{i=1}^k \left( a_i \cdot \prod_{j\ne i}^k\frac{x-u_j}{u_i-u_j} \right) </math>

der Paare <math>\Big((u_1,a_1),\,(u_2,a_2),\,\ldots,\,(u_k,a_k)\Big)</math>. Wegen <math>f(u_i)=a_i</math> für <math>i=1,\dots,k</math> ergibt sich aus <math>f(x)</math> das Kodewort
:<math>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)</math>

mit der Nachricht in den ersten <math>k</math> Stellen des Kodeworts im „Klartext“.

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

Aus den Koeffizienten des [[Polynom]]s <math>f(x) = a_1 + a_2\,x + a_3\,x^2 + \dots + a_k\,x^{k - 1}</math> erhält man die Erzeugendenmatrix für den Reed-Solomon-Code:<ref>Benjamin Klopsch: [https://www.math.uni-duesseldorf.de/~klopsch/mathematics/Manuskripte/cd_rscode.pdf Audio CDs und Reed-Solomon Codes]</ref>

<math>G =
\begin{pmatrix}
a_1 & a_2 & \ldots & a_k & 1 & 0 & \ldots & 0 \\
0 & a_1 & a_2 & \ldots & a_k & 1 & \ddots & \vdots \\
\vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \ddots & 0 \\
0 & \ldots & 0 & a_1 & a_2 & \ldots & a_k & 1 \\
\end{pmatrix}
\in M(k \times n, \mathbb F_p)</math>

== Eigenschaften ==
Durch die Definition ergeben sich sofort folgende Eigenschaften:
* Codewortlänge: <math>n</math>
* [[Dimension (Mathematik)|Dimension]] des Codes: <math>|C|=|f|=q^k</math>
* Coderate: <math>R_c=k/n</math>

Die Mindestdistanz beträgt <math>d_\text{min}=n-k+1</math> und erfüllt damit die [[Singleton-Schranke]]. Codes mit dieser Eigenschaft werden auch [[MDS-Code]]s genannt.

;Erklärung:

:Da <math>f</math> maximal <math>k-1</math> [[Nullstelle]]n besitzen kann (durch den Grad des [[Polynom]]s beschränkt), tauchen im korrespondierenden Codewort maximal <math>k-1</math> Stellen auf, die zu 0 werden. Damit ist das [[Hamming-Gewicht]] <math>wt(C) \geqq n-k+1</math> und somit wegen der [[Linearität (Mathematik)|Linearität]] auch die Minimaldistanz.
:Zusammen mit der [[Singleton-Schranke]] <math>d_\text{min} \leqq n-k+1</math> ergibt sich die Gleichheit.

== Beispiel ==
Gegeben ist die Nachricht <math>(a_1, a_2, a_3, a_4, a_5, a_6) = (2, 6, 8, 12, 15, 13, 1) </math> über <math>\mathbb F_{2^4}</math>. Daraus erhält man das [[Polynom]] <math>f(x) = 2 + 6 \cdot x + 8 \cdot x^2 + 12 \cdot x^3 + 15 \cdot x^4 + 13 \cdot x^5 + x^6</math>. Die Elemente von <math>\mathbb F_{2^4} </math>werden als Potenzen des [[Primitivwurzel|primitiven Elements]] <math>\alpha </math> berechnet:
{| class="wikitable"
!Exponentendarstellung
!Komponentendarstellung
!binäre Darstellung
!dezimale Darstellung
|-
|<math>\alpha^0 </math>
|<math>\quad \quad \quad \quad \quad \quad \alpha^0 </math>
|<math>[0001]_2 </math>
|1
|-
|<math>\alpha^1 </math>
|<math>\quad \quad \quad \quad \alpha^1 \quad \quad </math>
|<math>[0010]_2 </math>
|2
|-
|<math>\alpha^2 </math>
|<math>\quad \quad \alpha^2 \quad \quad \quad \quad </math>
|<math>[0100]_2 </math>
|4
|-
|<math>\alpha^3 </math>
|<math>\alpha^3 \quad \quad \quad \quad \quad \quad </math>
|<math>[1000]_2 </math>
|8
|-
|<math>\alpha^4 </math>
|<math>\alpha^3 \quad \quad \quad \quad + \alpha^0 </math>
|<math>[1001]_2 </math>
|9
|-
|<math>\alpha^5 </math>
|<math>\alpha^3 \quad \quad + \alpha^1 + \alpha^0 </math>
|<math>[1011]_2 </math>
|11
|-
|<math>\alpha^6 </math>
|<math>\alpha^3 + \alpha^2 + \alpha^1 + \alpha^0 </math>
|<math>[1111]_2 </math>
|15
|-
|<math>\alpha^7 </math>
|<math>\quad \quad \alpha^2 + \alpha^1 + \alpha^0 </math>
|<math>[0111]_2 </math>
|7
|-
|<math>\alpha^8 </math>
|<math>\alpha^3 + \alpha^2 + \alpha^1 \quad \quad </math>
|<math>[1110]_2 </math>
|14
|-
|<math>\alpha^9 </math>
|<math>\quad \quad \alpha^2 \quad \quad + \alpha^0 </math>
|<math>[0101]_2 </math>
|5
|-
|<math>\alpha^{10} </math>
|<math>\alpha^3 \quad \quad + \alpha^1 \quad \quad </math>
|<math>[1010]_2 </math>
|10
|-
|<math>\alpha^{11} </math>
|<math>\alpha^3 + \alpha^2 \quad \quad + \alpha^0 </math>
|<math>[1101]_2 </math>
|13
|-
|<math>\alpha^{12} </math>
|<math>\quad \quad \quad \quad \alpha^1 + \alpha^0 </math>
|<math>[0011]_2 </math>
|3
|-
|<math>\alpha^{13} </math>
|<math>\quad \quad \alpha^2 + \alpha^1 \quad \quad </math>
|<math>[0110]_2 </math>
|6
|-
|<math>\alpha^{14} </math>
|<math>\alpha^3 + \alpha^2 \quad \quad \quad \quad </math>
|<math>[1100]_2 </math>
|12
|}
Daraus ergeben sich die Werte über <math>\mathbb F_{2^4} </math> für die Symbole

<math>\begin{align}
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 + \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 + \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{align} </math>

und das Kodewort <math>c = (c_1, c_2, \ldots, c_{15}) = \Big(f(\alpha^0), f(\alpha^1), \ldots, f(\alpha^{14})\Big) = (3, 6, 15, 6, 6, 3, 13, 14, 3, 12, 15, 2, 11, 1, 0)</math>.<ref name=":0" />

== Literatur ==
* {{Literatur
|Autor=Stephen B. Wicker, Vijay K. Bhargava
|Titel=Reed Solomon Codes Applications
|Verlag=Wiley
|Datum=1999
|ISBN=0-7803-5391-9
|Online=[http://ieeexplore.ieee.org/xpl/bkabstractplus.jsp?bkn=5264570 ieeexplore.ieee.org]}}

== Weblinks ==
* [http://www.eccpage.com/ Kodier- und Dekodieralgorithmen für Reed-Solomon- und andere Kodes in C (Robert Morelos-Zaragoza)] (en)
* James S. Plank: [http://www.cs.utk.edu/~plank/plank/papers/SPE-9-97.html ''A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems''], Software – Practice & Experience, 27(9), September, 1997, S. 995–1012

== Einzelnachweise ==
<references>
<ref name="irvi1">
{{Literatur
|Autor=Irving S. Reed, Gustave Solomon
|Titel=Polynomial codes over certain finite fields
|Sammelwerk=Journal of the Society for Industrial and Applied Mathematics, SIAM J.
|Band=8
|Datum=1960
|ISSN=0036-1399
|Seiten=300–304}}
</ref>
</references>

[[Kategorie:Kodierungstheorie]]

Reed-Solomon-Code - Versionsgeschichte

imported>HICUM: Änderungen von \cdot in +. Leicht nachvollziehbar, da vorher die Anzahl der Summanden nicht gestimmt hatte.