Forums

Reed-Solomon decoding: Using different gen. polynomials.

Started by Jaco Versfeld February 11, 2005
Hi,

In [1], a decoding algorithm for errors and erasures for Reed-Solomon
codes is briefly stated.  The algorithm uses the Massey-Berlekamp
algorithm to find the error-locators, and Forney's algorithm to find
the values of the errors and erasures.

However, the decoding algorithm is for the Reed-Solomon codes
generated by g(x) = (x - a^1)(x - a^2)...(x - a^[n-k]).  How should I
adapt Forney's algorithm when I want to use the generator polynomial
(x - a^0)(x - a^1)...(x - a^[n-k-1])?

Your time, effort and suggestions will be highly appreciated
Jaco


[1]  S.B. Wicker and V.K. Bhargava, Reed-Solomon codes and their
applications.  New York: Institute of Electrical and Electronic
Engineers, Inc., 1994.
Dear Jaco,
I had a similar problem while writing  a RS decoder a while back.

There are two things that you need to take caree of:
1. Syndrome computation should be modified to compute at roots alpha^i,
i=0..2*t-1.
2. The forney algorithm should be computed using the relation

e(i,j)=[(Xi)^(2-m)]*Omega(1/Xi)/Lambda'(1/Xi)

where m is the lowest root of the RS generator polynomial. I need to
look back at my code to verify that this expression is absolutely
correct [I was succesfully able to get my code to work for arbitrary
start powers of the roots of the gen poly].

Finally, the book "The Art of Error correction coding" by Robert
Morelos Zaragoza has some very relavent information in this very topic.
Hope that helps,
Vikram

"Jaco Versfeld" <jaco_versfeld@hotmail.com> asked in message 
news:e48813da.0502102140.21ec1f3a@posting.google.com...
> How should I > adapt Forney's algorithm when I want to use the generator polynomial > (x - a^0)(x - a^1)...(x - a^[n-k-1])?
See Equation (7) in http://www.ifp.uiuc.edu/~sarwate/decoder.ps
Thank you very much for the help.
Jaco