ECE4253 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.

The primitive GF(2) polynomial P(x) defines a GF(2³) as the set {0, a¹, a²,...,a⁷} modulus P(x) where a is a root of P(x) in GF(2³).

The terms {aⁿ} may be computed directly as xⁿ modulo P(x). Click on one of the 3-bit values above to confirm this calculation using the polynomial calculator.

For this P(x) of degree 3, a complete set of 2³ - 1 = 7 non-zero elements is defined. This choice of P(x) is a primitive polynomial in GF(2). ( See the factors of P(x) )

Let a GF(23) be defined on the GF(2) primitive polynomial P(x) = x3 + x + 1. By definition, P(x) is a factor of x7+1 = (x3 + x2 + 1)(x3 + x + 1)(x + 1). These three polynomials are related through this factoring and their zeros and they define the candidate polynomials or minimal polynomials forming a BCH code. Now, any degree n polynomial A(x) will have n roots giving A(x) = 0, and it follows that in GF(8), x7+1 has 7 zeros that number in the unique zeros of each of its 3 factors. In this example, (x3 + x + 1) = 0 for x = {2,4,6}; and (x3 + x2 + 1) = 0 for x = {3,5,7}, and; (x + 1) = 0 for x = {1}, all computed in GF(8) mod P(x).

In the above table, each term aⁿ is associated with a minimal polynomial. The primitive polynomial P(x) of degree 3 is by definition a factor of x⁷+1 and the minimal polynomials shown represent all the irreducible factors of x⁷+1 including P(x). The BCH code generating polynomial is formed from one or more of these minimal polynomials.

The minimal polynomial M(x) associated with a given aⁿ is the one for which aⁿ is a root; in other words, for which M(aⁿ) = 0.

For example, the minimal polynomial for a⁶ in the table 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 ) + ( a²+a+1 ) + 1

M( a⁶ ) = 0, and therefore a⁶ is a root of M(x).

Each element aⁿ is the root of only one of the minimal polynomials; however, each minimal polynomial may have several roots in {aⁿ}. This observation resolves the issue of redundant information raised on the previous page as the terms in {aⁿ} which contribute usefully to growing the BCH generator matrix must have different minimal polynomials.

Identifying Minimal Polynomials

The structure imposed by the use of fields based on {aⁿ} is revealed by the surprising way in which minimal polynomials are related.

Let the first minimal polynomial have the root a¹, where n=(001) in 3-bit binary, and consider the rotations of these three bits:

Let the next minimal polynomial have the root a³, where n=(011) in 3-bit binary, and consider the rotations of these three bits:

Creating a BCH Generator Polynomial

A BCH generating polynomial can produce codewords with predictable distance properties given a set of distinct minimal polynomials.

1. Let t be the number of bit errors to be corrected. The required Hamming distance is D=2t+1
2. Identify a set of minimal polynomials from {aⁿ} for n= 1 to 2t.
3. Reduce the set by deleting any duplicate minimal polynomials.
4. The BCH generating polynomial G(x) is the product of the remaining minimal polynomials.

The original polynomial P(x) of degree 3 defines a codeword size of n=7 bits where 7 = 2³-1; the BCH polynomial G(x) of degree 3 defines 3 parity bits such that k = 7 - 3 = 4 to give (n,k) = (7,4).

This BCH (7,4) code can correct at least 1 bit error, as specified. (See the codewords and matrices)

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

2024-04-26 14:54:41 ADT Last Updated: 2010-02-23	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...