Cross-interleaved Reed–Solomon coding

Cross -interleaved Reed -Solomon code ( CIRC ) are used for error detection and error correction in CDs.

Requirements

The requirements of CIRC can be summarized as follows:

• High individual error correction rate (or random error correction rate ): Triggered by unclean pictured bits or production errors.
• High surface error correction rate: specks of dust or scratches on the CD surface are triggers for this kind of errors.
• Simple decoder strategies
• Little redundancy

Errors on the CD, combinations of random errors and surface defects. To cope with this, a product code is additionally with multiple interleaving used.

Codes used

On the CD are two codes ( 32,28,5 ), and uses that result from shortening of a ( 255,251,5 ) RS code by shortening by 227 and 218 points.

Cross interleaving

The CIRC processed blocks of 24 bytes, which are referred to in more consequence than frame 1 (F1). In the first step, a block with the help of so-called scrambler C_2 is delayed as follows: F1 - block is divided into two times 12 bytes, and delays the individual A / B pairs by 2 blocks. The four remaining free blocks in the next step by the encoder with Q- parity symbols (Q1, Q2, Q3, Q4) occupied. By storing the parity symbols in the middle of the block, the distance between originally consecutive bytes enlarged further. This intermediate result is often called F2 Frame This first interleaving stage is used in later decoding the correction of random errors and the marking of surface defects. The distinction between the A and B blocks is to show that it is `` left `` and each constitute a values ​​of the two audio channels on the right.

The scrambler receives a 28 -byte F2 - word, each byte is delayed by an integer value of 4. The original 28- byte word is thus distributed over 109 bytes to a word F3a.

If during the decoding, for example, a surface length of the error detected in a four - word F3a, it is distributed by the four - Unscrambler F2 frames. Thus, the original surface defect can be treated as four separate error subsequently.

The encoder receives a 28 -byte word that is formed from 28 different F2 - frames, and creates an additional 4 bytes with P parity. A last delay stage processed F3a two frames by the odd bytes are delayed by an amount of one byte. As a result, not more than one symbol per word affect single error, even if two successive symbols of a block are in error. From two F3a frames thus creating two F3 frames. This last interleaving makes it possible to relatively small area can correct errors better. By the delay stage, the disadvantage that, in combination with the clock trouble in the reading out a null word can occur is formed. To prevent this, the P and Q parity symbols are inverted.

Decoder

Since CIRC decoder are not standardized, there are several ways to implement a decoder. hereafter labeled the number of erasure flags that are passed as input.

C1-A decoder

IF syndrome for one or zero error THEN edit one or no symbol corresponding to ELSE sit extinction flags for the entire received word ENDIF

A C2 decoder

IF syndrome for one or zero error THEN edit one or no symbol corresponding to ELSE IF f > 2 THEN copy C2 erasure flags from the C1 erasure flags ELSE IF f = 2 THEN try to correct two erasures ELSE IF f < 2 OR correct two erasures fails THEN sit extinction flags for the entire received word ENDIF

C1-B decoder ( better strategy )

IF syndrome for one or zero error THEN edit one or no symbol corresponding to ELSE IF THEN error syndrome for 2 edit 2 symbols corresponding sit extinction flags for the entire received word ELSE sit extinction flags for the entire received word ENDIF

C2 -B decoder ( better strategy )

IF syndrome for one or zero error THEN edit one or no symbol corresponding to ELSEIF f < = 4 THEN IF syndrome for error 2 AND v = 2 THEN edit 2 symbols corresponding ELSEIF syndrome for error 1 AND f < = 2 THEN edit 3 symbols corresponding ELSEIF syndrome for error 2 AND ( (v = 1 AND f <= 3 ) OR (v = 0 AND f < = 2) ) OR ( f < = 2 AND NOT syndrome for 2 error ) THEN sit extinction flags for the entire received word ELSE copy C2 erasure flags of C1 erasure flags ENDIF ELSE copy C2 erasure flags of C1 erasure flags ENDIF

Example decoding

Suppose the matrix contains 18 columns, each with an error, a column with two penalties, another column with four errors and 11 correct columns. In addition, already an entire column was fitted with extinction flags, because the hardware that part could not recognize.

The columns were measured with a ( 28,24,5 ) - coded code, which means it can correct all 1 -fold and 2 -fold error. The C1 -A decoder uses in contrast to the C1-B decoder is not optimal this possibility. Uses the C1-B decoder can be corrected columns with single and double faults. The column with the dual error is additionally provided with erasure flags. In the column with four errors, two cases may occur. On the one hand this can be recognized and certain extinction flags is set or it is wrong and corrected another error happens.

The rows are encoded with a ( 32,28,5 ) code. If the C1-B decoder to correct the wrong column with four errors encountered by the C2 -B decoder to five incorrect line with one error and two cancellations. If the four errors are detected, the C2 -B decoder has to correct wrong four lines each with three cancellations. In both cases, correct the errors or the cancellation of the right C2 -B decoder. The C2 -A decoder could not correct these errors.

A priori can correct the code as a linear code with every 12 -fold or 24 error cancellations. Through the interaction of row and column error correction 24 and 28 extinctions are corrected in this example. The correction capacity is thus more than tripled.