ECE4253 Digital Communications  
Department of Electrical and Computer Engineering  University of New Brunswick, Fredericton, NB, Canada  
Error control codewords with predictable properties can be generated using a primitive polynomial P(x) to build a suitable generator polynomial G(x). To this end, BoseChaudhuriHocquenghem (BCH) codes can be specified having a target minimum distance (D). To correct t errors a minimum distance D=2t+1 is required. An (n,k) BCH code with minimum distance D=3 would be labeled BCH(n,k,3).
In an introduction to BCH codes, the basic technique of using BCH codes for single and doubleerror correction was outlined. 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^{3}) as the set {0, a^{1}, a^{2},...,a^{7}} modulus P(x) where a is a root of P(x) in GF(2^{3}).
GF(8) : P(x) = x^{3} + x + 1  
 MINIMAL POLYNOMIAL  
a^{0}  = 1  = 001  = 1  = a^{7}  = a^{14}  = a^{21}  ...   x+1 
a^{1}  = a  = 010  = 2  = a^{8}  = a^{15}  = a^{22}  ...   x^{3}+x+1 
a^{2}  = a^{2}  = 100  = 4  = a^{9}  = a^{16}  = a^{23}  ...   x^{3}+x+1 
a^{3}  = a+1  = 011  = 3  = a^{10}  = a^{17}  = a^{24}  ...   x^{3}+x^{2}+1 
a^{4}  = a^{2}+a  = 110  = 6  = a^{11}  = a^{18}  = a^{25}  ...   x^{3}+x+1 
a^{5}  = a^{2}+a+1  = 111  = 7  = a^{12}  = a^{19}  = a^{26}  ...   x^{3}+x^{2}+1 
a^{6}  = a^{2}+1  = 101  = 5  = a^{13}  = a^{20}  = a^{27}  ...   x^{3}+x^{2}+1 
a^{7}  = 1  = 001  = 1  = a^{14}  = a^{21}  = a^{28}  ...   x+1 
The terms {a^{n}} may be computed directly as x^{n} modulo P(x). Click on one of the 3bit values above to confirm this calculation using the polynomial calculator.
For this P(x) of degree 3, a complete set of 2^{3}  1 = 7 nonzero elements is defined. This choice of P(x) is a primitive polynomial in GF(2). ( See the factors of P(x) )
Let a GF(2^{3}) be defined on the GF(2) primitive polynomial P(x) = x^{3} + x + 1. By definition, P(x) is a factor of x^{7}+1 = (x^{3} + x^{2} + 1)(x^{3} + 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), x^{7}+1 has 7 zeros that number in the unique zeros of each of its 3 factors. In this example, (x^{3} + x + 1) = 0 for x = {2,4,6}; and (x^{3} + x^{2} + 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^{n} is associated with a minimal polynomial. The primitive polynomial P(x) of degree 3 is by definition a factor of x^{7}+1 and the minimal polynomials shown represent all the irreducible factors of x^{7}+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^{n} is the one for which a^{n} is a root; in other words, for which M(a^{n}) = 0.
For example, the minimal polynomial for a^{5} in the table is given as M(x) = x^{3}+x^{2}+1 and, for x = a^{5}:
M( a^{5} ) = (a^{5})^{3} + (a^{5})^{2} + 1
M( a^{5} ) = a^{15} + a^{10} + 1
M( a^{5} ) = ( a ) + ( a+1 ) + 1
M( a^{5} ) = 0, and therefore a^{5} is a root of M(x).
Each element a^{n} is the root of only one of the minimal polynomials; however, each minimal polynomial may have several roots in {a^{n}}. This observation resolves the issue of redundant information raised on the previous page as the terms in {a^{n}} 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^{n}} is revealed by the surprising way in which minimal polynomials are related.
Let the first minimal polynomial have the root a^{1}, where n=(001) in 3bit binary, and consider the rotations of these three bits:
(001) → (010) → (100)
The terms {a^{1}, a^{2}, a^{4}} share the same minimal polynomial M(x)=x^{3}+x+1.
Let the next minimal polynomial have the root a^{3}, where n=(011) in 3bit binary, and consider the rotations of these three bits:
(011) → (110) → (101)
The terms {a^{3}, a^{6}, a^{5}} share the same minimal polynomial M(x)=x^{3}+x^{2}+1.
Creating a BCH Generator Polynomial
A BCH generating polynomial can produce codewords with predictable distance properties given a set of distinct minimal polynomials.
(1011)
The original polynomial P(x) of degree 3 defines a codeword size of n=7 bits where 7 = 2^{3}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)

20240714 16:20:43 ADT
Last Updated: 20100223 
Richard Tervo [ tervo@unb.ca ]  Back to the course homepage... 