www.wikidata.de-de.nina.az

Reed Solomon Code s kurz RS Codes sind eine Klasse zyklischer Blockcodes Sie werden im Rahmen der Kanalkodierung zum Erk

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) 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 Bearbeiten

Jede Nachricht, zum Beispiel ein Textfragment, kann als Folge aus 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 fest vereinbarten Stützstellen interpretiert. Ein Polynom des Grades oder kleiner kann als Summe von 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 Zahlen besteht.

Werden bei der Übertragung nun einige wenige Zahlen ausgelöscht, sodass immer noch mehr als 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 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 ) korrigiert werden wie Verfälschungen , 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 Bearbeiten

Sei ein endlicher Körper mit Elementen ( ist dann notwendigerweise eine Primzahlpotenz, prim). Es werden nun paarweise verschiedene Elemente ausgewählt und fixiert.

Die Menge der Kodewörter eines Reed-Solomon-Codes der Länge für Nachrichten der Länge über ergibt sich nun durch die Wertetupel aller Polynome aus mit Grad kleiner an den gewählten Stützstellen:

wobei mit .

Stützstellenmengen Bearbeiten

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 -ten Grades umgewandelt, so dass der zweite Schritt wieder ein Kodewort ergibt.

Ist ein Element der Ordnung oder größer, so kann zum Beispiel

gewählt werden. Jeder endliche Körper enthält ein erzeugendes oder primitives Element der multiplikativen Gruppe , das heißt ein Element der Ordnung . Daher ist diese spezielle Wahl für immer möglich.

Sind die Stützstellen genau die Potenzen eines Elementes der Ordnung , , so ist der RS-Kode ein zyklischer Code. Denn das Kodewort zum Polynom ergibt sich durch Rotation des Kodewortes zu um Stellen nach links. Wegen der einfacheren Implementierbarkeit zyklischer Codes wird diese Variante im Allgemeinen bevorzugt.

Kodieren von Nachrichten Bearbeiten

Man kann eine Nachricht mit Symbolen direkt in ein Kodewort verwandeln, indem man die Komponenten als Koeffizienten eines Polynoms

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

der Länge .

Für die Anzahl der Symbole der Nachricht und die geforderte Minimaldistanz gilt . Weil ein beliebiges Polynom vom Grad kleiner oder gleich maximal Nullstellen haben kann, ist gewährleistet, dass jedes gültige Kodewort mindestens Symbole enthält, die ungleich 0 sind. Daher hat der gebildete Code die Minimaldistanz und ist in der Lage, maximal Fehler zu korrigieren.

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

der Paare . Wegen für ergibt sich aus das Kodewort

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

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

Aus den Koeffizienten des Polynoms erhält man die Erzeugendenmatrix für den Reed-Solomon-Code:

Eigenschaften Bearbeiten

Durch die Definition ergeben sich sofort folgende Eigenschaften:

  • Codewortlänge:
  • Dimension des Codes:
  • Coderate:

Die Mindestdistanz beträgt und erfüllt damit die Singleton-Schranke. Codes mit dieser Eigenschaft werden auch MDS-Codes genannt.

Beispiel Bearbeiten

Gegeben ist die Nachricht über . Daraus erhält man das Polynom . Die Elemente von werden als Potenzen des primitiven Elements berechnet:

Exponentendarstellung Komponentendarstellung binäre Darstellung dezimale Darstellung
1
2
4
8
9
11
15
7
14
5
10
13
3
6
12

Daraus ergeben sich die Werte über für die Symbole

und das Kodewort .

Literatur Bearbeiten

  • Stephen B. Wicker, Vijay K. Bhargava: Reed Solomon Codes Applications. Wiley, 1999, ISBN 0-7803-5391-9 (ieeexplore.ieee.org).

Weblinks Bearbeiten

Einzelnachweise Bearbeiten

  1. Irving S. Reed, Gustave Solomon: Polynomial codes over certain finite fields. In: Journal of the Society for Industrial and Applied Mathematics, SIAM J. Band 8, 1960, ISSN 0036-1399, S. 300–304.
  2. ↑ Eduard Jorswieck, Anne Wolf, Technische Universität Dresden: Reed-Solomon-Coder und -Decoder
  3. Benjamin Klopsch: Audio CDs und Reed-Solomon Codes
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Reed Solomon Codes kurz RS Codes sind eine Klasse zyklischer Blockcodes Sie werden im Rahmen der Kanalkodierung zum Erkennen und Korrigieren von Ubertragungs oder Speicherfehlern als Teil einer Vorwartsfehlerkorrektur 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 1 Zu dieser Zeit war die praktische Verwendbarkeit dieser Codes allerdings eingeschrankt da keine effiziente Methode zur Decodierung bekannt war Einen effizienten Decodieralgorithmus stellten 1969 Elwyn Berlekamp und James Massey in Form des auch fur 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 uber einen grossen Bereich wie den DVB Standard zur Aussendung digitaler Fernsehsignale verschiedene Mobilfunkstandards Digital Audio Broadcasting DAB 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 leistungsfahigere Codes wie die Low Density Parity Check Codes LDPC oder Turbo Codes TPC abgelost Dies ist beispielsweise im Fernsehstandard DVB S2 der Fall der LDPC zur Vorwartsfehlerkorrektur einsetzt Inhaltsverzeichnis 1 Motivation 2 Definition 2 1 Stutzstellenmengen 2 2 Kodieren von Nachrichten 3 Eigenschaften 4 Beispiel 5 Literatur 6 Weblinks 7 EinzelnachweiseMotivation BearbeitenJede Nachricht zum Beispiel ein Textfragment kann als Folge aus k displaystyle k nbsp Zahlen kodiert und ubertragen werden Ein typisches Beispiel fur die Kodierung von Texten ist der ASCII Standard Wird eine kodierte Nachricht von einem Sender zu einem Empfanger ubertragen besteht die Gefahr dass es zu Ubertragungsfehlern kommt Das bedeutet dass einige Zahlen der Nachricht ausgeloscht oder verfalscht werden Der Empfanger der Nachricht hat keine Moglichkeit den Ubertragungsfehler zu bemerken da man einer Zahl per se nicht ansehen kann ob sie richtig oder falsch ist Einem Ubertragungsfehler kann aber auf Sender Seite entgegengewirkt werden indem zusatzlich zur Nachricht redundante Informationen ubertragen werden Der Empfanger kann dann durch den Vergleich der erhaltenen Nachricht mit den redundant ubertragenen Informationen nicht nur die Integritat der ubertragenen Nachricht verifizieren sondern zusatzlich erkannte Fehler in der Nachricht korrigieren Um Redundanz zur Nachricht hinzuzufugen werden die Zahlen der Nachricht als Werte eines Polynoms an k displaystyle k nbsp fest vereinbarten Stutzstellen interpretiert Ein Polynom des Grades k 1 displaystyle k 1 nbsp oder kleiner kann als Summe von k displaystyle k nbsp Monomen dargestellt werden Die Koeffizienten dieser Monome ergeben sich als Losung eines linearen Gleichungssystems Aufgrund der speziellen Form dieses Systems gibt es eine Losungsformel die Lagrange Interpolation Das so erhaltene Polynom wird auf weitere Stutzstellen extrapoliert sodass die kodierte Nachricht insgesamt aus n gt k displaystyle n gt k nbsp Zahlen besteht Werden bei der Ubertragung nun einige wenige Zahlen ausgeloscht sodass immer noch mehr als k displaystyle k nbsp der Zahlen erhalten bleiben kann das Polynom wiederum durch Interpolation aus den korrekt ubertragenen Zahlen rekonstruiert werden und damit auch die ursprungliche Nachricht durch Auswerten in den ersten k displaystyle k nbsp Stutzstellen Bei einer fehlerbehafteten Ubertragung mit Fehlern an nur wenigen Stellen kann mit einem etwas komplizierteren Ansatz immer noch die ursprungliche Nachricht sicher rekonstruiert werden Je mehr Redundanz gewahlt wurde desto mehr Fehler konnen korrigiert werden Es konnen doppelt so viele Ausloschungen namlich n k displaystyle n k nbsp korrigiert werden wie Verfalschungen n k 2 displaystyle n k 2 nbsp daher fuhren Lesesysteme die Ausloschungen beim Empfang der Nachricht erkennen und mit den Nutzdaten ausgeben in der Regel zu einer verbesserten Korrekturfahigkeit Die in der Interpolation auftretenden Ausdrucke enthalten Divisionen mussen also uber einem Korper durchgefuhrt werden Werden die Zahlen oder Symbole der Nachricht aus den ganzen Zahlen gewahlt so finden die Rechnungen also in den rationalen Zahlen statt Ausserdem konnen die extrapolierten Werte sehr gross werden was eventuell im vorliegenden Ubertragungskanal nicht ubermittelt werden kann Um diese Nachteile zu beheben fuhrt man die Rechnungen in einem endlichen Korper durch Dieser hat eine endliche Anzahl von Elementen die durchnummeriert werden konnen um sie mit den Symbolen der Nachricht zu verknupfen Die Division ausser durch Null ist uneingeschrankt durchfuhrbar und somit auch die Interpolation Reed Solomon Codes sind zur Korrektur von Burstfehlern bei der Datenubertragung geeignet Bei Burstfehlern erscheinen fehlerhafte gekippte Bits haufig als eine zusammenhangende 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 verschrankt damit die Korrekturfahigkeit auch bei Burstfehlern moglichst hoch bleibt Definition BearbeitenSei F p displaystyle mathbb F p nbsp ein endlicher Korper mit p displaystyle p nbsp Elementen p q m displaystyle p q m nbsp ist dann notwendigerweise eine Primzahlpotenz q displaystyle q nbsp prim Es werden nun n displaystyle n nbsp paarweise verschiedene Elemente u 1 u n F p displaystyle u 1 dots u n in mathbb F p nbsp ausgewahlt und fixiert Die Menge der Kodeworter eines Reed Solomon Codes RS p k n displaystyle text RS p k n nbsp der Lange n displaystyle n nbsp fur Nachrichten der Lange k displaystyle k nbsp uber F p displaystyle mathbb F p nbsp ergibt sich nun durch die Wertetupel aller Polynome aus F p x displaystyle mathbb F p x nbsp mit Grad kleiner k displaystyle k nbsp an den gewahlten Stutzstellen C a a 1 a n F p n a j f u j j 1 n displaystyle C left a a 1 dots a n in mathbb F p n Big a j f u j j 1 dots n right nbsp wobei f F p x displaystyle f in mathbb F p x nbsp mit deg f lt k displaystyle deg f lt k nbsp Stutzstellenmengen Bearbeiten RS Codes zu verschiedenen zulassigen Stutzstellenmengen sind linear isomorph Die bijektive lineare Abbildung die die Isomorphie vermittelt ergibt sich durch Lagrange Interpolation bezuglich der ersten Stutzstellenmenge und Auswertung in der zweiten Stutzstellenmenge Dabei werden im ersten Schritt Kodeworter in Polynome kleiner k displaystyle k nbsp ten Grades umgewandelt so dass der zweite Schritt wieder ein Kodewort ergibt Ist a F p displaystyle alpha in mathbb F p nbsp ein Element der Ordnung n displaystyle n nbsp oder grosser so kann zum Beispiel u 1 1 u 2 a u j a j 1 u n a n 1 displaystyle u 1 1 u 2 alpha dots u j alpha j 1 dots u n alpha n 1 nbsp gewahlt werden Jeder endliche Korper enthalt ein erzeugendes oder primitives Element der multiplikativen Gruppe F p F p 0 displaystyle mathbb F p mathbb F p setminus 0 nbsp das heisst ein Element der Ordnung p 1 displaystyle p 1 nbsp Daher ist diese spezielle Wahl fur n p 1 displaystyle n p 1 nbsp immer moglich Sind die Stutzstellen genau die Potenzen u 1 1 u j a j 1 1 j 2 n displaystyle u 1 1 u j alpha j 1 neq 1 j 2 dots n nbsp eines Elementes a F p displaystyle alpha in mathbb F p nbsp der Ordnung n displaystyle n nbsp a n 1 displaystyle alpha n 1 nbsp so ist der RS Kode ein zyklischer Code Denn das Kodewort zum Polynom f j x f a j x displaystyle f j x f alpha j x nbsp ergibt sich durch Rotation des Kodewortes zu f x displaystyle f x nbsp um j displaystyle j nbsp Stellen nach links Wegen der einfacheren Implementierbarkeit zyklischer Codes wird diese Variante im Allgemeinen bevorzugt Kodieren von Nachrichten Bearbeiten Man kann eine Nachricht a 1 a 2 a k F p k displaystyle a 1 a 2 dots a k in mathbb F p k nbsp mit k displaystyle k nbsp 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 a k x k 1 i 1 k a i x i 1 F p x displaystyle 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 nbsp einsetzt und dieses an den Stutzstellen u 1 u 2 u n 0 1 p 1 displaystyle u 1 u 2 dots u n in 0 1 p 1 nbsp auswertet Es ergibt sich damit ein Kodewort c c 1 c 2 c n f u 1 f u 2 f u n F p n displaystyle 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 nbsp der Lange n displaystyle n nbsp Fur die Anzahl k displaystyle k nbsp der Symbole der Nachricht und die geforderte Minimaldistanz d displaystyle d nbsp gilt k n d 1 displaystyle k leq n d 1 nbsp Weil ein beliebiges Polynom f x displaystyle f x nbsp vom Grad kleiner oder gleich k displaystyle k nbsp maximal k displaystyle k nbsp Nullstellen haben kann ist gewahrleistet dass jedes gultige Kodewort mindestens d displaystyle d nbsp Symbole enthalt die ungleich 0 sind Daher hat der gebildete Code die Minimaldistanz d displaystyle d nbsp und ist in der Lage maximal t d 1 2 displaystyle t frac d 1 2 nbsp Fehler zu korrigieren 2 Statt die Nachricht a 1 a k displaystyle a 1 dots a k nbsp als Polynomkoeffizienten zu kodieren kann man sie alternativ auch in die ersten k displaystyle k nbsp Stutzstellen des Polynoms kodieren Dadurch erhalt man eine systematische Kodierung Das zum Kodewort fuhrende Polynom f x displaystyle f x nbsp ergibt sich dabei als Lagrange Polynomf x i 1 k a i j i k x u j u i u j displaystyle f x sum i 1 k left a i cdot prod j neq i k frac x u j u i u j right nbsp der Paare u 1 a 1 u 2 a 2 u k a k displaystyle Big u 1 a 1 u 2 a 2 ldots u k a k Big nbsp Wegen f u i a i displaystyle f u i a i nbsp fur i 1 k displaystyle i 1 dots k nbsp ergibt sich aus f x displaystyle f x nbsp das Kodewort c c 1 c 2 c n a 1 a 2 a k f u k 1 f u n displaystyle 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 nbsp mit der Nachricht in den ersten k displaystyle k nbsp Stellen des Kodeworts im Klartext Beide Varianten benutzen dieselbe Menge von Kodewortern und haben damit dieselben Fehlerkorrektureigenschaften Aus den Koeffizienten des Polynoms f x a 1 a 2 x a 3 x 2 a k x k 1 displaystyle f x a 1 a 2 x a 3 x 2 dots a k x k 1 nbsp erhalt man die Erzeugendenmatrix fur den Reed Solomon Code 3 G a 1 a 2 a k 1 0 0 0 a 1 a 2 a k 1 0 0 0 a 1 a 2 a k 1 M k n F p displaystyle G begin pmatrix a 1 amp a 2 amp ldots amp a k amp 1 amp 0 amp ldots amp 0 0 amp a 1 amp a 2 amp ldots amp a k amp 1 amp ddots amp vdots vdots amp ddots amp ddots amp ddots amp ddots amp ddots amp ddots amp 0 0 amp ldots amp 0 amp a 1 amp a 2 amp ldots amp a k amp 1 end pmatrix in M k times n mathbb F p nbsp Eigenschaften BearbeitenDurch die Definition ergeben sich sofort folgende Eigenschaften Codewortlange n displaystyle n nbsp Dimension des Codes C f q k displaystyle C f q k nbsp Coderate R c k n displaystyle R c k n nbsp Die Mindestdistanz betragt d min n k 1 displaystyle d text min n k 1 nbsp und erfullt damit die Singleton Schranke Codes mit dieser Eigenschaft werden auch MDS Codes genannt ErklarungDa f displaystyle f nbsp maximal k 1 displaystyle k 1 nbsp Nullstellen besitzen kann durch den Grad des Polynoms beschrankt tauchen im korrespondierenden Codewort maximal k 1 displaystyle k 1 nbsp Stellen auf die zu 0 werden Damit ist das Hamming Gewicht w t C n k 1 displaystyle wt C geqq n k 1 nbsp und somit wegen der Linearitat auch die Minimaldistanz Zusammen mit der Singleton Schranke d min n k 1 displaystyle d text min leqq n k 1 nbsp ergibt sich die Gleichheit Beispiel BearbeitenGegeben ist die Nachricht a 1 a 2 a 3 a 4 a 5 a 6 2 6 8 12 15 13 1 displaystyle a 1 a 2 a 3 a 4 a 5 a 6 2 6 8 12 15 13 1 nbsp uber F 2 4 displaystyle mathbb F 2 4 nbsp Daraus erhalt man das Polynom f x 2 6 x 8 x 2 12 x 3 15 x 4 13 x 5 x 6 displaystyle f x 2 6 cdot x 8 cdot x 2 12 cdot x 3 15 cdot x 4 13 cdot x 5 x 6 nbsp Die Elemente von F 2 4 displaystyle mathbb F 2 4 nbsp werden als Potenzen des primitiven Elements a displaystyle alpha nbsp berechnet Exponentendarstellung Komponentendarstellung binare Darstellung dezimale Darstellunga 0 displaystyle alpha 0 nbsp a 0 displaystyle quad quad quad quad quad quad alpha 0 nbsp 0001 2 displaystyle 0001 2 nbsp 1a 1 displaystyle alpha 1 nbsp a 1 displaystyle quad quad quad quad alpha 1 quad quad nbsp 0010 2 displaystyle 0010 2 nbsp 2a 2 displaystyle alpha 2 nbsp a 2 displaystyle quad quad alpha 2 quad quad quad quad nbsp 0100 2 displaystyle 0100 2 nbsp 4a 3 displaystyle alpha 3 nbsp a 3 displaystyle alpha 3 quad quad quad quad quad quad nbsp 1000 2 displaystyle 1000 2 nbsp 8a 4 displaystyle alpha 4 nbsp a 3 a 0 displaystyle alpha 3 quad quad quad quad alpha 0 nbsp 1001 2 displaystyle 1001 2 nbsp 9a 5 displaystyle alpha 5 nbsp a 3 a 1 a 0 displaystyle alpha 3 quad quad alpha 1 alpha 0 nbsp 1011 2 displaystyle 1011 2 nbsp 11a 6 displaystyle alpha 6 nbsp a 3 a 2 a 1 a 0 displaystyle alpha 3 alpha 2 alpha 1 alpha 0 nbsp 1111 2 displaystyle 1111 2 nbsp 15a 7 displaystyle alpha 7 nbsp a 2 a 1 a 0 displaystyle quad quad alpha 2 alpha 1 alpha 0 nbsp 0111 2 displaystyle 0111 2 nbsp 7a 8 displaystyle alpha 8 nbsp a 3 a 2 a 1 displaystyle alpha 3 alpha 2 alpha 1 quad quad nbsp 1110 2 displaystyle 1110 2 nbsp 14a 9 displaystyle alpha 9 nbsp a 2 a 0 displaystyle quad quad alpha 2 quad quad alpha 0 nbsp 0101 2 displaystyle 0101 2 nbsp 5a 10 displaystyle alpha 10 nbsp a 3 a 1 displaystyle alpha 3 quad quad alpha 1 quad quad nbsp 1010 2 displaystyle 1010 2 nbsp 10a 11 displaystyle alpha 11 nbsp a 3 a 2 a 0 displaystyle alpha 3 alpha 2 quad quad alpha 0 nbsp 1101 2 displaystyle 1101 2 nbsp 13a 12 displaystyle alpha 12 nbsp a 1 a 0 displaystyle quad quad quad quad alpha 1 alpha 0 nbsp 0011 2 displaystyle 0011 2 nbsp 3a 13 displaystyle alpha 13 nbsp a 2 a 1 displaystyle quad quad alpha 2 alpha 1 quad quad nbsp 0110 2 displaystyle 0110 2 nbsp 6a 14 displaystyle alpha 14 nbsp a 3 a 2 displaystyle alpha 3 alpha 2 quad quad quad quad nbsp 1100 2 displaystyle 1100 2 nbsp 12Daraus ergeben sich die Werte uber F 2 4 displaystyle mathbb F 2 4 nbsp fur die Symbolec 1 f a 0 2 a 0 6 a 0 8 a 0 12 a 0 15 a 0 13 a 0 a 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 a 1 2 a 0 6 a 1 8 a 2 12 a 3 15 a 4 13 a 5 a 6 a 1 a 0 a 13 a 1 a 3 a 2 a 14 a 3 a 6 a 4 a 11 a 5 a 0 a 6 a 1 a 14 a 5 a 2 a 10 a 1 a 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 c 15 f a 14 2 a 0 6 a 14 8 a 28 12 a 42 15 a 56 13 a 70 a 84 a 1 a 0 a 13 a 14 a 3 a 13 a 14 a 12 a 6 a 11 a 11 a 10 a 0 a 9 a 1 a 12 a 1 a 11 a 2 a 6 a 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 displaystyle begin aligned c 1 f alpha 0 amp 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 amp 2 6 8 12 15 13 1 amp 0010 2 0110 2 1000 2 1100 2 1111 2 1101 2 0001 2 amp 0011 2 3 c 2 f alpha 1 amp 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 amp 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 amp alpha 1 alpha 14 alpha 5 alpha 2 alpha 10 alpha 1 cdot alpha 6 amp 2 12 11 4 10 2 15 amp 0010 2 1100 2 1011 2 0100 2 1010 2 0010 2 1111 2 amp 0110 2 6 amp cdots c 15 f alpha 14 amp 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 amp 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 amp alpha 1 alpha 12 alpha 1 alpha 11 alpha 2 alpha 6 cdot alpha 9 amp 2 3 2 13 4 15 5 amp 0010 2 0011 2 0010 2 1101 2 0100 2 1111 2 0101 2 amp 0000 2 0 end aligned nbsp und das Kodewort c c 1 c 2 c 15 f a 0 f a 1 f a 14 3 6 15 6 6 3 13 14 3 12 15 2 11 1 0 displaystyle 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 nbsp 2 Literatur BearbeitenStephen B Wicker Vijay K Bhargava Reed Solomon Codes Applications Wiley 1999 ISBN 0 7803 5391 9 ieeexplore ieee org Weblinks BearbeitenKodier und Dekodieralgorithmen fur 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 amp Experience 27 9 September 1997 S 995 1012Einzelnachweise Bearbeiten Irving S Reed Gustave Solomon Polynomial codes over certain finite fields In Journal of the Society for Industrial and Applied Mathematics SIAM J Band 8 1960 ISSN 0036 1399 S 300 304 a b Eduard Jorswieck Anne Wolf Technische Universitat Dresden Reed Solomon Coder und Decoder Benjamin Klopsch Audio CDs und Reed Solomon Codes Abgerufen von https de wikipedia org w index php title Reed Solomon Code amp oldid 235383911