EE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

On this page, various polynomials can be chosen to demonstrate the structure of BCH codes capable of correcting several bit errors.

Given 1011, describing P(x) = x3 + x + 1, then if a is a root:

a3 + a + 1 = 0

a3 = a + 1

Successive terms in aN follow as shown below.

The polynomial P(x) defines the modulus for multiplication on this set. Each result here represents the remainder when x^N is divided by P(x). Click on one of the 3-bit values above to confirm the division result using the polynomial calculator. For any P(x) of order 3, remainders will have 3-bits.

For this P(x) of order 3, a complete set of 2³ - 1 = 7 non-zero elements is defined. This choice of P(x) is a primitive polynomial. ( See the factors of P(x) ) The 3-bit terms including [000] describe a Galois field GF(2³) generated by P(x).

The BCH codes are based on the minimal polynomials shown in the above table for each a^N. Specifically, BCH codes are constructed on the product of different minimum polynomials drawn from a range of terms in a^N.

The minimal polynomial M(x) for a given a^N is the smallest polynomial for which M(a^N) = 0

For example, in row 4 above, the minimal polynomial for a⁴ is given as M(x) = x³+x+1 and, for x = a⁴:

M( a⁴ ) = (a⁴)³ + a⁴ + 1

M( a⁴ ) = a¹² + a⁴ + 1

M( a⁴ ) = ( a²+a+1 ) + ( a²+a ) + 1

M( a⁴ ) = 0, and no smaller polynomials satisfy this condition The terms can be confirmed in the highighted column of the table below showing powers of a⁴.

Observe that the minimal polynomials for a¹ and a² are the same, and that any even numbered minimal polynomial a²ⁱ can be found previously in the list at aⁱ.

For a given P(x) of order 3 and 2³ - 1 = 7 unique a^N terms, the set of minimal polynomials is found in the factors of the polynomial x⁷+1 (See the Factors)

Table of Powers a^N

Each column contains successive powers of a^N raised to the power i. These terms serve to define the generator G(x) for BCH codewords.

Highlighted values in each column correspond to terms defining the minimal polynomial for each a^N. These values must add to zero since a^N is a root of its minimal polynomial.

Model C-182T BCH CODE GENERATOR P(x) = 1011 : P[x] = x3+x+1 1101 : P[x] = x3+x2+1 10011 : P[x] = x4+x+1 11001 : P[x] = x4+x3+1 100101 : P[x] = x5+x2+1 101001 : P[x] = x5+x3+1 101111 : P[x] = x5+x3+x2+x+1 110111 : P[x] = x5+x4+x2+x+1 111011 : P[x] = x5+x4+x3+x+1 111101 : P[x] = x5+x4+x3+x2+1 1000011 : P[x] = x6+x+1 1011011 : P[x] = x6+x4+x3+x+1 1100001 : P[x] = x6+x5+1 1100111 : P[x] = x6+x5+x2+x+1 1101101 : P[x] = x6+x5+x3+x2+1 1110011 : P[x] = x6+x5+x4+x+1    t= 1 2 3 4 5 6 7 8 9 Derivation  | Row Table  | Discussion  | MATLAB

Sun May 19 00:34:11 ADT 2013 Last Updated: 23 FEB 2010	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...