BCH Block Length?

Thread View: sci.math.research

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by alavarre Mon, 13 Jun 1994 12:03

#207

Author: alavarre
Date: Mon, 13 Jun 1994 12:03

26 lines
1916 bytes

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?"

I can see how the order (q) of the elements on GF(q) results in 
q distinct roots, hence a generator polynomial of degree q, and 
that for an extension field GF(2^m), q=2^m is always even, 
making the generator polynomial always of odd length.
  
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?

TIA,
Andy La Varre
alavarre@ids.net

Re: BCH Block Length?

#208

Author: Richard Pinch
Date: Mon, 13 Jun 1994 14:36

45 lines
3192 bytes

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

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads