CDROM, F2 Reed-Solomon P Q codes in CIRC encoder

Question

I research info about CDROM principies. In standart http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-130.pdf On page 35(45 in pdf) i see CIRC encoder. And his have Q code, and P codes, who calculated by reed-solomon algoritm. I try to confirm this and doit some sample audio tracks(audio track not used scramber as data track) one fill with 0x01 pattern, and one with 0xA5(CIRC interlive byte in packet not bits, and i see Q and P in F3 frame). After i reed this sector from CD(directly from Laser out) with logic analyzer, and decrypt by script. I have this data for track with pattern 0x01

S1 01 01 01 01 01 01 01 01 01 01 01 01 e5 6e 4e c5 01 01 01 01 01 01 01 01 01 01 01 01 ff ff ff ff

S2 01 01 01 01 01 01 01 01 01 01 01 01 e5 6e 4e c5 01 01 01 01 01 01 01 01 01 01 01 01 ff ff ff ff

First byte is Subcode sumbol in this sample SYNC_1 and SYNC_2

For track with pattern 0xA5

S1 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 6b bc a5 72 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 ff ff ff ff

S1 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 6b bc a5 72 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 ff ff ff ff

If see on CIRC all right 12-15 bytes its inverted Q parity and 28-32 P parity(First byte its sybcode his add at F3).

But i cant find algoritm for calculation this bytes, my maths skills very bad. I try calculator from cdrecord, his doit another codes, try some another Reed-Solomon emplemetation but i cant get identical code from this sample. Where i can get worked implementation of this code.

Audio track not used Q, P in sector, audio not have sectors. Audio write by 24 bytes(6 sample) its F1 frames, and directly go to F2 frame, F2 is CIRC interleaver and his use Q and P. But not same as Q and P for data sector on F1 level. Q 4 byte for 24 bytes frame F1 and P is 4 bytes for F1 interleaved frame plus Q. — Vulcanator
I found a link to edc_ecc.c, which should be helpful. I'll take a look at the code later and see if there's anything I can explain. — rcgldr
In edc_ecc have function encode_L1_Q and encode_L1_P firs doit from 24 bytes 28 byte by add 4 byte of RS code(and add his in between 12-13 originals byte), second doit from 28 bytes 32 byte. Its as CIRC encoder on first and second stage. But value that his calculate not indetical that i read from real cd. I forund this document ece.uvic.ca/~agullive/reedsolomon405-511-2016.pdf and on page 23 description abot algoritm calculation, but i not see reasisation anythere. — Vulcanator
I deleted prior comments since they were about L2. The L1 encode functions implement multiply by alog[( log(data) + log(RS term) ) % 255]. The log of the RS terms are stored in AQ and AP tables, but it appears AQ table is missing entries for AQ[0], AQ[1], AQ[2]. I'll try to figure out what the actual P and Q generator polynomials are later on. There is a tutorial on RS ECC in this NASA pdf file . — rcgldr

rcgldr rcgldr · Accepted Answer · 2019-01-18T11:02:10

I'm putting what I find in this answer as I make progress, based on the edc_ecc.c web github files. RSL12 is GF(2^8), polynomial x^8 + x^4 + x^3 + x^2 + 1 => hex 11d. All non-zero numbers in the field can be considered as powers of hex 02.

The P generator polynomial in hex is:

(x+01)(x+02)(x+04)(x+08) = 01 x^4 + 0f x^3 + 36 x^2 + 78 x + 40

If you look at the 4 entries for AP[...][31], you see the values 75, 249, 78, 6, these are the decimal logs of hex 0f, 36, 78, 40. Note that AP should be AP[4][28] (not [4][32]), the fix is shown below.

Based on your (now deleted) comment, I "uninverted" Q in the examples you gave in the original question, and using my own RS demo program to calculate the P parities, I now get 00 00 00 00:

01 01 01 01 01 01 01 01 01 01 01 01 1a 91 b1 3a 01 01 01 01 01 01 01 01 01 01 01 01 00 00 00 00
a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 94 43 5a 8d a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 00 00 00 00

The Q generator polynomial is the same as the P generator polynomial. It's used for RS(28,24), but the parity bytes are in the middle, so conventional encoding needs to be modified as explained below.

AQ[][] is wrong, using AQ[3][], to get Q[3], I get 69 instead of 3a:

01 01 01 01 01 01 01 01 01 01 01 01 -- -- -- 69 01 01 01 01 01 01 01 01 01 01 01 01

In addition, AQ[0] only has 21 bytes defined, AQ[1] only has 22 bytes defined, AQ[2] only has 23 bytes defined, AQ[3] has 24 bytes defined, but they are apparently wrong.

There is a workaround, use 4 erasure decoding with locations 12 through 15 marked as erasures (the xx xx xx xx) to do the Q encoding:

01 01 01 01 01 01 01 01 01 01 01 01 xx xx xx xx 01 01 01 01 01 01 01 01 01 01 01 01
a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 xx xx xx xx a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5

After the 4 erasure correction, the Q parity bytes are encoded:

01 01 01 01 01 01 01 01 01 01 01 01 1a 91 b1 3a 01 01 01 01 01 01 01 01 01 01 01 01
a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 94 43 5a 8d a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5 a5

Using the 4 erasure decoding method, I generated a fixed AQ[][]:

static const unsigned char AQ[4][24] =
  {{58,152,173,95,88,43,134,205,143,131,163,75,249,66,151,116,125,184,110,16,58,62,137,113},
   {30,214,148,138,112,154,157,96,49,198,189,249,69,47,147,235,156,47,209,183,138,232,205,120},
   {162,244,13,171,213,236,71,177,253,162,59,78,243,180,186,34,78,136,130,85,108,115,178,246},
   {158,179,101,94,49,140,211,149,137,169,81,6,72,157,122,131,190,116,22,64,68,143,119,22}};

However if you plan on writing a decoder (that fixes erasures and/or errors), then you could use the same method I did of using a 4 erasure decode instead of doing a encode. If I recall correctly, this is how some early DAT (digital audio tape) drives implemented this, as they also had their parity bytes in the middle of data.

AP should be AP[4][28]. P is RS(32,28), 28 bytes of data used to generate 4 bytes of parities. The first 4 values from each row of AP[...][32] should be removed, so it becomes AP[4][28], and encode_L1_P() should be encoding 28 bytes of data (a one line fix as noted below).

static const unsigned char AP[4][28] =
  {{249,142,180,197,5,155,153,132,143,244,101,76,102,155,203,104,58,152,173,95,88,43,134,205,143,131,163,75},
   {205,252,218,199,202,41,136,106,119,238,193,103,123,242,83,178,30,214,148,138,112,154,157,96,49,198,189,249},
   {67,11,131,40,7,41,80,147,151,17,245,253,208,66,228,116,162,244,13,171,213,236,71,177,253,162,59,78},
   {148,186,203,11,161,159,138,149,250,107,82,108,161,209,110,64,158,179,101,94,49,140,211,149,137,169,81,6}};

encode_L1_P() needs one line fixed:

static int
encode_L1_P(inout)
    unsigned char inout[L1_RAW + L1_Q + L1_P];
{
    unsigned char *P;
    int i;

    P = inout + L1_RAW + L1_Q;

    memset(P, 0, L1_P);
    for (i = 0; i < L1_RAW + L1_Q; i++) {   /* fix (remove + L1_P) */
        unsigned char data;

        data = inout[i];
        if (data != 0) {
            unsigned char base = rs_l12_log[data];

            P[0] ^= rs_l12_alog[(base+AP[0][i]) % (unsigned)((1 << RS_L12_BITS)-1)];
            P[1] ^= rs_l12_alog[(base+AP[1][i]) % (unsigned)((1 << RS_L12_BITS)-1)];
            P[2] ^= rs_l12_alog[(base+AP[2][i]) % (unsigned)((1 << RS_L12_BITS)-1)];
            P[3] ^= rs_l12_alog[(base+AP[3][i]) % (unsigned)((1 << RS_L12_BITS)-1)];
        }
    }
    return (0);
}

In response to comments. To generate AQ, I used erasure correction to generate 24 sets of parities:

01 00 00 00 00 00 00 00 00 00 00 00 69 60 bf b7 00 00 00 00 00 00 00 00 00 00 00 00
00 01 00 00 00 00 00 00 00 00 00 00 49 f9 fa 4b 00 00 00 00 00 00 00 00 00 00 00 00
...
00 00 00 00 00 00 00 00 00 00 00 00 9e a7 ab 93 00 00 00 00 00 00 00 00 00 00 01 00
00 00 00 00 00 00 00 00 00 00 00 00 1f 3b cf ea 00 00 00 00 00 00 00 00 00 00 00 01

AQ[][ 0] = hex log2{69 60 bf b7} = decimal {058 030 162 158}
AQ[][ 1] = hex log2{49 f9 fa 4b} = decimal {152 214 244 179}
...
AQ[][22] = hex log2{9e a7 ab 93} = decimal {137 205 178 119}
AQ[][23] = hex log2{1f 3b cf ea} = decimal {113 120 246 022}

An alternative method is to use a full length 255 byte codeword all zeroes, except one byte set to 01 at the appropriate position modulo 255, to generate the parities in the standard way, parities = msg * x^4 % generator. This generates parities 16 bytes beyond their target position, so the offset needs to be adjusted by 255-16 = +239 modulo 255 to produce the target parities:

255_byte_message_offset = 28_byte_message_offset + 239 % 255:

msg[239] = 01 => parities = 69 60 bf b7
msg[240] = 01 => parities = 49 f9 fa 4b
...
msg[010] = 01 => parities = 9e a7 ab 93
msg[011] = 01 => parities = 1f 3b cf ea

CDROM, F2 Reed-Solomon P Q codes in CIRC encoder

1 Answers