Forums

Reed Solomon decoder -help

Started by Zeph80 December 4, 2007
This is the first time Ive implemented a Reed Solomon decoder, and Im
having some strange problems , which I have not been able to debug.
Ive implemented a RS(255,191) code. That makes it a lil hard to verify all
steps of my C code by calculations on paper. Anyways, Ive tried Euclids and
Berlekamp in C, I always get the correct error locations, but my magnitudes
are not correct. 
  If my Error locator polynomial is correct, then my magnitude should be
correct too,(with Euclid, magnitude poly is also available at the end of
calculations, I have also verified by calculating magnitude polynomial
from error locator poly using (1 + S(x) )(error locator poly) mod x^(2t
+1)).

I even calculated Forney , on paper, since I thought if error locations
are correct, the error must be in the next step.I get an incorrect answer
even on paper.

Any suggestions, on where to debug.Error locations are the roots of the
error locator polynomial, so is it possible I get the first step correct
answer because Im using some multiple of error locator polynomial.
Are you using the correct Forney formula?  There
are different formulas depending on the sequence of
roots of the generator polynomial.  See, for example,
http://www.ifp.uiuc.edu/~sarwate/decoder.ps
Your "wrong" error magnitude Z might just be
equal to the correct error magnitude Y times X^i
where X is the error location at which the error
magnitude is Y.

--Dilip Sarwate

"Zeph80" <surabhi_talwar@hotmail.com> wrote in message 
news:7a6dncj7X75T5cjanZ2dnUVZ_tWtnZ2d@giganews.com...
> This is the first time Ive implemented a Reed Solomon decoder, and Im > having some strange problems , which I have not been able to debug. > Ive implemented a RS(255,191) code. That makes it a lil hard to verify all > steps of my C code by calculations on paper. Anyways, Ive tried Euclids > and > Berlekamp in C, I always get the correct error locations, but my > magnitudes > are not correct. > If my Error locator polynomial is correct, then my magnitude should be > correct too,(with Euclid, magnitude poly is also available at the end of > calculations, I have also verified by calculating magnitude polynomial > from error locator poly using (1 + S(x) )(error locator poly) mod x^(2t > +1)). > > I even calculated Forney , on paper, since I thought if error locations > are correct, the error must be in the next step.I get an incorrect answer > even on paper. > > Any suggestions, on where to debug.Error locations are the roots of the > error locator polynomial, so is it possible I get the first step correct > answer because Im using some multiple of error locator polynomial.
>Are you using the correct Forney formula? There >are different formulas depending on the sequence of >roots of the generator polynomial. See, for example, >http://www.ifp.uiuc.edu/~sarwate/decoder.ps >Your "wrong" error magnitude Z might just be >equal to the correct error magnitude Y times X^i >where X is the error location at which the error >magnitude is Y. > >--Dilip Sarwate > >"Zeph80" <surabhi_talwar@hotmail.com> wrote in message >news:7a6dncj7X75T5cjanZ2dnUVZ_tWtnZ2d@giganews.com... >> This is the first time Ive implemented a Reed Solomon decoder, and Im >> having some strange problems , which I have not been able to debug. >> Ive implemented a RS(255,191) code. That makes it a lil hard to verify
all
>> steps of my C code by calculations on paper. Anyways, Ive tried Euclids
>> and >> Berlekamp in C, I always get the correct error locations, but my >> magnitudes >> are not correct. >> If my Error locator polynomial is correct, then my magnitude should
be
>> correct too,(with Euclid, magnitude poly is also available at the end
of
>> calculations, I have also verified by calculating magnitude polynomial >> from error locator poly using (1 + S(x) )(error locator poly) mod
x^(2t
>> +1)). >> >> I even calculated Forney , on paper, since I thought if error
locations
>> are correct, the error must be in the next step.I get an incorrect
answer
>> even on paper. >> >> Any suggestions, on where to debug.Error locations are the roots of
the
>> error locator polynomial, so is it possible I get the first step
correct
>> answer because Im using some multiple of error locator polynomial.
Well, I was not accounting for all even powers in the derivative for Forney's equation. Silly mistake which i didn't catch because for less than 3 errors my code always worked. And that would work, because with 2 errors, the derivative of error locator polynomial would be just one value with power 0.
> > >
Hi,

If you have some experience with C++, you can use my RS library to
generate test vectors (parities, correction locations and magnitudes),
also print out the values of each step trivially - might help in
debugging
your own implementation. The library is scalled Schifra and can be
downloaded from: www.schifra.com



Arash Partow
__________________________________________________
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
http://www.partow.net