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.

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

Started by ●July 26, 2005

Reply by ●July 28, 20052005-07-28

<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).