Reed-Solomon-Code

Der Reed-Solomon - Code ist ein endliches Feld basierten Korrekturcode , dessen Prinzips ist es, eine bauen formales Polynom von den Symbolen zu übertragen und zu ihm überabtasten . Das Ergebnis wird dann anstelle der ursprünglichen Symbole gesendet. Die Redundanz dieser Überabtastung ermöglicht es dem Empfänger der codierten Nachricht, das Polynom zu rekonstruieren, selbst wenn während der Übertragung Fehler aufgetreten sind .

Geschichte

Dieser Code stammt von Irving S. Reed und Gustave Solomon . Es wurde insbesondere zum Codieren von CDs verwendet .

Überblick

Sei m , n , k , t streng positive ganze Zahlen, so dass . Im Allgemeinen nehmen wir m = 8 (manchmal m = 16), n = 255, k = 239, t = 8. Reed-Solomon-Codes sind Blockcodes. Tatsächlich nehmen sie einen Datenblock fester Größe k als Eingabe , wobei jedes Datenelement ein Elementsymbol des endlichen Feldes mit Elementen ist. Diesem Block werden 2 t Steuersymbole hinzugefügt , wodurch ein Ausgangsblock mit einer festen Größe von n gebildet wird . So haben wir: ${\ displaystyle n = 2 ^ {m} -1 = k + 2t}$ $2 ^ {m}$

m : Anzahl der Bits pro Symbol. In dem Fall, in dem m = 8 ist, sind die Symbole Bytes.
k : Anzahl der Informationssymbole, die als Nutzlast bezeichnet werden;
2 t : Anzahl der Prüf- oder Redundanzsymbole;
n : Anzahl der übertragenen Symbole (Nutzlast und Steuerung).

Dank der Hinzufügung von Steuersymbolen können mit diesen Codes zwei Arten von Fehlern korrigiert werden:

Fehler, die eine Modifikation der Daten induzieren, wobei bestimmte Bits vom Wert 0 zum Wert 1 und umgekehrt wie auf dem symmetrischen Binärkanal übergehen ;
Fehler, die zu Informationsverlust führen, werden auch als Löschvorgänge bezeichnet, wenn Informationspakete wie auf dem zu löschenden Binärkanal verloren gehen oder gelöscht werden .

Wir stellen eine Reed-Solomon-Codierung fest oder . ${\ displaystyle RS (n, k)}$ ${\ displaystyle RS (n, k, t)}$

Wenn die Fehlerlokalisierung nicht im Voraus bekannt ist - was in der Praxis der Fall ist -, ist bekannt, dass die Reed-Solomon-Codierung t Fehler korrigiert .

Da n in der Praxis häufig zu groß ist, kann ein Teil der Informationen vor dem Codieren durch Nullen ersetzt werden und wird nicht übertragen, sondern muss vor dem Decodieren hinzugefügt werden. Wir sprechen in diesem Fall von verkürzten Reed-Solomon-Codes .

Man kann sich auch Reed-Solomon-Codes auf beliebigen endlichen Feldern vorstellen.

Ein Beispiel für Reed-Solomon-Code

Es gibt verschiedene Varianten des Reed-Solomon-Codes, die in den letzten Jahrzehnten entwickelt wurden, um Kodierungs- und Dekodierungsprozesse immer schneller zu machen. Eine der möglichen Variationen wird hier vorgestellt.

Zu übermittelnde Informationen

Sei eine Nachricht A, die aus k elementaren Symbolen des endlichen Feldes besteht . Dieses Feld hat das Merkmal 2, was bedeutet, dass es die Berechnungsregel 1 + 1 = 0 oder sogar 1 = -1 erfüllt oder dass es keinen Unterschied zwischen Summe und Differenz gibt. Es hat auch ein sogenanntes primitives Element mit der folgenden Eigenschaft: ${\ displaystyle \ mathbb {F} _ {2 ^ {m}}}$ $\Alpha$

Die Elemente bilden eine Basis als m- dimensionaler Vektorraum auf dem Körper . ${\ displaystyle (1, \ alpha, \ alpha ^ {2}, ..., \ alpha ^ {m-1})}$ ${\ displaystyle \ mathbb {F} _ {2 ^ {m}}}$ $\ mathbb {F} _ {2}$
$\Alpha$ erzeugt die multiplikative Gruppe von ${\ displaystyle \ mathbb {F} _ {2 ^ {m}}}$

Somit können die Nicht-Null-Elemente von als lineare Kombinationen von mit Koeffizienten in {0,1}, aber auch als Potenz von zwischen 0 und geschrieben werden . ${\ displaystyle \ mathbb {F} _ {2 ^ {m}}}$ ${\ displaystyle (1, \ alpha, \ alpha ^ {2}, ..., \ alpha ^ {m-1})}$ $\Alpha$ ${\ displaystyle 2 ^ {m} -2}$

Die k Symbole, aus denen die Nachricht A besteht, werden als Koeffizienten eines Polynoms mit einem Grad kleiner oder gleich k & supmin; ¹ betrachtet, dh ein Element von . Dieses Polynom ist die zu übertragende Information und wird erneut notiert . ${\ displaystyle \ mathbb {F} _ {2 ^ {m}} [X]}$ $BEIM$

Codierung

Wir nennen das Generatorpolynom das Polynom vom Grad 2 t, das wie folgt definiert ist: $G$

{\ displaystyle G (X) = (X + \ alpha) (X + \ alpha ^ {2}) \ dots (X + \ alpha ^ {2t})}

Dieses Polynom lässt für Wurzeln die . ${\ displaystyle \ alpha ^ {i}, 1 \ leq i \ leq 2t}$

Wir definieren das Kontrollpolynom als den Rest der euklidischen Division von durch Dieses Polynom hat einen Grad von streng weniger als 2 t . Die Koeffizienten dieses Polynoms bilden den Informationssteuercode A. $B.$ ${\ displaystyle A \ times X ^ {2t}}$ ${\ displaystyle G.}$

Wir definieren dann das Polynom . Dieses Polynom ist von einem Grad kleiner oder gleich . Es hat die Eigenschaft, sich für aufzuheben . (Erinnerung: Wir befinden uns immer noch in einem Feld mit der Eigenschaft 2, also haben + und - den gleichen Effekt.) ${\ displaystyle C = A \ times X ^ {2t} + B}$ ${\ displaystyle k-1 + 2t = n-1}$ ${\ displaystyle X = \ alpha ^ {i}, 1 \ leq i \ leq 2t}$

Nachrichtenübertragung

Die Koeffizienten des Polynoms werden an den Empfänger übertragen. Während dieser Übertragung können Fehler in Bezug auf bestimmte Koeffizienten auftreten, und der Empfänger empfängt Koeffizienten, die ein Polynom bilden . $VS$ $D.$

Der Empfänger testet dann, ob für alle i zwischen 1 und 2 t wir haben . Wenn ja, wird davon ausgegangen, dass kein Übertragungsfehler aufgetreten ist . Es findet die Information A in den k -1 -Koeffizienten der Terme höchsten Grades des Polynoms . ${\ displaystyle D (\ alpha ^ {i}) = 0}$ ${\ displaystyle D = C}$ $D.$

Wenn mindestens einer der Werte ungleich Null ist, ist bei mindestens einem der Koeffizienten ein Übertragungsfehler aufgetreten. Der Empfänger ist jedoch der Ansicht, dass die Anzahl der betroffenen Koeffizienten kleiner oder gleich t ist . Unter dieser Annahme kann die anfängliche C-Nachricht rekonstruiert werden. ${\ displaystyle D (\ alpha ^ {i})}$

Korrektur von Fehlern

Wenn verschieden ist , das heißt , ein Polynom vom Grad weniger als oder gleich n -1 ist , und mit einer Anzahl von Nicht-Null - Koeffizienten. Nach der Hypothese nehmen wir an, dass dies kleiner oder gleich t ist . Lassen Sie uns posieren: $D.$ $VS$ ${\ displaystyle E = D + C}$ $\nackt$ $\nackt$

{\ displaystyle E = \ sum _ {r = 1} ^ {\ nu} e_ {i_ {r}} X ^ {i_ {r}}}

, Und die wobei unterschiedliche Indizes , die zwischen 0 und variieren kann n -1.

{\ displaystyle y_ {r} = e_ {i_ {r}}}

{\ displaystyle x_ {r} = \ alpha ^ {i_ {r}}}

{\ displaystyle i_ {r}}

$E.$ ist dem Empfänger derzeit unbekannt. Es ist für diesen zu bestimmen:

Die Anzahl der Fehler ,

\nackt

die Reihen, in denen sich diese Fehler befinden,

{\ displaystyle i_ {r}}

die Werte dieser Fehler.

{\ displaystyle y_ {r}}

Sobald diese Informationen rekonstruiert wurden, kann der Empfänger das Polynom bestimmen und die ursprüngliche Nachricht rekonstruieren . Dazu folgen wir den folgenden fünf Schritten. $E.$ ${\ displaystyle C = D + E}$

1) Berechnung von Syndromen: Wir berechnen die 2 t- Größen , sogenannte Syndrome . Da und dass die Null sind, haben wir auch: ${\ displaystyle S_ {j} = D (\ alpha ^ {j}), 1 \ leq j \ leq 2t}$ ${\ displaystyle E = D + C}$ ${\ displaystyle C (\ alpha ^ {j})}$

{\ displaystyle S_ {j} = E (\ alpha ^ {j}) = \ sum _ {r = 1} ^ {\ nu} e_ {i_ {r}} \ alpha ^ {ji_ {r}} = \ sum _ {r = 1} ^ {\ nu} y_ {r} x_ {r} ^ {j}}

Dies liefert 2 t Gleichungen, deren Unbekannte und mehr in Nummer 2 t sind . Das System ist jedoch nicht linear und seine Auflösung ist technisch. $x_ {r}$ ${\ displaystyle y_ {r}}$

2) Bestimmung der Anzahl der Fehler: Wir betrachten das Polynom, dessen Wurzeln die Umkehrungen von sind . Dieses Polynom dehnt sich in der Form aus . Wir können überprüfen, ob die dem Empfänger unbekannten Koeffizienten ein lineares Gleichungssystem erfüllen, wobei die j- te Gleichung für j von 1 bis 1 variiert : ${\ displaystyle \ Lambda (X) = \ prod _ {r = 1} ^ {\ nu} (1-x_ {r} X)}$ $x_ {r}$ ${\ displaystyle \ Lambda (X) = 1 + \ lambda _ {1} X + \ lambda _ {2} X ^ {2} + \ dots + \ lambda _ {\ nu} X ^ {\ nu}}$ $\nackt$ ${\ displaystyle \ lambda _ {r}}$ $\nackt$ $\nackt$

{\ displaystyle S _ {\ nu + j-1} \ lambda _ {1} + S _ {\ nu + j-2} \ lambda _ {2} + \ dots + S_ {j} \ lambda _ {\ nu } = -S _ {\ nu + j}}

tatsächlich : ${\ displaystyle \ left (\ sum _ {i = 1} ^ {\ nu} S _ {\ nu + ji} \ lambda _ {i} = \ sum _ {r = 1} ^ {\ nu} y_ {r } (\ sum _ {i = 1} ^ {\ nu} x_ {r} ^ {\ nu + ji} \ lambda _ {i}) = \ sum _ {r = 1} ^ {\ nu} y_ {r } x_ {r} ^ {\ nu + j} (\ Lambda (x_ {r} ^ {- 1}) - 1) = - S _ {\ nu + j} \ right)}$

Darüber hinaus ist der größte Wert kleiner oder gleich t, für den die Determinante dieses Systems ungleich Null ist, genau die Zahl , die der Anzahl der übertragenen Fehler entspricht. Wir beginnen daher mit , und wenn die Determinante Null ist, nehmen wir ab, bis wir eine Determinante ungleich Null erhalten. $\nackt$ $\nackt$ ${\ displaystyle \ nu = t}$ $\nackt$

3) Bestimmung des Ortes der Fehler: Sobald dies bestimmt ist, wird das System gelöst, das das Polynom definiert . Wir suchen nach den Wurzeln dieses Polynoms, dessen Umkehrungen die Werte von ergeben . Für jedes r zwischen 1 und , suchen wir die Leistung von so dass . Die Reihen der übertragenen Fehler wurden somit bestimmt . $\nackt$ $\ Lambda$ $x_ {r}$ $\nackt$ ${\ displaystyle i_ {r}}$ $\Alpha$ ${\ displaystyle x_ {r} = \ alpha ^ {i_ {r}}}$ ${\ displaystyle i_ {r}}$

4) Bestimmung des Wertes der Fehler: Die nunmehr bekannt ist, kann man das System , dessen allgemeine Gleichung lösen und deren Unbekannten sind die , die es ermöglichen , die Werte dieser Unbekannten zu bestimmen. Dies sind die Werte der gemachten Fehler. $x_ {r}$ ${\ displaystyle S_ {j} = \ sum _ {r = 1} ^ {\ nu} y_ {r} x_ {r} ^ {j}}$ ${\ displaystyle y_ {r}}$

5) Korrektur der empfangenen Nachricht: Wenn wir das und das kennen , kennen wir das Polynom und damit die ursprüngliche Nachricht ${\ displaystyle i_ {r}}$ ${\ displaystyle y_ {r}}$ ${\ displaystyle E,}$ ${\ displaystyle C = D + E}$

Löschfehler

Wenn die Informationen auf ein Medium wie eine CD oder DVD geschrieben werden, können Löschfehler auftreten. Der Fehler ist genau lokalisiert, aber dort können keine Informationen gelesen werden. Wir können jedoch die gelöschten Symbole mit Hilfe der durch die Syndrome gegebenen Gleichungen wiederherstellen. Da die Orte bekannt sind, dass die Unbekannten die einzigen Werte sind und wir 2 t- Gleichungen haben, können wir das Löschen von Symbolen korrigieren . $x_ {r}$ ${\ displaystyle y_ {r}}$ ${\ displaystyle \ nu = 2t}$

Anwendungen

Für die CD werden 2 Reed-Solomon-Codierungen verwendet (CIRC-Code für Cross Interleaved Reed-Solomon-Code). Wir codieren ein erstes Mal mit einem Code C1 = RS (28, 24), dann verschachteln wir (dies ermöglicht es, die Informationen zu verteilen, um den Zügen aufeinanderfolgender Fehler besser zu widerstehen, die einen Kratzer verursachen können, der viele Bytes lokal zerstört) dann werden die verschachtelten Daten erneut mit einem Code C2 = RS (32, 28) codiert. Die Idee ist, dass der erste Code es ermöglicht, das Umgebungsrauschen zu beseitigen. Wenn er jedoch nicht korrigiert werden kann (z. B. wenn ein Fehlerstoß auftritt), wird der Block gelöscht (da wir doppelt so viel korrigieren können, werden nur falsche Zeichen gelöscht). und dann wird der Code deinterlaced . Somit wird der Informationsverlust über einen großen Datenbereich verwässert, wodurch der Code diese Löschungen korrigieren kann.

Für die DVD gilt das gleiche Prinzip wie für die CD, wir haben einen Code PI = RS (182, 172) und einen Code PO = RS (208, 192)

Satellitenübertragung

Für DVB lautet die Codierung RS (204, 188, t = 8).

Datenübertragung

In ADSL / ADSL2 / ADSL2plus ist die Codierung häufig RS (240, 224, t = 8) oder sogar RS (255, 239, t = 8).

Beispiel

für DVB ist die Codierung RS (204, 188, t = 8)

Für 188 (= k) Bytes am Eingang werden 16 (= 2 t ) Fehlerkorrekturbytes addiert , was 204 am Encoderausgang ergibt.

8 Bytes (= t) von 204 können korrigiert werden.

Wenn mehr als 8 Bytes als fehlerhaft erkannt werden, wird der Benutzerdatenblock als fehlerhaft markiert. Es wird dann kein Fehler korrigiert

Die Schwäche

Aufgrund der geringen Anzahl von Symbolen, die durch die Reed-Solomon-Codierung korrigiert werden können, ist diese Codierung im Fall von Impulsrauschen mit langer Dauer oder regelmäßigem Zufallsrauschen sehr schlecht.

Bei der Datenübertragung (ADSL, DVB-T) können Impulsgeräusche durch Motoren, Relais, Entladungslampen oder Beleuchtungsröhren, elektrische Zäune usw. verursacht werden.
Bei der Datenspeicherung (CD, DVD) kann ein Impulsrauschen auf einen Kratzer auf dem Medium zurückzuführen sein.

Verwendung in einem Modem mit Faltungscodierer

Im Allgemeinen wird bei der Übertragung in einem Modem (ADSL, IDR / SMS-Satellitenmodem, DVB-S usw.) die durch einen Interleaver verstärkte Reed-Solomon-Codierung von einem Faltungscodierer begleitet. Beim Empfang werden die vom Viterbi- Decoder nicht korrigierten Restfehler dann in den Originalblöcken deinterlaced und vom Reed-Solomon-Decoder im Umfang seiner Korrekturleistung korrigiert.

Der Zweck des Deinterlacers besteht darin, beim Empfang einen Burst gruppierter und häufig nicht korrigierbarer Fehler (Impulsrauschen) durch eine Vielzahl verteilter und häufig korrigierbarer Fehler für den Reed-Solomon-Decoder zu ersetzen.

Externe Links

Reed-Solomon-Code Prinzipien und Programmierung von Reed-Solomon-Code in Java .
William Geisel, Tutorial zu Reed - Solomon Error Correction Coding , NASA, Technisches Memorandum (1990)

Verweise

(in) IS Reed, G. Solomon, " Polynomcodes über einige endliche Felder " , J. Soc. Indus. Appl. Mathematik. , N o 8,1960, p. 300-304
Pascal Boyer, kleiner Begleiter von Zahlen und ihren Anwendungen , Calvage und Mounet,2019648 p. ( ISBN 978-2-916352-75-6 ) , VI. Kryptographie, Kap. 8.4 („BCH-Codes“), S. 560-562.
(in) D. Gorenstein, N. Ziegler, " Eine Klasse von Fehlerkorrekturcodes in Symbolen $p ^ {m}$ " , J. Soc. Indus. Mathematik. Appl. , N O 9,1961, p. 207-2014
(in) WW Peterson, " Codierungs- und Fehlerkorrekturverfahren für die Bose-Chaudhuri-Codes " , IRE Trans. Informieren. Theorie , n o IT-6,1960, p. 459-470
(in) Maria Bras-Amoros " Ein Dekodierungsansatz für Reed-Solomon-Codes aus ihrer Definition " , Amer. Mathematik. Monthly , vol. 125, n o 4,April 2018, p. 320-338