In coding theory the BCH codes form a class of parameterised error-correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose and Ray-Chaudhuri [Page 189, cite book
last = Reed
first = Irving, S.
authorlink = Irving S. Reed
title = Error-Control Coding for Data Networks
publisher = Kluwer Academic Publishers
isbn = 0-7923-8528-4 ] . The acronym "BCH" comprises the initials of these inventors' names.
The principal advantage of BCH codes is the ease with which they can be decoded, via an elegant algebraic method known as syndrome decoding. This allows very simple electronic hardware to perform the task, obviating the need for a computer, and meaning that a decoding device may be made small and low-powered. As a class of codes, they are also highly flexible, allowing control over block length and acceptable error thresholds, meaning that a custom code can be designed to a given specification (subject to mathematical constraints).
In technical terms a BCH code is a multilevel, cyclic, error-correcting, variable-length digital code used to correct multiple random error patterns. BCH codes may also be used with multilevel phase-shift keying whenever the number of levels is a prime number or a power of a prime number. A BCH code in 11 levels has been used to represent the 10 decimal digits plus a sign digit. [Federal Standard 1037C, 1996.]
Construction
A BCH code is a polynomial code over a finite field with a particularly chosen generator polynomial. It is also a cyclic code.
Simplified BCH codes
For ease of exposition, we first describe a special class of BCH codes. General BCH codes are described in the next section.
Definition. Fix a finite field , where is a prime power. Also fix positive integers , , and such that and . We will construct a polynomial code over with code length , whose minimum Hamming distance is at least .What remains to be specified is the generator polynomial of this code.
Let be a primitive th root of unity in . For all , let be the minimal polynomial of with coefficients in . The generator polynomial of the BCH code is defined as the least common multiple .
Example
Let and (therefore ). We will consider different values of . There is a primitive root satisfying : (1);its minimal polynomial over is :. Note that in , the equation holds, and therefore.Thus is a root of , and therefore :.To compute , notice that, by repeated application of (1), we have the following linear relations:
*
*
*
*
* Five right-hand-sides of length four must be linearly dependent, and indeed we find a linear dependency .Since there is no smaller degree dependency, the minimal polynomial of is :.Continuing in a similar manner, we find
::::
The BCH code with has generator polynomial
:
It has minimal Hamming distance at least 3 and corrects up to 1 error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.
The BCH code with has generator polynomial
:
It has minimal Hamming distance at least 5 and corrects up to 2 errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.
The BCH code with has generator polynomial
:
It has minimal Hamming distance at least 7 and corrects up to 3 errors. This code has 5 data bits and 10 checksum bits.
The BCH code with and higher have generator polynomial
:
This code has minimal Hamming distance 8 and corrects up to 3 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.
General BCH codes
General BCH codes differ from the simplified case discussed above in two respects. First, one replaces the requirement by a more general condition. Second, the consecutive roots of the generator polynomial may run from instead of .
Definition. Fix a finite field , where is a prime power. Chose positive integers such that , , and is the multiplicative order of modulo .
As before, let be a primitive th root of unity in , and let be the minimal polynomial over of for all . The generator polynomial of the BCH code is defined as the least common multiple .
Note: if as in the simplified definition, then is automatically 1, and the order of modulo is automatically . Therefore, the simplified definition is indeed a special case of the general one.
Properties
1. The generator polynomial of a BCH code has degree at most . Moreover, if and , the generator polynomial has degree at most .
:Proof: each minimal polynomial has degree at most . Therefore, the least common multiple of of them has degree at most . Moreover, if , then for all . Therefore, is the least common multiple of at most minimal polynomials for odd indices , each of degree at most .
2. A BCH code has minimal Hamming distance at least . Proof: We only give the proof in the simplified case; the general case is similar. Suppose that is a code word with fewer than non-zero terms. Then
: