Forums

Reed Solomon decoding for arbitrary primitive elements in GF(2^m)

Started by Unknown July 26, 2005
Hello

I wish to know how to implement RS decoding for any arbitrary primitive
element in GF(2^m). Most literature covers decoding assuming that the
primitive element is of the form alpha^1.

In the CCSDS standard, the RS(255,239) code employs a generator
polynomial of the form:

g(x)=(x-A^120)(x-A^121)...(x-A^135)
where A=alpha^11 is a primitive element in GF(255)

[other valid primitive elements are of the form alpha^q where
GCD(q,255)=1].

For decoding such a code based on the primitive element alpha^11, how
do I modify the Berlekamp massey/Forney algorithm...

Any pointers to papers/textbooks would also be greatly appreciated.
Regards
Vikram

PS: For a start, I have derived that the error magnitudes based on the
Forney algorithm are given as:

e(k)=X(k)^(2-B)* Omega[X(k)^-1]
                 --------------
                 Lambda'[X(k)^-1]

where Omega(x) is the error magnitude polynomial, Lambda(x) is the
error location polynomial, and X(k)=A^k represents the inverse of root
of the error locator polynomial Lambda(x) and A is the primitive
element in GF(2^m). Finally B denotes the exponent of the start root of
the RS generator polynomial i.e. 120 in the above example.

<cvikram@mac.com> wrote in message 
news:1122419351.668937.210420@z14g2000cwz.googlegroups.com...
> Hello > > I wish to know how to implement RS decoding for any arbitrary primitive > element in GF(2^m). Most literature covers decoding assuming that the > primitive element is of the form alpha^1. > > In the CCSDS standard, the RS(255,239) code employs a generator > polynomial of the form: > > g(x)=(x-A^120)(x-A^121)...(x-A^135) > where A=alpha^11 is a primitive element in GF(255)
> For decoding such a code based on the primitive element alpha^11, how > do I modify the Berlekamp massey/Forney algorithm...
No modification of the Berlekamp-Massey algorithm is needed. The Forney algorithm uses an additional factor, as you discovered for yourself.
> Any pointers to papers/textbooks would also be greatly appreciated.
Ask Google to search for Sarwate+Shanbhag+Reed-Solomon
> PS: For a start, I have derived that the error magnitudes based on the > Forney algorithm are given as: > > e(k)=X(k)^(2-B)* Omega[X(k)^-1] > -------------- > Lambda'[X(k)^-1] > > where Omega(x) is the error magnitude polynomial, Lambda(x) is the > error location polynomial, and X(k)=A^k represents the inverse of root > of the error locator polynomial Lambda(x) and A is the primitive > element in GF(2^m). Finally B denotes the exponent of the start root of > the RS generator polynomial i.e. 120 in the above example.
Check your work; the exponent 2-B might be off by one (1-B instead of 2-B).