Im Codieren der Theorie sind Codes von Reed-Solomon (RS) nichtbinäre zyklische Fehlerkorrekturcodes, die von Irving S. Reed und Gustave Solomon erfunden sind. Sie haben einen systematischen Weg von Gebäudecodes beschrieben, die entdecken und vielfache zufällige Symbol-Fehler korrigieren konnten. Durch das Hinzufügen t von Kontrolle-Symbolen zu den Daten kann ein RS-Code jede Kombination bis zu t falschen Symbolen entdecken, und bis zu ⌊t/2&rfloor korrigieren; Symbole. Als ein Ausradierungscode kann es bis zu t bekannte Ausradierungen korrigieren, oder es kann entdecken und Kombinationen von Fehlern und Ausradierungen korrigieren.

Außerdem sind RS Codes als Bit-Fehler des vielfachen Platzens passend, der Codes, seit einer Folge von b + korrigiert, 1 Konsekutivbit-Fehler können höchstens zwei Symbole der Größe b betreffen.

Die Wahl von t ist bis zum Entwerfer des Codes, und kann innerhalb von breiten Grenzen ausgewählt werden.

Im Codieren des Rohres-Solomon werden Quellsymbole als Koeffizienten eines Polynoms p (x) über ein begrenztes Feld angesehen. Die ursprüngliche Idee war, N-Codesymbole von k Quellsymbolen durch die Überstichprobenerhebung p (x) an n> k verschiedene Punkte zu schaffen, die probierten Punkte und Gebrauch-Interpolationstechniken am Empfänger zu übersenden, um die ursprüngliche Nachricht wieder zu erlangen. Das ist nicht, wie RS-Codes heute verwendet werden. Statt dessen werden RS Codes als zyklische BCH-Codes angesehen, wo verschlüsselnde Symbole aus den Koeffizienten eines gebauten Polynoms durch das Multiplizieren p (x) mit einem zyklischen Generator-Polynom abgeleitet werden. Das verursacht effiziente Entzifferungsalgorithmen (beschrieben unten).

Codes des Rohres-Solomon haben wichtige Anwendungen von der Tief-Raumkommunikation bis Verbraucherelektronik seitdem gefunden. Sie werden in der Verbraucherelektronik wie CDs, DVDs, Blu-Strahl-Scheiben, in Datenübertragungstechnologien wie DSL und WiMAX, in Sendungssystemen wie DVB und ATSC, und in Computeranwendungen wie ÜBERFALL 6 Systeme prominent verwendet.

Geschichte

Codes des Rohres-Solomon wurden 1960 von Irving S. Reed und Gustave Solomon entwickelt, die dann Mitarbeiter des MIT Laboratoriums von Lincoln waren. Ihr Samenartikel wurde "Polynomische Codes über Bestimmte Begrenzte Felder betitelt." Als der Artikel geschrieben wurde, war ein effizienter Entzifferungsalgorithmus nicht bekannt. Eine Lösung für die Letzteren wurde 1969 von Elwyn Berlekamp und James Massey gefunden, und ist als der Berlekamp-Massey Entzifferung des Algorithmus seitdem bekannt. 1977 wurden RS Codes namentlich im Reisender-Programm in der Form von verketteten Codes durchgeführt. Die erste kommerzielle Anwendung in serienmäßig hergestellten Verbrauchsgütern ist 1982 mit der CD erschienen, wo zwei RS-Codes durchgeschossen hat, werden verwendet. Heute werden RS Codes in Digitalspeichergeräten und Digitalnachrichtenstandards weit durchgeführt, obwohl sie durch modernere Codes der Paritätskontrolle der niedrigen Dichte (LDPC) oder Turbocodes langsam ersetzt werden. Zum Beispiel werden RS Codes im Standard der Digitalvideorundfunkübertragung (DVB) DVB-S verwendet, aber LDPC-Codes werden in seinem Nachfolger DVB-S2 verwendet.

Beschreibung

Ursprüngliche Ansicht (Punkte übersendend)

Das ursprüngliche Konzept des Codierens des Rohres-Solomon beschreibt Verschlüsselung von k Nachrichtensymbolen durch die Betrachtung von ihnen als Koeffizienten eines Polynoms p (x) des maximalen Grads k − 1 über ein begrenztes Feld des Auftrags N und das Auswerten des Polynoms an n> k verschiedene Eingangspunkte. Die Stichprobenerhebung eines Polynoms des Grads k − 1 an mehr als K-Punkte schafft ein überentschlossenes System, und erlaubt Wiederherstellung des Polynoms am Empfänger gegeben jeder k aus n Beispielpunkten mit (Lagrange) Interpolation. Die Folge von verschiedenen Punkten wird durch einen Generator der multiplicative Gruppe des begrenzten Feldes geschaffen, und schließt 0 ein, so jeden Wert von n bis zu N erlaubend.

Mit einer mathematischen Formulierung, lassen Sie (x, x..., x), die Eingangsfolge von n verschiedenen Werten über das begrenzte Feld F zu sein; dann ist der codebook C geschaffen vom tuplets von erhaltenen Werten durch das Auswerten jedes Polynoms (über F) des Grads weniger als k an jedem x

:

wo F [x] der polynomische Ring über F ist, und k und n solch dass 1  k  n  N gewählt werden.

Wie beschrieben, oben wird eine Eingangsfolge (x, x..., x) n = N Werte als geschaffen

:

wo α eine primitive Wurzel von F ist. Wenn es 0 von der Folge, und seitdem α = 1 weglässt, hieraus folgt dass für jedes Polynom p (x) die Funktion p (αx) auch ein Polynom desselben Grads ist, und ist sein Kennwort eine zyklische nach links Verschiebung des Kennwortes ist auf p (x) zurückzuführen gewesen; so kann ein Code des Rohres-Solomon als ein zyklischer Code angesehen werden. Das wird in der klassischen Ansicht von RS-Codes verfolgt, hat nachher beschrieben.

Wie entworfen, in der Abteilung auf einem theoretischen Decoder verursacht die ursprüngliche Ansicht keinen effizienten Entzifferungsalgorithmus, wenn auch es zeigt, dass solch ein Code arbeiten kann.

Klassische Ansicht (Codiert Rohr-Solomon als BCH Codes)

In der Praxis, anstatt Musterwerte eines Polynoms zu senden, werden die Verschlüsselungssymbole als die Koeffizienten eines gebauten Produktionspolynoms durch das Multiplizieren des Nachrichtenpolynoms des maximalen Grads k &minus angesehen; 1 durch ein Generator-Polynom des Grads t = N − k − 1. Das Generator-Polynom wird definiert, indem es α, α..., α als seine Wurzeln, d. h., gehabt

wird:.

Der Sender sendet den N − 1 Koeffizienten, und der Empfänger können polynomische Abteilung durch g (x) des erhaltenen Polynoms verwenden, um zu bestimmen, ob die Nachricht irrtümlicherweise ist; ein Nichtnullrest bedeutet, dass ein Fehler entdeckt wurde. Lassen Sie r (x) das Nichtnullrest-Polynom sein, dann kann der Empfänger r (x) an den Wurzeln von g (x) bewerten, und ein Gleichungssystem bauen, das s (x) beseitigt und sich identifiziert, der Koeffizienten von r (x) irrtümlicherweise, und der Umfang des Fehlers jedes Koeffizienten sind. Wenn das Gleichungssystem gelöst werden kann, dann weiß der Empfänger, wie man seinen r (x) modifiziert, um das wahrscheinlichste zu bekommen.

Codes des Rohres-Solomon sind ein spezieller Fall einer größeren Klasse von Codes genannt BCH-Codes. Der Berlekamp-Massey Algorithmus ist für die Entzifferung solcher Codes entworfen worden, und ist so auf Codes des Rohres-Solomon anwendbar.

Um zu sehen, dass Codes des Rohres-Solomon spezielle BCH-Codes sind, ist es nützlich, die folgende alternative Definition von Codes des Rohres-Solomon zu geben.

In Anbetracht eines begrenzten Feldes der Größe, lassen Sie und lassen Sie, eine primitive th Wurzel der Einheit darin zu sein. Lassen Sie auch gegeben zu werden. Der Code des Rohres-Solomon für diese Rahmen hat Codewort, wenn, und nur wenn Wurzeln des Polynoms sind

:

Mit dieser Definition wird es sofort gesehen, dass ein Code des Rohres-Solomon ein polynomischer Code, und insbesondere ein BCH-Code ist. Das Generator-Polynom ist das minimale Polynom mit Wurzeln, wie definiert, oben, und die Codewörter sind genau die Polynome, die dadurch teilbar sind.

Gleichwertigkeit der zwei Formulierungen

Auf den ersten Blick scheinen die obengenannten zwei Definitionen von Codes des Rohres-Solomon sehr verschieden. In der ersten Definition sind Codewörter Werte von Polynomen, wohingegen im zweiten sie Koeffizienten sind. Außerdem sind die Polynome in der ersten Definition erforderlich, des kleinen Grads zu sein, wohingegen diejenigen in der zweiten Definition erforderlich sind, spezifische Wurzeln zu haben.

Die Gleichwertigkeit der zwei Definitionen wird verwendend des getrennten Fouriers bewiesen verwandeln sich. Das verwandelt sich, der in allen begrenzten Feldern sowie den komplexen Zahlen besteht, gründet eine Dualität zwischen den Koeffizienten von Polynomen und ihren Werten. Diese Dualität kann wie folgt ungefähr zusammengefasst werden: Lassen Sie und seien Sie zwei Polynome des Grads weniger als. Wenn die Werte dessen die Koeffizienten dessen sind, dann (bis zu einem Skalarfaktor und Umstellung) sind die Werte dessen die Koeffizienten dessen. Dafür, um Sinn zu haben, müssen die Werte an Positionen weil genommen werden, wo eine primitive th Wurzel der Einheit ist.

Um genauer zu sein, lassen Sie

::

und nehmen Sie an, und sind durch den getrennten Fourier verbunden verwandeln sich. Dann sind die Koeffizienten und Werte dessen und wie folgt verbunden: für alle, und.

Mit diesen Tatsachen haben wir: Ist ein Codewort des Codes des Rohres-Solomon gemäß der ersten Definition

• wenn, und nur wenn vom Grad weniger ist als (weil die Werte sind),
• wenn und nur wenn für,
• wenn und nur wenn für (weil),
• wenn, und nur wenn ein Codewort des Rohres-Solomon ist, gemäß der zweiten Definition codieren.

Das zeigt, dass die zwei Definitionen gleichwertig sind.

Bemerkungen

Codes des Rohres-Solomon werden gewöhnlich als systematische Codes gebaut. Statt des Sendens wird der encoder das übersandte solches Polynom bauen, dass es dadurch gleichmäßig teilbar ist und im Kennwort offenbar ist. Normalerweise wird der Aufbau durch das Multiplizieren durch x getan, um Platz für die T-Kontrolle-Symbole, das Teilen dieses Produktes zu machen, durch, den Rest, und dann das Ausgleichen diesen Rest zu finden. In diesem Fall werden die T-Kontrolle-Symbole durch die Computerwissenschaft des Rests, s (x) geschaffen:

:

und dieser Rest wird verwendet, um ein gleichmäßig teilbares Kennwort zu machen:

:

mit dem Ergebnis

:

Vertretung, die ein Vielfache des Generator-Polynoms g (x) ist.

Entwerfer sind nicht erforderlich, die "natürlichen" Größen von Codeblöcken des Rohres-Solomon zu verwenden. Eine als "Kürzung" bekannte Technik kann einen kleineren Code jeder gewünschten Größe aus einem größeren Code erzeugen. Zum Beispiel weit verwendet (255,223) kann Code zu (160,128) Code umgewandelt werden, indem er den unbenutzten Teil des Quellblocks mit 95 binären zeroes ausgepolstert wird und sie nicht übersandt wird. Am Decoder wird derselbe Teil des Blocks lokal mit binärem zeroes geladen. Der Delsarte-Goethals-Seidel Lehrsatz illustriert ein Beispiel einer Anwendung von verkürzten Codes des Rohres-Solomon. In der Parallele zur Kürzung eine bekannte Technik weil erlaubt das Durchstechen, einige der verschlüsselten Paritätssymbole wegzulassen.

Eigenschaften

Der Code des Rohres-Solomon ist [n, k, n − k + 1] Code; mit anderen Worten ist es ein geradliniger Block-Code der Länge n (über F) mit der Dimension k und minimalen Entfernung von Hamming n − k + 1. Der Code des Rohres-Solomon ist im Sinn optimal, dass die minimale Entfernung den maximalen Wert hat, der für einen geradlinigen Code der Größe (n, k) möglich ist; das ist als der gebundene Singleton bekannt. Solch ein Code wird auch einen Code der maximalen trennbaren Entfernung (MDS) genannt.

Die fehlerkorrigierende Fähigkeit eines Codes des Rohres-Solomon wird durch seine minimale Entfernung, oder gleichwertig, durch, das Maß der Überfülle im Block bestimmt. Wenn die Positionen der Fehlersymbole im Voraus nicht bekannt sind, dann kann ein Code des Rohres-Solomon bis zu falschen Symbolen korrigieren, d. h. er kann halb so viel Fehler korrigieren, wie es überflüssige zum Block hinzugefügte Symbole gibt. Manchmal sind Fehlerpositionen im Voraus bekannt (z.B, "Seiteninformation" in Demodulator-Verhältnissen des Signals zum Geräusch) — diese werden Ausradierungen genannt. Ein Code des Rohres-Solomon (wie jeder MDS-Code) ist im Stande, doppelt so viele Ausradierungen als Fehler zu korrigieren, und jede Kombination von Fehlern und Ausradierungen kann so lange die Beziehung 2E + S  n &minus korrigiert werden; k ist zufrieden, wo die Zahl von Fehlern ist und die Zahl von Ausradierungen im Block ist.

Für den praktischen Gebrauch von Codes des Rohres-Solomon ist es üblich, ein begrenztes Feld mit Elementen zu verwenden. In diesem Fall kann jedes Symbol als - Bit-Wert vertreten werden.

Der Absender sendet die Datenpunkte als verschlüsselte Blöcke, und die Zahl von Symbolen im verschlüsselten Block ist. So hat ein Code des Rohres-Solomon, der auf 8-Bit-Symbolen funktioniert, Symbole pro Block. (Das ist ein sehr populärer Wert wegen des Vorherrschens von byteorientierten Computersystemen.) Die Zahl, damit

Die obengenannten Eigenschaften von Codes des Rohres-Solomon machen sie besonders gut passend zu Anwendungen, wo Fehler in Brüchen vorkommen. Das ist, weil es für den Code nicht von Bedeutung ist, wie viele Bit in einem Symbol irrtümlicherweise sind — wenn vielfache Bit in einem Symbol verdorben werden, zählt es nur als ein einzelner Fehler. Umgekehrt, wenn ein Datenstrom durch Fehlerbrüche oder Schulabbrecher, aber durch zufällige einzelne Bit-Fehler nicht charakterisiert wird, ist ein Code des Rohres-Solomon gewöhnlich eine schlechte Wahl im Vergleich zu einem binären Code.

Der Code des Rohres-Solomon, wie der Convolutional-Code, ist ein durchsichtiger Code. Das bedeutet, dass, wenn die Kanalsymbole irgendwo entlang der Linie umgekehrt worden sind, die Decoder noch funktionieren werden. Das Ergebnis wird die Inversion der ursprünglichen Daten sein. Jedoch verliert der Code des Rohres-Solomon seine Durchsichtigkeit, wenn der Code verkürzt wird. Die "fehlenden" Bit in einem verkürzten Code müssen entweder durch Nullen oder durch je nachdem gefüllt werden, ob die Daten ergänzt werden oder nicht. (Um es ein anderer Weg zu stellen, wenn die Symbole umgekehrt werden, dann muss die Nullauffüllung zu einer umgekehrt werden - füllen sich.) Aus diesem Grund ist es dass der Sinn der Daten (d. h., wahr oder ergänzt) obligatorisch, vor der Entzifferung des Rohres-Solomon aufgelöst werden.

Fehlerkorrektur-Algorithmen

Theoretischer Decoder

beschrieben ein theoretischer Decoder, der Fehler durch die Entdeckung des populärsten Nachrichtenpolynoms korrigiert hat. Der Decoder für einen RS-Code würde auf alle möglichen Teilmengen von Symbolen vom Satz von Symbolen schauen, die erhalten wurden. Für den Code, um im Allgemeinen mindestens korrigierbar zu sein, mussten Symbole richtig erhalten werden, und Symbole sind erforderlich, um das Nachrichtenpolynom zu interpolieren. Der Decoder würde ein Nachrichtenpolynom für jede Teilmenge interpolieren, und es würde die resultierenden polynomischen Kandidaten nachgehen. Die populärste Nachricht ist das korrigierte Ergebnis. Leider gibt es viele Teilmengen, so ist der Algorithmus unpraktisch. Die Zahl von Teilmengen ist der binomische Koeffizient, und die Zahl von Teilmengen ist für sogar bescheidene Codes unausführbar. Für einen Code, der 3 Fehler korrigieren kann, würde der naive theoretische Decoder 359 Milliarden Teilmengen untersuchen. Der RS-Code hat einen praktischen Decoder gebraucht.

Decoder von Peterson

entwickelt ein praktischer Decoder auf der Syndrom-Entzifferung gestützt. Berlekamp würde (unten) diesen Decoder übertreffen.

Syndrom-Entzifferung

Die übersandte Nachricht wird als die Koeffizienten eines Polynoms s (x) angesehen, der durch ein Generator-Polynom g (x) teilbar ist.

::

wo α ist eine primitive Wurzel.

Seitdem s (x) ist durch den Generator g (x), hieraus folgt dass teilbar

:

Das übersandte Polynom wird unterwegs durch ein Fehlerpolynom e (x) verdorben, um das erhaltene Polynom r (x) zu erzeugen.

::

wo e der Koeffizient für die i-th Macht von x ist. Koeffizient e wird Null sein, wenn es keinen Fehler an dieser Macht von x und Nichtnull gibt, wenn es einen Fehler gibt. Wenn es &nu gibt; Fehler an verschiedenen Mächten i von x, dann

:

Die Absicht des Decoders ist, die Zahl von Fehlern zu finden (ν), die Positionen der Fehler (i) und des Fehlers schätzt auf jene Positionen (e).

Die Syndrome S werden als definiert

:\begin {richten }\aus

S_j &= r (\alpha^j) = s (\alpha^j) + e (\alpha^j) = 0 + e (\alpha^j) = e (\alpha^j), \j=1,2, \ldots, n-k \\

&= \sum_ {k=1} ^ {\\nu} e_ {i_k} \left (\alpha^ {j} \right) ^ {i_k }\

\end {richten }\aus</Mathematik>

Der Vorteil des Schauens an den Syndromen besteht darin, dass das Nachrichtenpolynom aussteigt.

Fehler locators und Fehlerwerte

Für die Bequemlichkeit, definieren Sie den Fehler locators X, und Fehler schätzt Y als:

:

Dann können die Syndrome in Bezug auf den Fehler locators und die Fehlerwerte als geschrieben werden

:

Die Syndrome geben ein System von n &minus; k &ge; 2&nu; Gleichungen in 2&nu; unknowns, aber dieses Gleichungssystem ist in den X nichtlinear und hat keine offensichtliche Lösung. Jedoch, wenn die X (sieh unten) bekannt waren, dann stellen die Syndrom-Gleichungen ein geradliniges Gleichungssystem zur Verfügung, das für die Y Fehlerwerte leicht gelöst werden kann.

:

X_1^1 & X_2^1 & \cdots & X_\nu^1 \\

X_1^2 & X_2^2 & \cdots & X_\nu^2 \\

\vdots & \vdots && \vdots \\

X_1^ {n-k} & X_2^ {n-k} & \cdots & X_\nu^ {n-k} \\

\end {bmatrix }\\begin {bmatrix }\

Y_1 \\Y_2 \\\vdots \\Y_\nu

\end {bmatrix }\\begin {bmatrix }\

S_1 \\S_2 \\\vdots \\S_ {n-k }\

\end {bmatrix }\</Mathematik>

Folglich findet das Problem die X.

Fehler locator Polynom

Peterson hat eine geradlinige Wiederauftreten-Beziehung gefunden, die ein System von geradlinigen Gleichungen verursacht hat.

Das Lösen jener Gleichungen identifiziert die Fehlerpositionen.

Definieren Sie den Fehler locator Polynom &Lambda; (x) als

:

Die Nullen &Lambda; (x) sind die Gegenstücke:

::

Multiplizieren Sie beide Seiten damit, und es wird noch Null sein.

:\begin {richten }\aus

& Y_k X_k^ {j +\nu} \Lambda (X_k^ {-1}) = 0. \\

\text {Folglich} & Y_k X_k^ {j +\nu} + \Lambda_1 Y_k X_k^ {j +\nu} X_k^ {-1} + \Lambda_2 Y_k X_k^ {j +\nu} X_k^ {-2} + \cdots + \Lambda_ {\\nu} Y_k X_k^ {j +\nu} X_k^ {-\nu} = 0, \\

\text {und so} & Y_k X_k^ {j +\nu} + \Lambda_1 Y_k X_k^ {j +\nu-1} + \Lambda_2 Y_k X_k^ {j +\nu-2} + \cdots + \Lambda_ {\\nu} Y_k X_k^j = 0 \\

\end {richten }\aus</Mathematik>

Summe für k = 1 zu

&nu; :

& \sum_ {k=1} ^\\nu (Y_k X_k^ {j +\nu} + \Lambda_1 Y_k X_k^ {j +\nu-1} + \Lambda_2 Y_k X_k^ {j +\nu-2} + \cdots + \Lambda_ {\\nu} Y_k X_k^ {j}) = 0 \\

& \sum_ {k=1} ^\\nu (Y_k X_k^ {j +\nu}) + \Lambda_1 \sum_ {k=1} ^\\nu (Y_k X_k^ {j +\nu-1}) + \Lambda_2 \sum_ {k=1} ^\\nu (Y_k X_k^ {j +\nu-2}) + \cdots + \Lambda_\nu \sum_ {k=1} ^\\nu (Y_k X_k^j) = 0

\end {richten} </Mathematik> {aus}

Das nimmt zu ab

::

Das gibt ein System von geradlinigen Gleichungen nach, die für die Koeffizienten &Lambda gelöst werden können; des Fehlerpositionspolynoms:

:

S_1 & S_2 & \cdots & S_ {\\nu} \\

S_2 & S_3 & \cdots & S_ {\\nu+1} \\

\vdots & \vdots && \vdots \\

S_ {\\nu} & S_ {\\nu+1} & \cdots & S_ {2\nu-1 }\

\end {bmatrix }\\begin {bmatrix }\

\Lambda_ {\\nu} \\\Lambda_ {\\nu-1} \\\vdots \\\Lambda_1

\end {bmatrix }\\begin {bmatrix }\

- S_ {\\nu+1} \\-S_ {\\nu+2} \\\vdots \\-S_ {\\nu +\nu }\

\end {bmatrix }\</Mathematik>

Erhalten Sie die Fehlerpositionen vom Fehler locator Polynom

Verwenden Sie die Koeffizienten &Lambda; gefunden im letzten Schritt, das Fehlerpositionspolynom zu bauen. Die Wurzeln des Fehlerpositionspolynoms können durch die erschöpfende Suche gefunden werden. Der Fehler locators (und folglich die Fehlerpositionen) kann von jenen Wurzeln gefunden werden. Suche von Chien ist eine effiziente Durchführung dieses Schritts.

Berechnen Sie die Fehlerwerte

Sobald die Fehlerpositionen bekannt sind, können die Fehlerwerte bestimmt und korrigiert werden. Das kann durch die direkte Lösung für Y in den Fehlergleichungen getan werden, die oben, oder das Verwenden des Algorithmus von Forney gegeben sind.

Berlekamp-Massey Decoder

Der Berlekamp-Massey Algorithmus ist ein abwechselndes wiederholendes Verfahren, für den Fehler locator Polynom zu finden. Während jeder Wiederholung berechnet es eine Diskrepanz, die auf einem aktuellen Beispiel &Lambda gestützt ist; (x) mit einer angenommenen Zahl von Fehlern e:

:

und passt sich dann &Lambda an; (x) und e so dass ein wiederberechneter &Delta; würde Null sein. Berlekamp-Massey Algorithmus hat ein Detaillieren des Verfahrens. Im folgenden Beispiel, C (x) wird verwendet&Lambda zu vertreten; (x).

Beispiel

Betrachten Sie den Code des Rohres-Solomon als definiert in mit und (das wird in PDF417 Strichcodes verwendet). Das Generator-Polynom ist

:

Wenn das Nachrichtenpolynom ist, dann wird das Kennwort wie folgt berechnet.

::

Fehler in der Übertragung könnten das veranlassen, stattdessen erhalten zu werden.

:

Die Syndrome werden durch das Auswerten r an Mächten &alpha;. berechnet

::

Um die Fehler zu korrigieren, verwenden Sie zuerst den Berlekamp-Massey Algorithmus, um den Fehler locator Polynom zu berechnen.

Der Endwert von C ist der Fehler locator Polynom, &Lambda; (x). Die Nullen können durch den Probe-Ersatz gefunden werden. Sie sind x = 757 = 3 und x = 562 = 3, entsprechend den Fehlerpositionen. Um die Fehlerwerte zu berechnen, wenden Sie den Algorithmus von Forney an.

::::Wenn er

ab und ab vom erhaltenen Polynom Abstriche macht, bringt r das ursprüngliche Kennwort s wieder hervor.

Euklidischer Decoder

Eine andere wiederholende Methode, für den Fehler locator Polynom zu berechnen, basiert auf dem Euklidischen Algorithmus

:t = Zahl von Gleichheiten

:R = x

:S = Syndrom-Polynom

:A = 1

:B = 0

:i = 0

:while-Grad von S &ge; (t/2)

:: Q = R / S

::S = R - Q S = R modulo S

:: = Q + B

:: R = S

:: B = EIN

:: ich = ich + 1

:&Lambda; (x) = / (0)

:&Omega; (x) = (-1) S / (0)

(0) ist der unveränderliche (am wenigsten bedeutende) Begriff von A.

Hier ist ein Beispiel der Euklidischen Methode mit denselben Daten wie das Beispiel von Berlekamp Massey oben. Im Tisch unten sind R und S vorwärts, A, und B werden umgekehrt.

:&Lambda; (x) = / 544 = 001 + 821 x + 329 x

:&Omega; (x) = (-1) S / 544 = 546 x + 732

Die Entzifferung im Frequenzgebiet (Skizze)

Die obengenannten Algorithmen werden im Zeitabschnitt präsentiert. Die Entzifferung im Frequenzgebiet, das Verwenden von Fourier gestalten Techniken um, kann sich rechenbetont und Durchführungsvorteile bieten.

Der folgende ist eine Skizze der Hauptidee hinter dieser Fehlerkorrektur-Technik.

Definitionsgemäß wird ein Codewort eines Codes des Rohres-Solomon durch die Folge von Werten eines Polynoms des niedrigen Grads über ein begrenztes Feld gegeben. Eine Schlüsseltatsache für den Fehlerkorrektur-Algorithmus ist, dass die Werte und die Koeffizienten eines Polynoms durch den getrennten Fourier verbunden sind, verwandeln sich.

Der Zweck eines Fouriers verwandelt sich ist, ein Signal von einem Zeitabschnitt bis ein Frequenzgebiet oder umgekehrt umzuwandeln.

Im Falle des Fouriers verwandeln sich über ein begrenztes Feld, das Frequenzbereichssignal entspricht den Koeffizienten eines Polynoms, und das Zeitabschnitt-Signal entspricht den Werten desselben Polynoms.

Wie gezeigt, in Abbildungen 1 und 2 entspricht ein isolierter Wert im Frequenzgebiet einer glatten Welle im Zeitabschnitt. Die Wellenlänge hängt von der Position des isolierten Werts ab.

Umgekehrt, wie gezeigt, in Abbildungen 3 und 4, entspricht ein isolierter Wert im Zeitabschnitt einer glatten Welle im Frequenzgebiet.

In einem Code des Rohres-Solomon wird das Frequenzgebiet in zwei Gebiete, wie gezeigt, in der Abbildung 5 geteilt: ein linkes (niederfrequentes) Gebiet der Länge und ein richtiges (hochfrequenz)-Gebiet der Länge. Ein Datenwort wird dann ins linke Gebiet eingebettet (entsprechend den Koeffizienten eines Polynoms des Grads höchstens), während das richtige Gebiet mit Nullen gefüllt wird. Das Ergebnis ist in den Zeitabschnitt umgestalteter Fourier, ein Codewort nachgebend, das nur niedriger Frequenzen zusammengesetzt wird. Ohne Fehler kann ein Codewort durch die Rückseite Fourier decodiert werden, der es zurück ins Frequenzgebiet umgestaltet.

Denken Sie jetzt ein Codewort, das einen einzelnen Fehler, wie gezeigt, im Rot in der Abbildung 6 enthält. Die Wirkung dieses Fehlers im Frequenzgebiet ist eine glatte Monofrequenzwelle im richtigen Gebiet, genannt das Syndrom des Fehlers. Die Fehlerposition kann durch die Bestimmung der Frequenz des Syndrom-Signals bestimmt werden.

Ähnlich, wenn zwei oder mehr Fehler im Codewort eingeführt werden, wird das Syndrom ein Signal sein, das aus zwei oder mehr Frequenzen, wie gezeigt, in der Abbildung 7 zusammengesetzt ist. So lange es möglich ist, die Frequenzen zu bestimmen, aus denen das Syndrom zusammengesetzt wird, ist es möglich, die Fehlerpositionen zu bestimmen. Bemerken Sie, dass die Fehlerpositionen nur von den Frequenzen dieser Wellen abhängen, wohingegen die Fehlerumfänge von ihren Umfängen und Phase abhängen.

Das Problem, die Fehlerpositionen zu bestimmen, ist deshalb auf das Problem der Entdeckung, in Anbetracht einer Folge von Werten, des kleinsten Satzes von elementaren Wellen reduziert worden, in die diese Werte zersetzt werden können. Es ist vom Digitalsignal bekannt, das in einer Prozession geht, dass dieses Problem zur Entdeckung der Wurzeln des minimalen Polynoms der Folge, oder gleichwertig gleichwertig ist, das kürzeste geradlinige Feed-Back-Verschiebungsregister (LFSR) für die Folge zu finden. Das letzte Problem kann entweder ineffizient durch das Lösen eines Systems von geradlinigen Gleichungen, oder effizienter durch den Berlekamp-Massey Algorithmus behoben werden.

Die Entzifferung außer der Fehlerkorrektur hat gebunden

Der Singleton hat Staaten gebunden, dass die minimale Entfernung d eines geradlinigen Block-Codes der Größe (n, k) durch n &minus ober begrenzt wird; k + 1. Wie man gewöhnlich verstand, hat die Entfernung d die Fehlerkorrektur-Fähigkeit auf d/2  beschränkt. Der Code des Rohres-Solomon erreicht das hat mit der Gleichheit gebunden, und kann so bis zu  korrigieren (n &minus; k + 1)/2  Fehler. Jedoch ist diese gebundene Fehlerkorrektur nicht genau.

1999, Madhu der Sudan und Venkatesan Guruswami an MIT haben "Verbesserte Entzifferung von Codes des Rohres-Solomon und Algebraischen Geometrie" das Einführen eines Algorithmus veröffentlicht, der die Korrektur von Fehlern außer der Hälfte der minimalen Entfernung des Codes berücksichtigt hat. Es gilt für Codes des Rohres-Solomon und mehr allgemein zu algebraischen geometrischen Codes. Dieser Algorithmus erzeugt eine Liste von Kennwörtern (es ist ein listendecodierender Algorithmus), und basiert auf der Interpolation und factorization von Polynomen und seinen Erweiterungen.

Weiche Entzifferung

Die algebraischen Entzifferungsmethoden, die oben beschrieben sind, sind Methoden der harten Entscheidung, was bedeutet, dass für jedes Symbol eine harte Entscheidung über seinen Wert getroffen wird. Das Advent von LDPC und Turbocodes, die wiederholte Glaube-Fortpflanzungsentzifferungsmethoden der weichen Entscheidung verwenden, Fehlerkorrektur-Leistung in der Nähe von der theoretischen Grenze zu erreichen, hat Interesse an der Verwendung der Entzifferung der weichen Entscheidung zu herkömmlichen algebraischen Codes gespornt. 2003 haben Ralf Koetter und Alexander Vardy eine polynomisch-malige weiche Entscheidung algebraischer listendecodierender Algorithmus für RS-Codes präsentiert, der nach der Arbeit vom Sudan und Guruswami basiert hat.

Anwendungen

Datenlagerung

Das Codieren des Rohres-Solomon wird in Massenlagerungssystemen sehr weit verwendet, um zu korrigieren

die Platzen-Fehler haben mit Mediadefekten verkehrt.

Das Codieren des Rohres-Solomon ist ein Schlüsselbestandteil der CD. Es war der erste Gebrauch des starken Fehlerkorrektur-Codierens in einem serienmäßig hergestellten Verbraucherprodukt, und DAT und DVD verwenden ähnliche Schemas. In der CD geben zwei Schichten des Codierens des Rohres-Solomon, das durch einen 28-wegigen convolutional interleaver getrennt ist, ein Schema genannt Quer-durchgeschossener Reed Solomon Coding (CIRC) nach. Das erste Element eines CIRC Decoders ist ein relativ schwacher innerer (32,28) Code des Rohres-Solomon, der von (255,251) Code mit 8-Bit-Symbolen verkürzt ist. Dieser Code kann bis zu 2 Bytes Fehler pro 32-Byte-Block korrigieren. Noch wichtiger es beflaggt als Ausradierungen irgendwelche unkorrigierbaren Blöcke, d. h., blockiert mit mehr als 2 Bytes Fehlern. Die decodierten 28-Byte-Blöcke, mit Ausradierungsanzeigen, werden dann durch den deinterleaver zu verschiedenen Blöcken (28,24) Außencode ausgebreitet. Dank des deinterleaving wird ein gelöschter 28-Byte-Block aus dem inneren Code ein einzelnes gelöschtes Byte in jedem von 28 Außencodeblöcken. Der Außencode korrigiert leicht das, da er bis zu 4 solche Ausradierungen pro Block behandeln kann.

Das Ergebnis ist ein CIRC, der völlig richtiger Fehler kann, bis zu 4000 Bit oder ungefähr 2.5 Mm auf der Scheibe-Oberfläche sprengen. Dieser Code ist so stark, dass die meisten CD-Play-Back-Fehler fast sicher durch das Verfolgen von Fehlern verursacht werden, die den Laser veranlassen, Spur zu springen, nicht durch unkorrigierbare Fehlerbrüche.

DVDs verwenden ein ähnliches Schema, aber mit viel größeren Blöcken, (208,192) innerer Code, und (182,172) Außencode.

Fehlerkorrektur des Rohres-Solomon wird auch in parchive Dateien verwendet, die Begleitmultimediadateien auf USENET allgemein angeschlagen werden. Der Verteilte Dienst des rechnerabhängigen Speichers Wuala macht auch vom Rohr-Solomon wenn Gebrauch, Dateien zerbrechend.

Strichcode

Fast alle Zweidimensionalen Strichcodes wie PDF-417, MaxiCode, Datamatrix, QR Code und aztekischer Code verwenden Fehlerkorrektur des Rohres-Solomon, um das richtige Lesen zu erlauben, selbst wenn ein Teil des Strichcodes beschädigt wird. Wenn der Strichcode-Scanner kein Strichcode-Symbol anerkennen kann, wird er es als eine Ausradierung behandeln.

Ein anderer Strichcode, der das Codieren des Rohres-Solomon vereinigt, ist vom E-Leser von Nintendo verwendeter derjenige. Das ist ein Videospiel-Liefersystem, das einen zweidimensionalen auf Handelskarten gedruckten Strichcode verwendet. Die Karten werden mit einem Gerät gescannt, das dem Spieljunge-Fortschritt-Spielsystem von Nintendo anhaftet.

Das Codieren des Rohres-Solomon ist in eindimensionalen Strichcodes weniger üblich, aber wird von PostBar symbology verwendet.

Datenübertragung

Spezialformen von Codes des Rohres-Solomon, spezifisch Cauchy-RS und Vandermonde-RS, können verwendet werden, um die unzuverlässige Natur der Datenübertragung über Ausradierungskanäle zu überwinden. Der Verschlüsselungsprozess nimmt einen Code von RS an (N, K), der auf N Kennwörter der Länge N Symbole jede Speicherung K Symbole von Daten hinausläuft, erzeugt zu werden, der dann über einen Ausradierungskanal gesandt wird.

Jede Kombination von K am anderen Ende erhaltenen Kennwörtern ist genug, um alle N Kennwörter wieder aufzubauen. Die Coderate wird allgemein auf 1/2 gesetzt, wenn die Ausradierungswahrscheinlichkeit des Kanals nicht entsprechend modelliert werden kann und gesehen wird, weniger zu sein. Schließlich N ist gewöhnlich 2K, bedeutend, dass mindestens Hälfte aller gesandten Kennwörter erhalten werden muss, um alle gesandten Kennwörter wieder aufzubauen.

Codes des Rohres-Solomon werden auch in xDSL Systemen und den Raumkommunikationsprotokoll-Spezifizierungen von CCSDS als eine Form der Vorwärtsfehlerkorrektur verwendet.

Satellitenübertragung

Eine bedeutende Anwendung des Codierens des Rohres-Solomon sollte die durch die Reisender-Raumsonde zurückgesendeten Digitalbilder verschlüsseln.

Reisender hat das Codieren des Rohres-Solomon eingeführt, das mit Convolutional-Codes, eine Praxis verkettet ist, die sehr weit verbreitet im tiefen Raum und Satelliten (z.B, direkte Digitalrundfunkübertragung) Kommunikationen seitdem geworden ist.

Decoder von Viterbi neigen dazu, Fehler in kurzen Brüchen zu erzeugen. Das Korrigieren dieser Platzen-Fehler ist ein durch kurze oder vereinfachte Codes des Rohres-Solomon am besten getaner Job.

Moderne Versionen von verkettetem Reed-Solomon/Viterbi-Decoded convolutional das Codieren waren und werden auf dem Bahnbrecher von Mars, Galileo, Mars Exploration Rover und Missionen von Cassini verwendet, wo sie innerhalb von ungefähr 1-1.5 DB der äußersten durch die Kapazität von Shannon festgesetzten Grenze leisten.

Diese verketteten Codes werden jetzt durch stärkere Turbocodes ersetzt, wo die übersandten Daten sofort nicht decodiert zu werden brauchen.

Siehe auch

BCH codieren

• Zyklischer Code
• Suche von Chien
• Berlekamp-Massey Algorithmus
• Schicken Sie Fehlerkorrektur nach
• Berlekamp-walisischer Algorithmus
• Gefalteter Code des Rohres-Solomon
• Krauser Ex-Traktor

Referenzen

Links

• Schifra Open Source C ++ Rohr-Solomon Codec
• Die RSCode Bibliothek von Henry Minsky, Rohr-Solomon encoder/decoder
• Offene Quelle Verilog Rohr-Solomon IP
• Ein Tutorenkurs auf dem Codieren des Rohres-Solomon für die Schuld-Toleranz in RAID ähnlichen Systemen
• Die algebraische weiche Entzifferung des Rohres-Solomon codiert
• Durchführung von Matlab des Fehlerund-Ausradierungsrohres-Solomon, das decodiert
• BBC R&D Weißbuch WHP031