MATH 392 -- Seminar in Coding Theory

Reed-Solomon decoding example

April 19, 2002

First, read in a package of coding theory Maple procedures. (These

can be downloaded from the course homepage for your future use, if you like.)

> read "/home/fac/little/public_html/SemCodTh/CTPMaple6.map";

Warning, the protected names norm and trace have been redefined and unprotected

We will work an example with the code RS( ) -- a Reed-Solomon code

over with . To construct the field we need an

irreducible polynomial of degree 6 whose roots are primitive elements. To

find an appropriate one, we can factor in [ x ]

> Factor(x^63+1) mod 2;

Check primitivity:

> alias(alpha=RootOf(z^6+z^5+1));

> h:=z^6+z^5+1;

> for i from 0 to 63 do if (Normal(alpha^i) mod 2) = 1 then lprint(i); end if; end do;

0

63

The powers of give all 63 nonzero elements of the field, so this is our primitive element.

The Reed-Solomon generator polynomial (using in general formula) -- this is

the expanded form of the product (with like terms collected):

> gp:=RSGenPoly(2,6,25,0,h,x);

Next, we'll enerate a random codeword by encoding a particular vector of information symbols. The

procedure RSEncode uses the polynomial division encoder we talked about in class:

> infosyms:=vector([seq(alpha^i,i=1..64-25)]):

> codeword:=RSEncode(infosyms,gp,x,h,2);

A random error vector -- weight is 8 ( < t = 12 for this code)

> errorvector:=vector([1,0,0,0,alpha,0,0,0,0,0,0,0,0,alpha^43,0,0,0,0,0,0,1,

> calpha^7,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,alpha^6,0,0,0,0,0,0,0,0,0,0,0,0,0,1,alpha^11,0,0,0]);

> vectdim(errorvector);

> received:=map(y->Normal(y) mod 2,matadd(codeword,errorvector)):

> st:=time():

> decoded:=RSBMDecode(received,2,h,25,0);

> time() - st;

> for i to 63 do if codeword[i] <> decoded[i] then lprint(i,codeword[i],decoded[i]) end if end do;

(no output so correctly decoded!)

Note: The decoding took about 12 seconds in Maple. In fact, it is true in general

that Maple is relatively slow for this type of procedure (its programming language

is interpreted vs. compiled, and it is not optimized for finite field arithmetic

the way "professional" coding theory software would be.)

On the other hand, consider the job of constructing the SDA for this code and

looking up an error syndrome to find the coset leaders.

There are = approx = 2 x different cosets. If you could compute

a billion ( = ) coset leaders per second (not likely!), just constructing the SDA would

take 2 x seconds approx = 6 x years, or longer than the total age of the universe!

It would take more than 7 x gigabytes to store all that information (a HUGE

amount -- immensely more than all the computer memory in the world now -- more

than is conceivable any time in the forseeable future).

And even assuming we could store all that information somehow, we would still need

some way to retrieve leaders from the SDA -- not a trivial task with that much info.

12 seconds to decode a received word doesn't look so bad any more, does it!

> evalf(2^144*6*63/(2^30));

> evalf(2*10^34/(60*60*24*365));

>