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

Started by 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
> 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.

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

```