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

BCH Code Generator

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(23) as the set {0, a1, a2,...,a7} modulus P(x) where a is a root of P(x) in GF(23).

 GF(8) : P(x) = x3 + x + 1 |  MINIMAL POLYNOMIAL a0 = 1 = 001 = 1 = a7 = a14 = a21 ... |  x+1 a1 = a = 010 = 2 = a8 = a15 = a22 ... |  x3+x+1 a2 = a2 = 100 = 4 = a9 = a16 = a23 ... |  x3+x+1 a3 = a+1 = 011 = 3 = a10 = a17 = a24 ... |  x3+x2+1 a4 = a2+a = 110 = 6 = a11 = a18 = a25 ... |  x3+x+1 a5 = a2+a+1 = 111 = 7 = a12 = a19 = a26 ... |  x3+x2+1 a6 = a2+1 = 101 = 5 = a13 = a20 = a27 ... |  x3+x2+1 a7 = 1 = 001 = 1 = a14 = a21 = a28 ... |  x+1

The terms {an} may be computed directly as xn 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 23 - 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) )

Minimal Polynomials

 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 an is associated with a minimal polynomial. The primitive polynomial P(x) of degree 3 is by definition a factor of x7+1 and the minimal polynomials shown represent all the irreducible factors of x7+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 an is the one for which an is a root; in other words, for which M(an) = 0.

For example, the minimal polynomial for a5 in the table is given as M(x) = x3+x2+1 and, for x = a5:

M( a5 ) = (a5)3 + (a5)2 + 1

M( a5 ) = a15 + a10 + 1

M( a5 ) = ( a ) + ( a+1 ) + 1

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

Each element an is the root of only one of the minimal polynomials; however, each minimal polynomial may have several roots in {an}. This observation resolves the issue of redundant information raised on the previous page as the terms in {an} 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 {an} is revealed by the surprising way in which minimal polynomials are related.

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

(001) → (010) → (100)

The terms {a1, a2, a4} share the same minimal polynomial M(x)=x3+x+1.

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

(011) → (110) → (101)

The terms {a3, a6, a5} share the same minimal polynomial M(x)=x3+x2+1.

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 {an} 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.

Generator Polynomial G(x) for BCH Code (D=3) based on P(x) = x3+x+1
To achieve t=1, using two terms i=(1 .. 2) reduced to one unique term i=(1)
Terms having duplicate minimal polynomials are not used.

G(x) = x3+x+1

(1011)

The original polynomial P(x) of degree 3 defines a codeword size of n=7 bits where 7 = 23-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)

Select a primitive polynomial P(x) and specify the target number of bits to correct t

 2024-08-08 20:36:17 ADT Last Updated: 2010-02-23 Richard Tervo [ tervo@unb.ca ]