M2-SCCI Coding; Class project: CIRC Coder/Decoder

Topic:  Implementing the Cross Interleaved Reed-Solomon Code of the audio CD.

Students have to write 4 programs: For the tests, we provide a noise generator. It introduces errors on the encoded file in order to emulate, scratches, dusts, etc, of 2 kind: Downloading the noise generator (in C) : noise-generator.tgz
Then, decompressing and help is obtain by: $ tar xvfz noise-generator.tgz ; cat noise-generator/ReadMe
The noise generator has the following specification: Usage : 
$  bruiteur -p 0.01 -f 0.001 - l 100  < input_file > output_file

and to use it with the encoding/decoding:
$ CIRC_coding < test_file    |    noise-generator -p 0.01 -f 0.001 -l 100  |  CIRC_decoding  > output_file;
To test: use the program "diffbinfiles" comparing 2 binary files
          $ diffbinfiles  file1 file2
NB : you are free to modify/improve the noise-generator and adapt it to your experimenations by adding new options for example. But you have to leave the existing options unchanged (they will be used for the tests).

Work assignment (in groups of 2 students):

Informations on how to create a CIRC coder/decoder

Below are usefull informations: base field, generating matrices for the codes, taken from [1]. Additional material can be found in [3]. Encoding. The audio signal is split into frames of 6 samples of 4 bytes each (un sample has 32 bits). It corresponds to a stereo signal, with 16 bits on the left and 16 bits channel on the right channel). The CIRC encoding encodes these 24 bytes by 32 bytes, using two truncated Reed-Solomon: C1 and C2 (cf generating matrices for the codes C1 and C2 ) in the following way. Each block of 24 byte is first encoded using C1 to form words of 28 bytes that place in an interleaving table with a delay of 4 and a depth of 28 (i.e., 28 rows). Two consecutive symbols of a same code word C1 are spaced one from each other by 1 row and 4 columns (cf Figure 1). The · are arbitrary symbols symboles quelconques (we usually use 0). In practice on an audio CD, this table has more than 100 million of columns. Each column of 28 byte is then encoded using C2 to form a byte table of 32 rows (cf Figure 2). The encoded file is then obtained by reading this table column-wise (second interleaving).



Figure 1: Interleaving table of delay 4 and depth 8



Figure 2: Diagram of the coding

Decoding . the decoding of table in Figure 2 is first done column-wise, using a decoder for C2 correcting 1 error. If the column is not a word in C2 and the correction fail, the 28 symbols returned by the decoder are marked as erased. From the 109-ith decoded column, we begin to decode the diagonals (with delay 4), using a decoder for C1 fixing 4 erasing or less. In particular, this implies that the decoder of C1 will also receive the positions of erasing, together with the word to be decoded.


Références. This project is directly inspired by a project from Nicolas Sendrier [1]. The report [2] gives a more detailed description of the audio CD encoding. The page [3] enumerates several C/C++ programs for coding/decoding.