Cross-interleaved Reed-Solomon Code

Cross-interleaved Reed-Solomon Codes ( CIRC ) are used to detect and correct errors on CDs .

conditions

The requirements for CIRC can be summarized as follows:

There is a high rate of individual error correction (or random error correction rate) triggered by improperly mapped bits or production errors. Furthermore, there is a high rate of surface error correction, which is triggered by dust particles or scratches on the CD surface. These are responsible for this type of error. A simple decoder strategy is also needed. Last but not least, it should be noted that a further criterion is low redundancies.

Errors on the CD are combinations of random errors and area errors. To cope with this, a product code with additional multiple interleaving is used.

Codes used

Two codes (32,28,5) and are used on the CD , which result from a (255,251,5) RS code by shortening it by 227 or 218 digits. ${\ displaystyle C_ {1}}$ ${\ displaystyle C_ {2} (28,24,5)}$

Cross interleaving

The CIRC processes blocks of 24 bytes, which are referred to below as frame 1 (F1). In the first step a block is delayed with the help of the so-called scrambler as follows: The F1 block is divided into two times 12 bytes and the individual A / B pairs are delayed by 2 blocks each. In the next step, the four blocks that remain free are assigned Q parity symbols (Q1, Q2, Q3, Q4) by the encoder. By placing the parity symbols in the middle of the block, the distance between originally consecutive bytes increases further. This intermediate result is often called an F2 frame. This first interleaving stage is used in the later decoding to correct random errors and to mark area errors. The distinction between A and B blocks is intended to show that these are values of the two audio channels `` left and right '' . ${\ displaystyle C_ {2}}$ ${\ displaystyle C_ {2}}$

The scrambler receives a 28-byte F2 word, each individual byte being delayed by an integer value of 4. The original 28-byte word is distributed over 109 bytes to form an F3a word. ${\ displaystyle C_ {1}}$

If, for example, an area error of length 4 is detected in an F3a word during decoding, the unscrambler will distribute it to four F2 frames. As a result, the original area error can be treated as four individual errors. ${\ displaystyle C_ {1}}$

The encoder receives a 28-byte word, which is formed from 28 different F2 frames, and generates a further 4 bytes with P parity. A final delay stage processes two F3a frames by delaying the odd bytes by an amount of one byte. This means that single errors cannot affect more than one symbol per word, even if two consecutive symbols in a block are incorrect. Two F3 frames are thus created from two F3a frames. This last interleaving makes it possible to correct relatively small surface errors better. This delay stage has the disadvantage that in combination with clock difficulties when reading out a zero word can arise. To prevent this from happening, the P and Q parity symbols are inverted. ${\ displaystyle C_ {1}}$

decoder

Since CIRC decoders are not standardized, there are several ways to implement a decoder. hereinafter denotes the number of deletion flags that are transferred as input. ${\ displaystyle f}$

C1-A decoder

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

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 (better strategy)

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 (better strategy)

IF Syndrom für ein oder null Fehler THEN
   bearbeite ein oder kein Symbol entsprechend
ELSE IF f <= 4 THEN
   IF Syndrom für 2 Fehler AND v = 2 THEN
      bearbeite 2 Symbole entsprechend
   ELSE IF Syndrom für 1 Fehler AND f <= 2 THEN
      bearbeite 3 Symbole entsprechend
   ELSE IF 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

Decoding example

Example part 1

Assume the matrix contains 18 columns with one error each, one column with two errors, another column with four errors and 11 correct columns. In addition, a complete column has already been provided with deletion flags, as the hardware could not recognize this part.

The columns were coded with a (28,24,5) code, which means that it can correct all 1-fold and 2-fold errors. In contrast to the C1-B decoder, the C1-A decoder does not make optimal use of this option. If the C1-B decoder is used, the columns with single and double errors are corrected. The column with the double error is also provided with deletion flags. There can be two cases for the column with four errors. On the one hand, this can be recognized and erasure flags are set, or it is incorrectly corrected and another error occurs. ${\ displaystyle 18 + 1}$

Example part 2

The lines were encoded with a (32,28,5) code. If the C1-B decoder corrects the column with four errors incorrectly, the C2-B decoder encounters five incorrect lines, each with one error and two erasures. If the four errors are detected, the C2-B decoder must correct four incorrect lines with three erasures each. In both cases the C2-B decoder can correct the errors or the deletions correctly. The C2-A decoder could not correct these errors.

A priori, the code as a linear code can correct all 12-fold errors or 24 deletions. The interplay of row and column correction in this example corrects 24 errors and 28 erasures. The correction capacity is thus more than tripled. ${\ displaystyle C_ {1} \ times C_ {2}}$ ${\ displaystyle d = 25}$

Individual evidence

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

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