- Reed-Solomon Codes

For compact discs, Reed-Solomon codes are used and the algorithm is known as the Cross-Interleave Reed-Solomon code (CIRC). Reed-Solomon codes exclusively use polynomials derived using finite field mathematic known as Galois Field to encode and decode block data. Either multiplication or addition can be used to combine elements, and the result of adding or multiplying two elements is always a third element contained in the field. In addition, there exists at least one element called a primitive such that every other element can be expressed as a power of this element.

The size of the Galois Field, which determine the number of symbols in the code, is based on the number of bits comprising a symbol; 8-bit symbols are commonly used. A primitive polynomial often used in GF (28) systems is x^8+x^4+x^3+x^2+1.

The code can use the input word to generate two types of parity, P and Q. The P parity can be a modulo 2 sum of the symbols. The Q parity multiplies each input word by a different power of the GF primitive element. If one symbol is erroneous, the P parity gives a nonzero syndrome S1. The Q parity yields a syndrome S2. By checking this relationship between S1 and S2, the RS code can locate the error. Correction is performed by adding S1 to the designated location.

Reed-Solomon codes are used for error correction in the compact disc, DAT, DVD, direct broadcast satellite, digital radio and digital television applications. Read more about Reed-Solomon Code over here.

- Cross-Interleave Reed Solomon Code

The particular error correction code used in the CD system is called the Cross Interleave Reed-Solomon Code, or CIRC, followed by EFM.

CIRC (Cross Interleaved Reed-Solomon Code) is the error detection and correction technique used on a CD (and on DVD for that matter). It is a variant of the more general BNC codes. These codes are actually Bytes added during premastering or recording to the normal data bytes for achieving error free reading of a disc. The CIRC bytes are present in all CD modes (audio and data alike). The whole error correction method that makes use of these added CIRC bytes is commonly referred to as the CIRC based algorithm.

While the laser head reads the bits out of the disk surface introducing one erroneous bit out of 10^-6, the basic level of error correction provided for the Audio CD by CIRC results to only one unrecoverable bit out of every 10^-9 bits read! CD-ROM provides additional protection for data (ECC/EDC), the so-called layer 3 (L3) error correction, reducing this error rate to just one bit out of 10^-12 bits!

Let's see how this is important. One data bit corresponds to 3.0625 so-called "channel bits". These are the ones that are actually recorded onto a disc surface. A whole disk is 333,000 sectors long. Each sector contains 2,048 data bytes. By performing the necessary simple arithmetic calculations, we can easily see that every data disk would be unreadable without the implementation of both the above error correcting codes.

CIRC corrects error bursts up to 3,500 bits (2.4 mm in length) and compensates for error bursts up to 12,000 bits (8.5 mm) such as caused by minor scratches.

The CIRC is designed such that the C1 code corrects most of the random errors and C2 code corrects most of the burst errors. The interleaver between the C1 and C2 codes is performed to make it easier for the C2 Reed-Solomon code to correct burst errors. Interleaving also protects against burst errors appearing in the Audio steam: A long burst due to a failed C2 creates short audio errors.

For a detailed explanation of the CIRC you can read the ECMA 130 standard.