Hi,

For a normal binary BCH code of length n = 2^m - 1, n - k <= m*t we
construct a generator polynomial such that alpha,
alpha^2,...,alpha^{2*t) are roots of the generator polynomial (where
alpha is a primitive element in GF(2^m).  This can be constructed by
multiplying the minimal polynomials phi_i(x) (where phi_i is the
minimal polynomial of alpha^i).

The parity-check matrix is constructed by using the roots:

     -                                                 -
H = | 1    alpha    alpha^2       ...    alpha^{n-1}    |
    | 1    alpha^2  (alpha^2)^2   ...   (alpha^2)^{n-1} |
    | .      .          .         ...         .         |
    | 1    alpha^t   (alpha^t)^2  ...   (alpha^t)^{n-1} |
     -                                                 -

Thus, H*transpose(v) = 0, where v is any valid codeword of the BCH
code.  This is the same as substituting each root in v(x), and getting
the result as zero.

I want to extend these principles to codes over GF(2^m).  I tried an
example using codes over GF(2^4).  I facorized x^13 + 1 in GF(2^m),
and obtained the following factors (using MAGMA) (these will each
generate a (13,10) cyclic code with d_{min} = 4):

f1 = x^3 + z^7*x^2 + z^13*x + 1;
f2 = x^3 + z^11*x^2 + z^14*x + 1;
f3 = x^3 + z^13*x^2 + z^7*x + 1;
f4 = x^3 + z^14*x^2 + z^11*x + 1;

(z = alpha)

When I factored f1 over GF(2^12), I got the following:
x + z^568
x + z^3625
x + z^3997

However, when I multiply a polynomial p(x) with f1 in GF(2^4) to
obtain c(x) and then substitute the roots (z^568, z^3625, z^3997) into
c(x) in GF(2^12), the results are not zero.  Why doesn't this work? 
How can I change this?  (I know that the fields are generated using
Conway polynomials -> Should I try to use another polynomial to
generate the GF(2^12) field?)  Also, multiplying f1*p in GF(2^4)
results in a different polynomial than when I multiply f1*p in
GF(2^12).   Why does this work for the binary case, but doesn't work
for the non-binary case?

Your time. effort and suggestions will be greatly appreciated.
Jaco Versfeld

Jaco Versfeld wrote:

> 
> I want to extend these principles to codes over GF(2^m).  I tried an
> example using codes over GF(2^4).  I facorized x^13 + 1 in GF(2^m),
> and obtained the following factors (using MAGMA) (these will each
> generate a (13,10) cyclic code with d_{min} = 4):

Why should these codes necessarily have d_min=4? May be they do, I'm
just curious, because I didn't see how this would follow from the BCH-bound
or any bound that I know of?
 
> f1 = x^3 + z^7*x^2 + z^13*x + 1;
> f2 = x^3 + z^11*x^2 + z^14*x + 1;
> f3 = x^3 + z^13*x^2 + z^7*x + 1;
> f4 = x^3 + z^14*x^2 + z^11*x + 1;
> 
> (z = alpha)

What exactly is alpha here? My guess is that it is a root of 
x^4+x+1=0, but unless you know that you are fumbling in the dark,
and it is hard to guess/reproduce what might have gone wrong.

> When I factored f1 over GF(2^12), I got the following:
> x + z^568
> x + z^3625
> x + z^3997

What is z this time? Is it again something called 'alpha'. Surely
you are aware of the fact that this 'alpha' is different from the
'alpha' in the construction of GF(16)? Your notation suggests that
you always want alpha to be a primitive element of the field. So,
if beta=z is a primitive element of GF(2^12), then alpha=z^273 is
a primitive element of GF(2^4) (caveat: this alpha may have a different
minimal polynomial, i.e. it may now be that z^273 is a zero of
x^4+x^3+1=0 instead of x^4+x+1=0. (273 here = 4095/15).

Something very fishy about these zeros anyway. If f1 is a factor
of x^13+1, then all these roots should have order 13, i.e. the exponents
should be multiples of 4095/13=315, but they aren't.

> 
> However, when I multiply a polynomial p(x) with f1 in GF(2^4) to
> obtain c(x) and then substitute the roots (z^568, z^3625, z^3997) into
> c(x) in GF(2^12), the results are not zero.  Why doesn't this work?

No wonder! I guess that what happened is that you have named two different
things 'alpha' (or z), and this has lead to a confusion.

> How can I change this?  (I know that the fields are generated using
> Conway polynomials -> Should I try to use another polynomial to
> generate the GF(2^12) field?)  Also, multiplying f1*p in GF(2^4)
> results in a different polynomial than when I multiply f1*p in
> GF(2^12).   Why does this work for the binary case, but doesn't work
> for the non-binary case?

In binary case no powers of alpha appear as coefficients, so you didn't
have a chance to make this mistake.

What you should do, is to 
1) generate the field GF(2^12), call a primitive element alpha=z
2) identify the subfield GF(2^4) within this field: let beta=z^273,
   then GF(2^4)=GF(2)(beta)
3) you may want to find out the minimal polynomial of beta, so that
you can properly map elements of this subfield into a copy of GF(2^4)
generated by some other means.

If any of this is not crystal clear, then follow the earlier advice
and study a book on abstract algebra.

Good luck!

Jyrki Lahtonen, Turku, Finland

"Jyrki Lahtonen" <l...@utu.fi> wrote in message
news:4...@utu.fi...
>
>
> Jaco Versfeld wrote:
>
> >
> > I want to extend these principles to codes over GF(2^m).  I tried an
> > example using codes over GF(2^4).  I facorized x^13 + 1 in GF(2^m),
> > and obtained the following factors (using MAGMA) (these will each
> > generate a (13,10) cyclic code with d_{min} = 4):
>
> Why should these codes necessarily have d_min=4? May be they do, I'm
> just curious, because I didn't see how this would follow from the
BCH-bound
> or any bound that I know of?


In fact, a (13, 10) code with d_{min} = 4 is a maximum-distance-separable
code -- which makes Jaco's claim even more interesting, and certainly worth
publishing.

"Dilip V. Sarwate" <s...@YouEyeYouSee.edu> wrote in message
news:<bvefdr$pf7$1...@news.ks.uiuc.edu>...
> "Jyrki Lahtonen" <l...@utu.fi> wrote in message
> news:4...@utu.fi...
> >
> >
> > Jaco Versfeld wrote:
> >
> > >
> > > I want to extend these principles to codes over GF(2^m).  I tried an
> > > example using codes over GF(2^4).  I facorized x^13 + 1 in GF(2^m),
> > > and obtained the following factors (using MAGMA) (these will each
> > > generate a (13,10) cyclic code with d_{min} = 4):
> >
> > Why should these codes necessarily have d_min=4? May be they do, I'm
> > just curious, because I didn't see how this would follow from the
>  BCH-bound
> > or any bound that I know of?
> 
> 
> In fact, a (13, 10) code with d_{min} = 4 is a maximum-distance-separable
> code -- which makes Jaco's claim even more interesting, and certainly worth
> publishing.

Hi,

I stressed a moment on the claim I made that the codes have d_{min} =
4.  (Thought that this was one of my famous emails where I posted it
without making sure that everything was correct...).  One of the
theorems I did in a mathematical course on Coding Theory last year
stated that the minimum weight and minimum distance of a cyclic code
is equal to the weight of the generator polynomial.  Just to check
that my memory didn't forsake me, I tested the above polynomials with
Magma, and yes, according to Magma, they all generate (13,10) cyclic
codes with d_{min} = 4. [Using GF(2^4) generated by the "Conway
polynomials" -> don't know what this is yet, I think Conway found a
way to generate a primitive polynomail p_m for each GF(2^m).]

Thanks for the replies.

Jyrki Lahtonen <l...@utu.fi> wrote in message news:<4...@utu.fi>...
> Jaco Versfeld wrote:
> 
> > 
> > I want to extend these principles to codes over GF(2^m).  I tried an
> > example using codes over GF(2^4).  I facorized x^13 + 1 in GF(2^m),
> > and obtained the following factors (using MAGMA) (these will each
> > generate a (13,10) cyclic code with d_{min} = 4):
> 
> Why should these codes necessarily have d_min=4? May be they do, I'm
> just curious, because I didn't see how this would follow from the BCH-bound
> or any bound that I know of?
>  
> > f1 = x^3 + z^7*x^2 + z^13*x + 1;
> > f2 = x^3 + z^11*x^2 + z^14*x + 1;
> > f3 = x^3 + z^13*x^2 + z^7*x + 1;
> > f4 = x^3 + z^14*x^2 + z^11*x + 1;
> > 
> > (z = alpha)
> 
> What exactly is alpha here? My guess is that it is a root of 
> x^4+x+1=0, but unless you know that you are fumbling in the dark,
> and it is hard to guess/reproduce what might have gone wrong.
> 
> > When I factored f1 over GF(2^12), I got the following:
> > x + z^568
> > x + z^3625
> > x + z^3997
> 
> What is z this time? Is it again something called 'alpha'. Surely
> you are aware of the fact that this 'alpha' is different from the
> 'alpha' in the construction of GF(16)? Your notation suggests that
> you always want alpha to be a primitive element of the field. So,
> if beta=z is a primitive element of GF(2^12), then alpha=z^273 is
> a primitive element of GF(2^4) (caveat: this alpha may have a different
> minimal polynomial, i.e. it may now be that z^273 is a zero of
> x^4+x^3+1=0 instead of x^4+x+1=0. (273 here = 4095/15).
> 
> Something very fishy about these zeros anyway. If f1 is a factor
> of x^13+1, then all these roots should have order 13, i.e. the exponents
> should be multiples of 4095/13=315, but they aren't.
> 
> > 
> > However, when I multiply a polynomial p(x) with f1 in GF(2^4) to
> > obtain c(x) and then substitute the roots (z^568, z^3625, z^3997) into
> > c(x) in GF(2^12), the results are not zero.  Why doesn't this work?
> 
> No wonder! I guess that what happened is that you have named two different
> things 'alpha' (or z), and this has lead to a confusion.
> 
> > How can I change this?  (I know that the fields are generated using
> > Conway polynomials -> Should I try to use another polynomial to
> > generate the GF(2^12) field?)  Also, multiplying f1*p in GF(2^4)
> > results in a different polynomial than when I multiply f1*p in
> > GF(2^12).   Why does this work for the binary case, but doesn't work
> > for the non-binary case?
> 
> In binary case no powers of alpha appear as coefficients, so you didn't
> have a chance to make this mistake.
> 
> What you should do, is to 
> 1) generate the field GF(2^12), call a primitive element alpha=z
> 2) identify the subfield GF(2^4) within this field: let beta=z^273,
>    then GF(2^4)=GF(2)(beta)
> 3) you may want to find out the minimal polynomial of beta, so that
> you can properly map elements of this subfield into a copy of GF(2^4)
> generated by some other means.
> 
> If any of this is not crystal clear, then follow the earlier advice
> and study a book on abstract algebra.
> 
> Good luck!
> 
> Jyrki Lahtonen, Turku, Finland

Hi,

Last year I did a third year Abstract Algebra course.  It was an
introduction to Abstract Algebra, so we only touched the concepts.  We
did learn about subgroups and subrings, and maybe this ideas can be
extended to fields as well...  (We used "Contempory Abstract Algebra"
from J.A. Gallian.  We covered only the first 15 chapters in the
semester.  The book was excellent, for me anyways.)  Can you recommend
any book that will help me with the above problem.

I know that GF(2^12) is generated by a binary primitive polynomial,
(don't know which one was used by MAGMA, but I can find out).  Also,
for an m there are many fields GF(2^m), each generated by a different
primitive polynomial of degree m -> thus, there exists an isomorphism
between the fields, to use the correct mathematical terminology.

If I understand you correctly, I need to find the primitive polynomial
used to generate GF(2^4) such that GF(2^4) will be a subfield of the
GF(2^12) that was used with MAGMA.  The reason why the above example
failed was because the GF(2^4) was generated by a different primitive
polynomial than the GF(2^4) that would be a subfield of GF(2^12).

Thanks for your help, I appreciate it greatly
Jaco

ps.
I can be reached at: JV at ING dot RAU dot AC dot ZA.  Due to spam, I
don't use the above email anymore.

"Jaco Versfeld" <j...@hotmail.com> wrote in message
news:e...@posting.google.com...

>One of the theorems I did in a mathematical course on Coding Theory last
year
> stated that the minimum weight and minimum distance of a cyclic code
> is equal to the weight of the generator polynomial.

Are you sure that you are remembering the theorem correctly?  For
example, x^5 + x^4 + x^3 + x^2 + 1 is a primitive binary polynomial
of weight 5, but it generates a (31, 26) cyclic binary Hamming code
of minimum distance 3.

If your (13, 10) cyclic code really has minimum distance 4, then it is
an MDS code, and is certainly a new result as far as I know, and
certainly worth writing up for publication.  One can get a *noncyclic*
(13, 10) MDS code over GF(16) by starting with a cyclic (15, 12)
Reed-Solomon code over GF(16) and then shortening it by two symbols,
but your (13, 10) cyclic MDS code is a new entity to me.

"Dilip V. Sarwate" <s...@YouEyeYouSee.edu> wrote in message
news:<bvgkfr$f14$1...@news.ks.uiuc.edu>...
> "Jaco Versfeld" <j...@hotmail.com> wrote in message
> news:e...@posting.google.com...
> 
> >One of the theorems I did in a mathematical course on Coding Theory last
>  year
> > stated that the minimum weight and minimum distance of a cyclic code
> > is equal to the weight of the generator polynomial.
> 
> Are you sure that you are remembering the theorem correctly?  For
> example, x^5 + x^4 + x^3 + x^2 + 1 is a primitive binary polynomial
> of weight 5, but it generates a (31, 26) cyclic binary Hamming code
> of minimum distance 3.
> 
> If your (13, 10) cyclic code really has minimum distance 4, then it is
> an MDS code, and is certainly a new result as far as I know, and
> certainly worth writing up for publication.  One can get a *noncyclic*
> (13, 10) MDS code over GF(16) by starting with a cyclic (15, 12)
> Reed-Solomon code over GF(16) and then shortening it by two symbols,
> but your (13, 10) cyclic MDS code is a new entity to me.

I confused the above statement with the theorem that if the degree of
g(x) is n-k, g(x) will produce an (n,k) cyclic code given that g(x)
divides x^n - 1.

Intuitively, the above polynomials will generate a MDS code, because
the length of the codewords -> n = 13 are smaller than the length  (n
= 15) of the corresponding Reed-Solomon code in GF(2^4).  I think
suspect that this has something to do with the Singleton bound.  I
couldn't establish what the maximum length would be for a code to be
still a MDS code for GF(2^4).