Calculating parity bytes

Ive been attending this class, just havent raised my hand;)
I bought the book you suggested in another thread a while back “A first course in coding theory” and have to admit its quite execellent. I just want to suggest to Ipse to get that book because it explains everyhting thats been said here in the first 3 chapters. And it assumes only a high school level of math with the reader from the start so its real easy to understand.

Well spath, you are right about that. Having never worked in the field before, I can only imagine how hard it is. This new company is not funded yet (it probably never will be), so there is actually no one on the team at this point. But, if and when it does get funded, we will be looking for many such experienced people in this “odd field”. If you are (or you know of) such an expert, there might be an opportunity for you or them in Orange County, California soon.
Let me know and we’ll talk.

Hi Anthony,

Did you already contact such experts to ask for a feasibility study ?
Discs have been built specifically to be burned in the way they are
now, so you’d better first make sure that your idea has a chance
to work before starting the big journey. Once this is done, you should
know which parts you need to build your machine, thus which kind of
expertise you need. For a complete drive you would need people for digital
and analog electronics, automatism, signal processing, electromechanics,
optics, and a bunch of firmware coders.

Unfortunately I don’t know of available experts in the US at the moment,
and it’s out of the question for me to go back there as long as I have to
give out my fingerprints.

–spath

Hey Reddish,

Ive been playing with the source and was wondering if you can explain why this parity calculation works, its different from what youve done.


;-----
	for(i=1;i<frames;i++)
	{
		z_index=0;
		for(hp_row=0;hp_row<4;hp_row++)
		{
		z=0;
		p_delay=0;
			for(j=0;j<32;j++)
			{
			z=data[i-p_delay][j]^invert[j]^Product(z,2);
			p_delay^=1;
			}
		z_list[z_index++]=z;
		if(z!=0)
			printf("Perr->frame:%i,hp_row:%i,z:%02X
",hp_row,i,z);
		}
	}
;-----
instead of 
;-----
			hplog=hp_row*(31-j);
			hp=ALog[hplog];
			z=z^Product(hp,data[i-p_delay][j]^invert[j]);

in the inner loop.
;-----

I was looking through some reed solomon source code and noticed there syndrome calculation had less lookups into the log tables and was wondering why that shortcut works.

Ive been working on error correcting and the
only algorithm Ive found is “Berlekamp Massey” that requires you to know which codewords are in error. If in the EFM decoder you get a 14 bit code thats not in the table then you can flag it and use that in the equation which boils down to a sum of products equal to zero and just solve for the unknown. But if a codeword changed enough bits and it turned into another valid EFM codeword, then the only way I see now is to brute force check. I know the answer is in Hills book just havent read enough, theres lot to chew on in there;)

Ok. let’s say d[j] = data[i-p_delay[j]][j]^invert[j] for now (both laser2wav and the code you show agree on that).

Now I think you will agree that what laser2wav calculates is ("**" denotes exponentiation):


            31                                    
z[hp_row] = SUM d[j] * alpha ** (hp_row*(31-j)) = 
            j=0            

 d[0] * alpha ** (hp_row*31) + d[1] * alpha ** (hp_row*30) + ... + d[30] * alpha ** hp_row + d[31]
            
            

This is just a polynomial evaluation; it is possible to bring this in Horner form to get rid of the exponentiation (http://mathworld.wolfram.com/HornersRule.html) - try it. By evaluating it in that way, this will take you to something that is very close to the code sample you gave, except for the fact that I am missing an hp_row, on first sight… I will check later.

Regards, Sidney

I just want to suggest to Ipse to get that book because it explains everyhting thats been said here in the first 3 chapters. And it assumes only a high school level of math with the reader from the start so its real easy to understand.
Thank you, such books are very rare in my place (always have to import everything), there’s only one posgraduate course in whole country that covers this stuff, and the professor and his few students weren’t able to help. Sidney’s code and help with GF have been critical to me, as this guy’s key introduction to RS: http://www.informit.com/authors/bio.asp?a=33da8471-9fa5-4b9a-a70a-aab5bbbd7357

Encoding soon! :smiley:

Arranged LFSR for

g(X) = α^3 + α^1 X + α^0 X^2 + α^3 X^3 + X^4

from form

g(X) = (X - α )(X - α^2)(X - α^3)(X - α^4)

for RS (32, 28), didn’t work, checked config and seems faithful, wrong poly?

Thanks a lot.

Obviously… Forgive me.

An (n, k) Reed-Solomon code is constructed by forming the code generator polynomial g(x), consisting of n-k=2t factors, the roots of which are consecutive elements of the Galois field. Choosing consecutive elements ensures the distance properties of the code are maximised. Thus the code generator polynomial takes the form:

g(x) = (x+α^b)(x+α^b+1)…(x+α^b+2t-1)

It should be noted that this expression is often quoted in the literature with subtle variations to catch the unwary. For example, the factors are often written as (x - α^i), which emhasises that g(x) = 0 when X = α^i and those familiar with Galois fields realise that - α^i is exactly the same as α^i. Also, some choose roots starting with α^0 (b=0 in equation), while many others start with α, the primitive element (b=1 in equation). While each is valid, it results in a completely different code requiring changes in both the coder and decoder operation.
What is then the g(x) for RS on CD?

  1. Let C1 denote the (28, 24) code and let C2 denote the (32, 28) code
  2. Let α be a primitive root of p(x) = x^8 +x^4 +x^3 +x^2 +1. Then the generator for both the (28, 24)
    and the (32, 28) code is given by

g(x) = (x + α )(x + α^2)(x + α^3)(x + α^4)
Seems instructors at EPFL mistaken CIRC stages, should we trust they gave the right g(x)?

Please, somebody help. :sad:

:cool: Ok guys, I’m RS encoding (finally!)…

The roots of generator polynomial must also be the roots of the codeword generated by itself, because a valid codeword is U(x) = m(x) g(x), therefore an arbitrary codeword must yield 0 when evaluated at any root of g(x).

Clues to right g(x) are on Hp and Hq parity check matrices I posted (they proven to work with real life CD codewords inside Sidney’s laser2wav), which test the codeword multiplying it by 1, α, α^2 and a^3 (mistake was Dr. Sklar’s solution was over a different GF, for wrong EPFL factors, BTW), conclusion is DIYC (Do It Yourself Carefully!), result:

g(x) = x^4 + α^75 x^3 + α^249 x^2 + α^78 x^1 + α^6

So (for who don’t know him) say hello to Mr. CD C1/C2 RSC LFSR HW encoder on attachment, whose ‘software’ version is available in a MS XLS format bundle (bonus parity checker) via IMS (PM me). Would kind webspace owner upload 36 KB ARJ to page/site?

I’ll always thank Mr. Sidney Cadot. :slight_smile:


Parity checker packed with encoder became syndrome calculator for decoder under advanced construction, has also now direct method (matrices) RS decoding algorithm that determines error locator polynomial input to Chien search brute force stage that returns error locations.

Only thing left is error evaluation and maybe the interesting erasure processing. :smiley:

Ive been working on error correcting and the
only algorithm Ive found is “Berlekamp Massey”
There are also: direct, Peterson and Euclid algorithms. I’ll try give you a list of useful docs on the net. :slight_smile:

[QUOTE=IpseDixit;931291]g(x) = x^4 + α^75 x^3 + α^249 x^2 + α^78 x^1 + α^6

So (for who don’t know him) say hello to Mr. CD C1/C2 RSC LFSR HW encoder on attachment, whose ‘software’ version is available in a MS XLS format bundle (bonus parity checker) via IMS (PM me). Would kind webspace owner upload 36 KB ARJ to page/site?

I’ll always thank Mr. Sidney Cadot. :)[/QUOTE]
Great, but ops, just to point out some mistakes to you ;)…

Your LFSR (Linear Feedback Shift Register) diagram will only generate (low level Red book CIRC) C1 parity bytes and cannot do so for C2 parity bytes that goes in the correct place.

Also, in your diagram the values are wrong, you’ve put in powers 6, 78, 249, and 75 - instead they should be the coefficients: a^6, a^78, a^249 and a^75 (which are really values 64, 120, 54 and 15) in the diagram.

For those who don’t know: a LFSR (really just a shift register with operations) configuration can be used to generate (encode) parity bytes. You can directly write a code that implements that quite easily. :slight_smile:

You will probably think of why not for C2? :eek:

Although the code word generator g(x) polynomial (the one you posted) is the same for both C1 and C2 you’d think that they would be generated in exactly the same way, answer is not quite - in fact you can see the problem in the CD interleaving diagram that you’ve posted in another thread:

http://club.cdfreaks.com/f52/offsets-handling-syncing-audio-data-vs-q-channel-111913/index3.html#post1693090

Regular systematic parities are calculated to be appended at the end of input data and that is what the LFSR encoder will generate. But for C2 it is non regular, i.e. it isn’t appended at the end.

In the interleaving diagram you can see that an arrow showing 28 input bytes will generate 4 bytes of C1 parities, and are appended to the end - this is fine. But for the 4 bytes of C2 parities, you can see that it is not appended to the end, and you can also see there are 2 separate arrows of 12 bytes of input data in both directions.

Wouldn’t it be better if you white coats could explain how you got that and preferably in a language for us normal citizens or those blonde types. :slight_smile:

Oki, I’ll show it:

As you’ve nicely posted, this is the code word generator polynomial for C1/C2 for Red book low level Reed Solomon (RS) code:
g(x) = (x + α )(x + α^2)(x + α^3)(x + α^4)

LFSR encoder requires the coefficient values of the expanded form, so we need to apply plain algebra maths for this, i.e. multiply out brackets and collect like terms, but using Galois Field: GF(2^8) over the primitive polynomial arithmetic, and one of which we need here is xor for adding coefficient values:

Obtaining the code word generator polynomial (where a = primitive element of the Galois Field in question):

        g(x) = (x+a^0)(x+a^1)(x+a^2)(x+a^3)

(1)
Let's do first half (multiply out brackets and collect like terms):
        g(x) = (x+a^0)(x+a^1)
             = x*x + a^1*x + a^0*x + a^0*a^1  (multiplied out)
             = x^2 + (a^0+a^1)*x + a^0*a^1    (collect like terms)
             = x^2 + (a^0+a^1)*x + a^1        (a^0 = 1)

(2)
Now we do the other half (multiply out brackets and collect like terms):
        g(x) = (x+a^0)(x+a^1)(x+a^2)(x+a^3)
             = (x^2 + (a^0+a^1)*x + a^1)(x+a^2)(x+a^3)   (expression from 1 and 2nd half)
             = (x^3 + (a^0+a^1)*x^2 + a^1*x + a^2*x^2 + (a^2+a^3)*x + a^3)(x+a^3)   (multiplied out)
             = (x^3 + (a^0+a^1+a^2)*x^2 + (a^1+a^2+a^3)*x + a^3)(x+a^3)    (collect like terms)
             = x^4 + (a^0+a^1+a^2)*x^3 + (a^1+a^2+a^3)*x^2 + a^3*x + a^3*x^3 + (a^3+a^4+a^5)*x^2 + (a^4+a^5+a^6)*x + a^6   (multiplied out)
             = x^4 + (a^0+a^1+a^2+a^3)*x^3 + (a^1+a^2+(1+1)a^3+a^4+a^5)*x^2 + (a^3+a^4+a^5+a^6)*x + a^6   (collect like terms)
             = x^4 + (a^0+a^1+a^2+a^3)*x^3 + (a^1+a^2+a^4+a^5)*x^2 + (a^3+a^4+a^5+a^6)*x + a^6   (remove (1+1)a^3 because 1 xor 1 = 0)

Since we know a = 2 we then have the final form as:
        g(x) = x^4 + 15x^3 + 54x^2 + 120x + 64

So the coefficient values are 1, 15, 54, 120 and 64. Note coefficent 1 is not required for the LFSR calculation.

Although not needed, ouch, how did you arrive at the following equivalent forms: a^75, a^249, a^78 and a^6 values?

Hehe, I bet via naughty way… all you do is look up the power table of a^i from GF(2^8) over the primitive polynomial. Saving us time, Sidney’s source code galois.h contains the already calculated power table for the GF we’re looking at:

const unsigned char alpha_power_table[255] =
{
    1,   2,   4,   8,  16,  32,  64, 128,  29,  58, 116, 232, 205, 135,  19,  38,
   76, 152,  45,  90, 180, 117, 234, 201, 143,   3,   6,  12,  24,  48,  96, 192,
  157,  39,  78, 156,  37,  74, 148,  53, 106, 212, 181, 119, 238, 193, 159,  35,
   70, 140,   5,  10,  20,  40,  80, 160,  93, 186, 105, 210, 185, 111, 222, 161,
   95, 190,  97, 194, 153,  47,  94, 188, 101, 202, 137,  15,  30,  60, 120, 240,
  253, 231, 211, 187, 107, 214, 177, 127, 254, 225, 223, 163,  91, 182, 113, 226,
  217, 175,  67, 134,  17,  34,  68, 136,  13,  26,  52, 104, 208, 189, 103, 206,
  129,  31,  62, 124, 248, 237, 199, 147,  59, 118, 236, 197, 151,  51, 102, 204,
  133,  23,  46,  92, 184, 109, 218, 169,  79, 158,  33,  66, 132,  21,  42,  84,
  168,  77, 154,  41,  82, 164,  85, 170,  73, 146,  57, 114, 228, 213, 183, 115,
  230, 209, 191,  99, 198, 145,  63, 126, 252, 229, 215, 179, 123, 246, 241, 255,
  227, 219, 171,  75, 150,  49,  98, 196, 149,  55, 110, 220, 165,  87, 174,  65,
  130,  25,  50, 100, 200, 141,   7,  14,  28,  56, 112, 224, 221, 167,  83, 166,
   81, 162,  89, 178, 121, 242, 249, 239, 195, 155,  43,  86, 172,  69, 138,   9,
   18,  36,  72, 144,  61, 122, 244, 245, 247, 243, 251, 235, 203, 139,  11,  22,
   44,  88, 176, 125, 250, 233, 207, 131,  27,  54, 108, 216, 173,  71, 142
};

Now you lookup the coefficient values in that table, and their index position in the array is the index i of a^i of the GF we’re looking at:
15, 54, 120 and 64

You’ll get positions:
75, 249, 78 and 6

Which corresponds to:
a^75, a^249, a^78 and a^6

Now where’s my rain coat…