Forums

Galois fields and Reed-Solomon codes?

Started by Jaco Versfeld November 11, 2004
Hi,

I have worked a bit on Reed-Solomon codes over GF(2^m).

However, a co-student of mine asked me to help him with a Reed-Solomon
code over GF(3^2).

I have two questions:
How do I construct the field GF(3^2)?  With a GF(2^m) field it is
quite easy.  You derive the field using a primitive binary polynomial
of degree m.  Also, how do I perform addition and multiplication?

My second question:  I used Matlab to construct a GF(3^2) field, and
constructed a polynomial consisting of all the nonzero elements of the
field as roots.  The result that I got was a polynomial with only two
nonzero coefficients, at x^0 and x^n.  However, with GF(2^m), both
coefficients would be the unity element, indicating that all
Reed-Solomon codes would be cyclic.  In this case for the specific
GF(3^2), the coefficient of x^0 was not the unity element.  Does this
indicate that for this specific GF(9), I will not be able to construct
a cyclic Reed-Solomon code?

Thank you very much
Jaco
Jaco Versfeld wrote:

> Hi, > > I have worked a bit on Reed-Solomon codes over GF(2^m). > > However, a co-student of mine asked me to help him with a Reed-Solomon > code over GF(3^2). > > I have two questions: > How do I construct the field GF(3^2)? With a GF(2^m) field it is > quite easy. You derive the field using a primitive binary polynomial > of degree m. Also, how do I perform addition and multiplication? > > My second question: I used Matlab to construct a GF(3^2) field, and > constructed a polynomial consisting of all the nonzero elements of the > field as roots. The result that I got was a polynomial with only two > nonzero coefficients, at x^0 and x^n. However, with GF(2^m), both > coefficients would be the unity element, indicating that all > Reed-Solomon codes would be cyclic. In this case for the specific > GF(3^2), the coefficient of x^0 was not the unity element. Does this > indicate that for this specific GF(9), I will not be able to construct > a cyclic Reed-Solomon code? > > Thank you very much > Jaco
From Clark & Cain, "Error-Correction Coding for Digital Communications", Plenum 1981, page 64: "If q is a power of a prime number (say q = p^m), then the field elements are all possible polynomials of degree m-1 where the coefficients are from the prime field GF(p)..." Basically you do the same thing as you do over GF(2): you do all addition & multiplication modulo 3, you take care of subtraction and division by using the inverses, etc. I felt that book does a very good job of explaining the concept (it must have -- I've never used GF(n != 2) codes, yet I remembered what to do and where to find it!). -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
"Tim Wescott" <tim@wescottnospamdesign.com> wrote in message
news:10p74lgg9ksjn43@corp.supernews.com...
>> > Basically you do the same thing as you do over GF(2): you do all > addition & multiplication modulo 3, you take care of subtraction and > division by using the inverses, etc. > > I felt that book does a very good job of explaining the concept (it must > have -- I've never used GF(n != 2) codes, yet I remembered what to do > and where to find it!). > > --
Hello Tim, I'm still looking for a good application for the ternary golay code. It seems a waste to have a perfect code available and no place to use it. I've modelled some stuff with it, and it is quite interesting to play with. But a 3 level slicer is a bit strange! For Jaco's viewpoint and what you recall, the working with different radices drives home the unification of ECC processes and the underlying mathematical processes. Binary just happens to be quite convenient in practice. Clay
Thanks a lot for the suggestions and remarks.

I see our library has a copy of the mentioned book.  I will certainly look at it.

Thanks again,
Jaco
"Clay Turner" <physics@bellsouth.net> writes:

> "Tim Wescott" <tim@wescottnospamdesign.com> wrote in message > news:10p74lgg9ksjn43@corp.supernews.com... > >> > > Basically you do the same thing as you do over GF(2): you do all > > addition & multiplication modulo 3, you take care of subtraction and > > division by using the inverses, etc. > > > > I felt that book does a very good job of explaining the concept (it must > > have -- I've never used GF(n != 2) codes, yet I remembered what to do > > and where to find it!). > > > > -- > > Hello Tim, > > I'm still looking for a good application for the ternary golay code. It > seems a waste to have a perfect code available and no place to use > it.
Use it with a 3-psk modulation system.
> I've > modelled some stuff with it, and it is quite interesting to play with. But a > 3 level slicer is a bit strange! > > For Jaco's viewpoint and what you recall, the working with different radices > drives home the unification of ECC processes and the underlying mathematical > processes. Binary just happens to be quite convenient in practice. > > Clay > >
-- Johan KULLSTAM