Reed-Solomon-Code

Kernidee und Bedeutung

Reed-Solomon-Codes, kurz RS-Codes, sind eine Klasse zyklischer Blockcodes. Sie werden in der Kanalkodierung eingesetzt, um Übertragungs- oder Speicherfehler zu erkennen und zu korrigieren. Das geschieht als Vorwärtsfehlerkorrektur: Schon beim Senden werden zusätzliche, redundante Informationen mitgegeben, damit der Empfänger Fehler später finden und teilweise beheben kann.

RS-Codes sind eine Unterklasse der BCH-Codes und zugleich MDS-Codes. MDS steht für Codes, die die Singleton-Schranke mit Gleichheit erfüllen; sie gelten in der Kodierungstheorie deshalb als optimal. Praktisch werden Reed-Solomon-Codes unter anderem bei Compact Disks, digitalen Fernsehsignalen, Mobilfunkstandards, Digital Audio Broadcasting, RAID-6-Systemen, PAR2-Dateiformaten und zweidimensionalen Barcodes wie QR-Code, DataMatrix, Aztec-Code und PDF417 verwendet. In neueren Anwendungen werden sie teilweise durch leistungsfähigere Codes wie Low-Density-Parity-Check-Codes oder Turbo-Codes ersetzt, zum Beispiel im Fernsehstandard DVB-S2.

Motivation

Eine Nachricht kann als Folge von k Zahlen dargestellt werden, zum Beispiel ein Text mithilfe des ASCII-Standards. Bei der Übertragung können Zahlen ausgelöscht oder verfälscht werden. Eine einzelne Zahl zeigt aber nicht von selbst, ob sie richtig oder falsch angekommen ist. Deshalb fügt der Sender redundante Informationen hinzu. Der Empfänger kann die empfangene Nachricht dann mit diesen Zusatzinformationen vergleichen, ihre Integrität prüfen und erkannte Fehler korrigieren.

Die Grundidee ist, die k Zahlen der Nachricht als Werte eines Polynoms an k fest vereinbarten Stützstellen zu betrachten. Ein Polynom vom Grad k - 1 oder kleiner ist durch k passende Werte eindeutig bestimmt. Die Bestimmung dieses Polynoms erfolgt über ein lineares Gleichungssystem; wegen seiner besonderen Form gibt es dafür die Lagrange-Interpolation. Danach wird das Polynom an weiteren Stützstellen ausgewertet. So entsteht eine kodierte Nachricht aus n Zahlen mit n > k.

Wenn bei der Übertragung einige Zahlen ausgelöscht werden, kann das Polynom rekonstruiert werden, solange noch mehr als k Zahlen korrekt erhalten bleiben. Aus dem Polynom erhält man anschließend wieder die ursprüngliche Nachricht. Bei verfälschten Stellen ist das Verfahren komplizierter, aber auch hier können wenige Fehler sicher korrigiert werden. Je größer die Redundanz ist, desto mehr Fehler lassen sich beheben. Es können n - k Auslöschungen korrigiert werden, aber nur (n - k) / 2 Verfälschungen. Darum verbessern Lesesysteme, die Auslöschungen erkennen und als solche ausgeben, meistens die Korrekturfähigkeit.

Die Rechnungen enthalten Divisionen und müssen daher in einem Körper stattfinden. Damit die Werte nicht zu groß werden und die Symbole endlich bleiben, rechnet man in einem endlichen Körper. Dort gibt es nur endlich viele Elemente, die mit den Nachrichtensymbolen verknüpft werden können, und jede Division außer durch 0 ist möglich. Reed-Solomon-Codes eignen sich besonders für Burstfehler, also zusammenhängende Ketten fehlerhafter Bits, wie sie etwa durch einen Kratzer auf einer CD entstehen können.

Formale Definition

Sei F_p ein endlicher Körper mit p Elementen. Dabei ist p = q^m notwendigerweise eine Primzahlpotenz, wobei q prim ist. Man wählt n paarweise verschiedene Elemente u_1, ..., u_n aus F_p aus und hält sie fest. Diese Elemente heißen Stützstellen.

Ein Reed-Solomon-Code RS(p,k,n) der Länge n für Nachrichten der Länge k über F_p besteht aus den Wertetupeln aller Polynome aus F_p[x] mit Grad kleiner k an den gewählten Stützstellen. Die Menge der Kodewörter ist

C = { a = (a_1, ..., a_n) in F_p^n | a_j = f(u_j), j = 1, ..., n },

wobei f in F_p[x] liegt und deg(f) < k gilt. Ein Kodewort ist also die Liste der Werte eines Polynoms an n festgelegten Stellen.

Stützstellen und zyklische Codes

RS-Codes zu verschiedenen zulässigen Stützstellenmengen sind linear isomorph. Das bedeutet: Sie haben dieselbe lineare Struktur, nur in einer anderen Darstellung. Die passende bijektive lineare Abbildung entsteht, indem man zuerst durch Lagrange-Interpolation aus Kodewörtern wieder Polynome vom Grad kleiner k gewinnt und diese Polynome anschließend an einer anderen Stützstellenmenge auswertet.

Eine wichtige Wahl der Stützstellen nutzt Potenzen eines Elements alpha aus F_p. Ist alpha von Ordnung n oder größer, kann man u_1 = 1, u_2 = alpha, ..., u_j = alpha^(j-1), ..., u_n = alpha^(n-1) wählen. Jeder endliche Körper besitzt ein erzeugendes oder primitives Element der multiplikativen Gruppe F_p^* = F_p \ {0}, also ein Element der Ordnung p - 1. Deshalb ist diese Wahl für n = p - 1 immer möglich.

Sind die Stützstellen genau die Potenzen u_1 = 1 und u_j = alpha^(j-1) != 1 für j = 2, ..., n eines Elements alpha der Ordnung n mit alpha^n = 1, dann ist der RS-Code ein zyklischer Code. Das Kodewort zum Polynom f_j(x) = f(alpha^j x) entsteht durch Rotation des Kodewortes zu f(x) um j Stellen nach links. Weil zyklische Codes einfacher implementiert werden können, wird diese Variante im Allgemeinen bevorzugt.

Kodierung und Fehlerkorrektur

Eine Nachricht (a_1, a_2, ..., a_k) in F_p^k kann direkt kodiert werden, indem man ihre k Symbole als Koeffizienten eines Polynoms benutzt:

f(x) = a_1 + a_2 x + a_3 x^2 + ... + a_k x^(k-1) = Summe von i = 1 bis k aus a_i x^(i-1).

Dieses Polynom wird an den Stützstellen u_1, u_2, ..., u_n ausgewertet. Dadurch entsteht das Kodewort c = (c_1, c_2, ..., c_n) = (f(u_1), f(u_2), ..., f(u_n)) in F_p^n.

Für die Anzahl k der Nachrichtensymbole und die geforderte Minimaldistanz d gilt k <= n - d + 1. Die Minimaldistanz ist der kleinste Abstand zwischen zwei verschiedenen Kodewörtern; sie bestimmt wesentlich, wie gut Fehler erkannt und korrigiert werden können. Da ein Polynom vom passenden Grad nur begrenzt viele Nullstellen besitzen kann, enthält jedes gültige Kodewort mindestens d von 0 verschiedene Symbole. Der Code hat daher Minimaldistanz d und kann maximal t = (d - 1) / 2 Fehler korrigieren.

Alternativ kann man die Nachricht nicht als Koeffizienten, sondern in die ersten k Stützstellen des Polynoms kodieren. Dann erhält man eine systematische Kodierung, bei der die Nachricht im Kodewort direkt am Anfang steht. Das Polynom f(x) ist dann das Lagrange-Polynom zu den Paaren ((u_1,a_1), (u_2,a_2), ..., (u_k,a_k)):

f(x) = Summe von i = 1 bis k aus a_i · Produkt über j != i bis k von (x - u_j) / (u_i - u_j).

Da f(u_i) = a_i für i = 1, ..., k gilt, lautet das Kodewort c = (a_1, a_2, ..., a_k, f(u_(k+1)), ..., f(u_n)). Beide Kodierungsvarianten verwenden dieselbe Menge von Kodewörtern und haben deshalb dieselben Fehlerkorrektureigenschaften.

Eigenschaften und Beispiel

Aus der Definition folgen wichtige Kennwerte. Die Codewortlänge ist n. Die Dimension des Codes wird mit |C| = |f| = q^k angegeben. Die Coderate ist R_c = k / n; sie beschreibt, welcher Anteil des Kodeworts Nutzinformation trägt. Die Mindestdistanz beträgt d_min = n - k + 1 und erfüllt damit die Singleton-Schranke. Codes mit dieser Eigenschaft heißen MDS-Codes.

Die Begründung für die Mindestdistanz nutzt den Grad des Polynoms: Ein Polynom f kann höchstens k - 1 Nullstellen besitzen. Im zugehörigen Kodewort können daher höchstens k - 1 Stellen zu 0 werden. Damit ist das Hamming-Gewicht wt(C) >= n - k + 1. Wegen der Linearität gilt dies auch für die Minimaldistanz. Zusammen mit der Singleton-Schranke d_min <= n - k + 1 folgt d_min = n - k + 1.

Im Beispiel wird die Nachricht (a_1, a_2, a_3, a_4, a_5, a_6) = (2,6,8,12,15,13,1) über F_(2^4) betrachtet; die Angabe nennt sieben Werte, obwohl der Index nur bis a_6 läuft. Daraus wird das Polynom f(x) = 2 + 6x + 8x^2 + 12x^3 + 15x^4 + 13x^5 + x^6 gebildet. Die Elemente von F_(2^4) werden als Potenzen eines primitiven Elements alpha dargestellt. Durch Auswertung von f an alpha^0, alpha^1, ..., alpha^14 erhält man das Kodewort

c = (c_1, c_2, ..., c_15) = (f(alpha^0), f(alpha^1), ..., f(alpha^14)) = (3,6,15,6,6,3,13,14,3,12,15,2,11,1,0).