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 4-bit values above to confirm this calculation using the polynomial calculator.

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

In the above table, each term aⁿ is associated with a minimal polynomial. The primitive polynomial P(x) of degree 4 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²+1 ) + ( a³+a² ) + 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=(0001) in 4-bit binary, and consider the rotations of these four bits:

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

Let the next minimal polynomial have the root a⁵, where n=(0101) in 4-bit binary, and consider the rotations of these four bits:

Let the next minimal polynomial have the root a⁷, where n=(0111) in 4-bit binary, and consider the rotations of these four 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.

This G(x) is the product of three minimal polynomials for {a¹,a³,a⁵} as:

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

This BCH (15,5) code can correct at least 3 bit errors, 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-29 17:45:34 ADT Last Updated: 2010-02-23	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...