🚀 go-pugleaf

In article <2tk2pr$opp@paperboy.ids.net> alavarre@ids.net writes:
>
>Why must a BCH code have as a length the multiplicative order 
>of alpha?  
>
>Michelson, p. 121, states, without proof, that "The block 
>length of a  BCH code is the order of the element used in 
>defining the consecutive roots [of the generator polynomial]."  
>Gallager gives the same as a defined property of a BCH code.  
>My question is "why?"
>
>[...]
>  
>But it seems that the information word length k can be 
>arbitrary, and the resulting codeword must then be of arbitrary 
>degree (and length).
>
>So how does the choice of a particular generator constrain the 
>number of information bits and hence the length of the codeword?  And 
>why does the order of alpha matter?

A BCH code is an example of a cyclic code.  If a cyclic code has block
length l, then the code words can be regarded as polynomials c(X) in X
where X^l = 1.  The code then consists of multiples of a generator g(X)
which must be a factor of X^l - 1.  The number of information bits will
be the dimension of the resulting code as a vector space over GF(p):
this dimension will be l - d, where d is the degree of g.  So the number
of information bits in a cyclic code of length l is constrained by the
degrees of the possible factors of X^l - 1.  (The error checking 
capabilities are harder to control, hence the interest in BCH codes.)

For example, over GF(2) the polynomial X^23 - 1 factors as (X+1)FG where
F and G are polynomials each of degree 11.  So the code with generator
polynomial G has length 23 and dimension 12.  It happens that it has
minimum distance 7.  (This is the Golay code).  The generator may also
be specified by its roots.  This is how BCH codes are constructed.  For
example, let b be an element of order 7 in GF(2^3).  Then b and b^2 both
satisfy the polynomial X^3 + X + 1 over GF(2), which is a factor of
X^7 - 1, and so defines a cyclic code of length 7 and dimension 4. (This 
is the Hamming code.)

For further details, you might consult chapter 6 of Communication Theory,
by C.M. Goldie and [ahem] R.G.E. Pinch, Cambridge University Press, 1991.

Richard Pinch;  Pure Mathematics, Cambridge