Cross-interleaved Reed–Solomon coding

Cross-interleaved Reed–Solomon coding. It is a powerful error correction code scheme that combines two Reed–Solomon codes with a specific data interleaving technique. Developed primarily for the Compact Disc Digital Audio format, the system was designed to correct burst errors caused by physical damage like scratches or dust. The method's robustness made it a cornerstone technology for consumer digital audio and influenced subsequent optical storage formats.

● Overview

The code was invented by Kees A. Schouhamer Immink during the development of the Philips and Sony Compact Disc Digital Audio standard in the late 1970s. It is a specific type of concatenated code where an outer Reed–Solomon code and an inner Reed–Solomon code are linked by a convolutional interleaver. This structure is particularly effective against both random errors and long burst errors, which are common on media such as optical discs. The design was critical to achieving the high fidelity required for consumer digital audio, as endorsed by artists like Herbert von Karajan. The implementation details were standardized in the Red Book (CD standard) published by Philips and Sony.

● Encoding process

The encoding process begins with the audio data frame, which is first encoded by the outer Reed–Solomon code, known as C2. This generates parity symbols that are added to the original data block. The output from C2 is then passed through a cross-interleaver, which scrambles the symbol order according to a defined delay pattern. This interleaved sequence is subsequently encoded by the inner Reed–Solomon code, called C1, which adds further parity. The final encoded frame includes the interleaved data and the parity symbols from both CIRC stages. This entire process was meticulously implemented in early CD player hardware from manufacturers like Denon and Technics.

● Decoding and error correction

During playback in a device like a Sony Discman, the decoder performs the inverse operations. The inner C1 decoder first attempts to correct errors. Its output is de-interleaved, which spreads any remaining uncorrected burst errors across multiple code words. These are then presented to the outer C2 decoder, which can correct the now-dispersed errors. The system employs sophisticated erasure correction techniques, where the C1 decoder can flag unreliable symbols for the C2 decoder. This two-stage approach, combined with interleaving (data), allows CIRC to correct error bursts up to 3,500 bits long, a capability demonstrated in products from Pioneer Corporation and JVC.

● Applications

The primary and most famous application is in the Compact Disc Digital Audio format, as defined by the Red Book (CD standard). Its success led to adoption in the CD-ROM format described in the Yellow Book (CD standard) and the CD-i format from Philips. The underlying principles influenced the error correction systems in later optical media, including the MiniDisc format by Sony and the DVD format standardized by the DVD Forum. While largely superseded by more powerful codes like Reed–Solomon product code in Blu-ray Disc, its legacy is foundational to consumer digital media.

● Advantages and limitations

A key advantage is its exceptional performance against long burst errors caused by scratches on a CD, a common issue in consumer use. The combination of concatenated code structure and interleaving (data) provides a high level of reliability with relatively low overhead. However, its fixed structure is less flexible than modern iterative codes like Turbo code or Low-density parity-check code. The coding gain, while sufficient for CD audio, is outperformed by codes used in modern systems like the Digital Video Broadcasting standards or deep-space probes from NASA.

● Variants and related codes

The basic CIRC concept inspired several related schemes. A notable variant is the Reed–Solomon product code (RS-PC) used in the DVD format, which employs a two-dimensional array. The Advanced Intelligent Tape format by Sony used a similar interleaved Reed–Solomon code approach. Later optical formats, like the MMCD proposal from Philips and the final DVD standard, evolved the principles into more complex product codes. Modern successors include the powerful Bose–Chaudhuri–Hocquenghem code and Reed–Solomon code combinations found in contemporary flash memory controllers from companies like Samsung and Toshiba.

Category:Error detection and correction Category:Computer storage