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

The Bose-Chaudhuri-Hocquenghem (BCH) codes are a widely used class of multi-bit error correcting codes. A simple BCH code is developed here which can achieve two-bit error correction on 7-bit codewords. An (n,k) BCH code with minimum distance D=5 is generally labeled BCH(n,k,5).

Matrices constructed on polynomial-based Galois fields have been used to develop codes for single bit error correction. From these same formulations, it is possible to construct BCH codes with predictable distance properties and the abllity to correct multi-bit errors.

The Galois field GF(2³) or GF(8) has eight elements numbered [0..7] as shown below. The specific relationship among these elements is defined by a primitive polynomial P(x) with degree 3. In this example, let P(x) = x³ + x + 1. If some element a is a root of P(x), then P(a) = 0. From the table below, P(a) = a³ + a + 1 = 3 + 2 + 1 = 0 with the usual bitwise modulo 2 addition.

Observe that consecutive powers of a^N reduce to seven different 3-bit terms and that the sequence repeats periodically for N>6, such that a⁷ = a⁰ and so on. All positive powers of a^N can be found in this way. These powers will serve to develop a check matrix capable of multi-bit error correction. In general, operations within this GF(8) use the usual modulus 2 arithmetic on 3-bit values. For example 011 + 101 = 110, or 3 + 5 = 6.

The i-th power of each of the elements a^N can be described as a^Ni. From the values found above, these powers can be summarized as the octal values shown here:

Rows in the table repeat periodically for i > 7. The row for i = 7 is included for completeness.

Single-Bit Error Correction (D=3)

The (3 x 7) check matrix H for single-bit error correction is defined from the above table (with i=1) as shown below.

    A B C D E F G 
H = 5 7 6 3 4 2 1 
 
    1 1 1 0 1 0 0 
H = 0 1 1 1 0 1 0 
    1 1 0 1 0 0 1 

Single bit error correction is possible because every 3-bit column is unique. For example, the single bit error E(x) = x⁴ returns the syndrome 6 from column C and no other single bit error will return this same value.

Double-bit error correction is not possible because different two-bit errors do not give a unique result. The two bit error E(x) = x⁶ + x³ returns a non-zero syndrome (detection!); however, it is the same syndrome as above, since the bits (A,D) give 3 + 5 = 6. Also, the two-bit error (B,G) is 7 + 1 = 6. Consequently, there is no way to distinguish between different two-bit patterns and therefore no way to correct two bad bits.

Overall, this matrix gives a minimum Hamming distance D=3. Using a different row (i<7) in the table simply changes the column ordering and would not improve this situation, although the specific syndromes would be different for each column.

Double-Bit Error Correction (D=5)

To achieve two bit error correction, D=5 is necessary. To this end, the check matrix may be expanded to give different syndromes for each of the expected error patterns. The challenge of course is to determine how to extend this matrix to assure that all one- and two-bit errors will give a unique syndrome. Note that in every row (i) the different column ordering gives a different syndrome for any specific error, so the combination of two rows from the table is key to this next step.

Using the same GF(8) as the basis for this new matrix, another row may be incorporated as shown below. This additional row will add three rows to the binary matrix. Choose i=3 for this new row.

The (6 x 7) check matrix H for double-bit error correction is defined with i=(1,3) shown below.

    A B C D E F G 
H = 5 7 6 3 4 2 1 
    6 2 7 4 5 3 1 
 
    1 1 1 0 1 0 0 
H = 0 1 1 1 0 1 0 
    1 1 0 1 0 0 1 
    1 0 1 1 1 0 0 
    1 1 1 0 0 1 0 
    0 0 1 0 1 1 1 

Single bit error correction is still possible because every 6-bit column is unique. This result is assured from the original three rows and does not depend on the new rows. The single bit error E(x) = x⁴ now returns the 6-bit syndrome 67 (octal) from column C and no other single bit error will return this same value.

Double-bit error correction is now possible because different two-bit errors will give a unique result. The two bit error E(x) = x⁶ + x³ or (A,D) returns 34 + 56 = 62. Also the two-bit error (B,G) is now 72 + 11 = 63, another different result. Consequently, it is now possible to distinguish between different two-bit error patterns and therefore two bad bits can be corrected by identifying their unique syndrome. This syndrome is like a 'signature' for the error pattern. The table below shows the unique 6-bit syndrome (in octal) for all possible one and two bit errors.

Further observation reveals that this error check matrix also produces unique syndromes for three-bit errors, implying (D=7) and it exceeds the expected performance. With six bits dedicated to checkbits, there is only one information bit and the two valid seven-bit codewords are the trivial pair (0000000, 1111111) which could easily be corrected by hand (majority vote).

Overall, this check matrix confirms the performance of this BCH code. Using a different row (i) in the table may not lead to the same happy outcome; in practice; in particular, even-numbered rows do not contribute new information to the check matrix.

A Check Matrix that Does not Work

The (6 x 7) check matrix H for double-bit error correction is defined from the above table (with i=1 and i=2) as shown below. However, this choice of rows fails.

    A B C D E F G 
H = 5 7 6 3 4 2 1 
    7 3 2 5 6 4 1 
 
    1 1 1 0 1 0 0 
H = 0 1 1 1 0 1 0 
    1 1 0 1 0 0 1 
    1 0 0 1 1 1 0 
    1 1 1 0 1 0 0 
    1 1 0 1 0 0 1 

At first glance, this matrix seems as good as the previous example. Unfortunately, nothing has been gained by including this particular choice of new rows.

The single bit error E(x) = x⁴ now returns the 6-bit syndrome 62 (octal) from column C and no other single bit error will return this same value. The two bit error E(x) = x⁶ + x³ returns a non-zero syndrome (detection!) as the sum from the bits (A,D) give 35 + 57 = 62, the same as the single bit error. The new row does not contribute to distinguishing two-bit errors..

It happens that in this number system, squaring a term is a linear operation (in other words, x² + y² = (x+y)²) and each value in the row (i=2) is the square of the corresponding value found in (i=1). Moreover, none of the even-numbered rows will contribute any additional information necessary to give a unique syndrome. In particular, the values in rows i=(1,2) are squared with respect to each other, as are i=(2,4). The values i=(3,6) describe another pair of rows related by the square.

From row (i=1), let a=5 and d=3, then a+d=6. 

Let LHS = a2 + d2 
        = 52 + 32 
        = 7 + 5 
        = 2

Let RHS = (a+d)2. 
        = (6)2. 
        =  2 

LHS=RHS

Three-Bit Error Correction (D=7)

In general, the check matrix can be extended to higher order error correction by simply including more rows with a suitable index (i). In the present case, correction of three bit errors (D=7) has already been achieved with the two rows chosen above. When specifying a minimum error checking capability, the resulting code may actually be more performant.

A BCH Code has been constructed which can correct two-bit errors. While this example is limited by the low order polynomial used, a (6 x 7) check matrix was constructed systematically and is able to return a unique syndrome for all one- and two-bit errors. The two valid 7-bit codewords (0000000, 1111111) that emerge have the required distance properties (and more).

To continue this exploration of BCH codes, visit the Online BCH Code Generator.

Wed May 22 06:42:16 ADT 2013 Last Updated: 08 FEB 2010	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...