Cross-interleaved Reed-Solomon Code

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Cross-interleaved Reed-Solomon Codes (CIRC) dienen der Fehlererkennung und Fehlerkorrektur bei CDs.

Anforderungen[Bearbeiten]

Die Anforderungen an CIRC kann man folgendermaßen zusammenfassen:

Dieser Artikel oder Abschnitt besteht hauptsächlich aus Listen, an deren Stelle besser Fließtext stehen sollte. Bitte hilf Wikipedia, das zu verbessern. Mehr zum Thema ist hier zu finden.

Es besteht eine hohe Einzelfehlerkorrekturrate (oder Zufallsfehlerkorrekturrate), die ausgelöst durch unsauber abgebildete Bits oder Produktionsfehlerausgelöst werden. Des Weiteren gibt es eine hohe Flächenfehlerkorrekturrate, die durch Staubkörner oder Kratzer auf der CD Oberfläche ausgelöst werden. Diese sind für diese Art von Fehler verantwortlich. Außerdem wird eine einfache Dekodierer-Strategie benötigt. Zu guter letzt ist noch anzuführen, dass ein weiteres Kriterium geringe Redundanzen sind.

Fehler auf der CD sind Kombinationen von Zufallsfehlern und Flächenfehlern. Um dies zu bewältigen, kommt ein Produktcode mit zusätzlich mehrfachem Interleaving zum Einsatz.

Verwendete Codes[Bearbeiten]

Auf der CD werden zwei Codes C_1 (32,28,5) und C_2(28,24,5) verwendet, die durch Verkürzung aus einem (255,251,5) RS-Code durch Verkürzung um 227 bzw. 218 Stellen entstehen.

Cross Interleaving[Bearbeiten]

[1] Der CIRC bearbeitet Blöcke von 24 Byte, die in weitere Folge als Frame 1 (F1) bezeichnet werden. Im ersten Schritt wird ein Block mit Hilfe des so genannten C_2-Scramblers folgendermaßen verzögert: Der F1-Block wird in zwei mal 12 Byte unterteilt und die einzelnen A/B-Paare um jeweils 2 Blöcke verzögert. Die vier freibleibenden Blöcke werden im nächsten Schritt durch den C_2-Encoder mit Q-Paritätssymbolen (Q1,Q2,Q3,Q4) belegt. Durch das Ablegen der Paritätssymbole in der Mitte des Blocks vergrößert sich der Abstand zwischen ursprünglich aufeinander folgenden Bytes weiter. Dieses Zwischenergebnis wird oft F2-Frame genannt Diese erste Interleavingstufe dient im späteren Dekodieren der Korrektur von Zufallsfehlern und der Markierung von Flächenfehlern. Die Unterscheidung zwischen A- und B-Blöcken soll zeigen, dass es sich jeweils um Werte der beiden Audiokanäle ``links und ``rechts handelt.

C2scrambler

Der C_1-Scrambler empfängt ein 28-Byte-F2-Wort, wobei jedes einzelne Byte um einen ganzzahligen Wert von 4 verzögert wird. Das ursprüngliche 28-Byte-Wort wird also über 109 Byte zu einem F3a-Wort verteilt.

C1-Scrambler

Sollte beim Dekodieren zum Beispiel ein Flächenfehler der Länge 4 in einem F3a-Wort erkannt werden, wird dieser durch den C_1-Unscrambler auf vier F2-Frames verteilt. Dadurch kann in weiterer Folge der ursprüngliche Flächenfehler als vier Einzelfehler behandelt werden.

Korrektur eines C1-Fehlers

Der C_1-Encoder empfängt ein 28-Byte-Wort, welches aus 28 verschiedenen F2-Frames gebildet wird, und erzeugt weitere 4 Bytes mit P-Parität. Eine letzte Verzögerungsstufe verarbeitet zwei F3a-Frames, indem die ungeraden Bytes um einen Betrag von einem Byte verzögert werden. Dadurch können Einzelfehler nicht mehr als ein Symbol pro Wort beeinträchtigen, auch wenn zwei aufeinander folgende Symbole eines Blocks fehlerhaft sind. Aus zwei F3a-Frames entstehen somit zwei F3-Frames. Dieses letzte Interleaving ermöglicht es, relativ kleine Flächenfehler besser korrigieren zu können. Durch diese Verzögerungsstufe entsteht der Nachteil, dass in Kombination mit Taktschwierigkeiten beim Auslesen ein Null-Wort entstehen kann. Um dies zu verhindern, werden die P- und Q-Paritätssymbole invertiert.

Decoder[Bearbeiten]

Da CIRC-Decoder nicht standardisiert sind, gibt es mehrere Möglichkeiten einen Decoder zu implementieren. f bezeichnet in weiterer Folge die Anzahl der Auslöschungsflags, die als Input übergeben werden.

C1-A-Decoder[Bearbeiten]

IF Syndrom für ein oder null Fehler THEN
bearbeite ein oder kein Symbol entsprechend
ELSE
setze Auslöschungsflags für das gesamte empfangene Wort
ENDIF

C2-A-Decoder[Bearbeiten]

IF Syndrom für ein oder null Fehler THEN
bearbeite ein oder kein Symbol entsprechend
ELSE IF f > 2 THEN
kopiere C2 Auslöschungsflags von den C1 Auslöschungsflags
ELSE IF f = 2 THEN
versuche 2 Auslöschungen zu korrigieren
ELSE IF f < 2 OR 2 Auslöschungen korrigieren scheitert THEN
setze Auslöschungsflags für das gesamte empfangene Wort
ENDIF

C1-B-Decoder(bessere Strategie)[Bearbeiten]

IF Syndrom für ein oder null Fehler THEN
bearbeite ein oder kein Symbol entsprechend
ELSE IF Syndrom für 2 Fehler THEN
bearbeite 2 Symbole entsprechend
setze Auslöschungsflags für das gesamte empfangene Wort
ELSE
setze Auslöschungsflags für das gesamte empfangene Wort
ENDIF

C2-B-Decoder(bessere Strategie)[Bearbeiten]

IF Syndrom für ein oder null Fehler THEN
bearbeite ein oder kein Symbol entsprechend
ELSEIF f <= 4 THEN
IF Syndrom für 2 Fehler AND v = 2 THEN
bearbeite 2 Symbole entsprechend
ELSEIF Syndrom für 1 Fehler AND f <= 2 THEN
bearbeite 3 Symbole entsprechend
ELSEIF Syndrom für 2 Fehler AND ((v = 1 AND f <= 3) OR (v=0 AND f <= 2))
OR (f <= 2 AND NOT Syndrom für 2 Fehler) THEN
setze Auslöschungsflags für das gesamte empfangene Wort
ELSE
kopiere C2 Auslöschungsflags von C1 Auslöschungsflags
ENDIF
ELSE
kopiere C2 Auslöschungsflags von C1 Auslöschungsflags
ENDIF

Beispiel Decodieren[Bearbeiten]

Beispiel Teil 1

Angenommen die Matrix enthält 18 Spalten mit je einem Fehler, eine Spalte mit zwei Fehlern, eine weitere Spalte mit vier Fehlern und 11 korrekte Spalten. Außerdem wurde bereits eine komplette Spalte mit Auslöschungsflags versehen, da die Hardware diesen Teil nicht erkennen konnte.

Die Spalten wurden mit einem (28,24,5) - Code codiert, das heißt er kann alle 1-fach- und 2-fach-Fehler korrigieren. Der C1-A-Decoder nutzt im Gegensatz zum C1-B-Decoder diese Möglichkeit nicht optimal. Verwendet man den C1-B-Decoder werden die 18+1 Spalten mit Einfach- und Zweifachfehlern korrigiert. Die Spalte mit dem Zweifachfehler wird zusätzlich mit Auslöschungsflags versehen. Bei der Spalte mit vier Fehlern können zwei Fälle auftreten. Zum einen kann dies erkannt werden und es werden Auslöschungsflags gesetzt oder es wird falsch korrigiert und ein weiterer Fehler kommt dazu.

Beispiel Teil 2

Die Zeilen wurden mit einem (32,28,5)-Code codiert. Sollte der C1-B-Decoder die Spalte mit vier Fehlern falsch korrigieren, stößt der C2-B-Decoder auf fünf falsche Zeilen mit je einem Fehler und zwei Auslöschungen. Sollten die vier Fehler erkannt werden muss der C2-B-Decoder vier falsche Zeilen mit je drei Auslöschungen korrigieren. In beiden Fällen kann der C2-B-Decoder die Fehler beziehungsweise die Auslöschungen richtig korrigieren. Der C2-A-Decoder könnte diese Fehler nicht korrigieren.

A priori kann der Code C_1 \times C_2 als Linearcode mit d = 25 alle 12-fach Fehler oder 24 Auslöschungen korrigieren. Durch das Zusammenspiel von Zeilen- und Spaltenkorrektur werden in diesem Beispiel 24 Fehler und 28 Auslöschungen korrigiert. Die Korrekturkapazität wird also mehr als verdreifacht.

Einzelnachweise[Bearbeiten]

  1. K. Pohlmann. Compact Disc Handbuch. IWT, 1 edition, 1994. ISBN 3-88322-500-2.

Siehe auch[Bearbeiten]