BCH code

In coding theory, the Bose-Chaudhuri-Hocquenghem codes form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field. BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Chandra Bose and D. K. Ray-Chaudhuri. The name Bose-Chaudhuri-Hocquenghem arises from the initials of the inventors' surnames.
One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low-power electronic hardware.
BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, USB flash drives, solid-state drives, and two-dimensional bar codes.

Definition and illustration

Primitive narrow-sense BCH codes

Given a prime number and prime power with positive integers and such that, a primitive narrow-sense BCH code over the finite field with code length and distance at least is constructed by the following method.
Let be a primitive element of.
For any positive integer, let be the minimal polynomial with coefficients in of.
The generator polynomial of the BCH code is defined as the least common multiple.
It can be seen that is a polynomial with coefficients in and divides.
Therefore, the polynomial code defined by is a cyclic code.

Example

Let and . We will consider different values of for based on the reducing polynomial, using primitive element. There are fourteen minimum polynomials with coefficients in satisfying
The minimal polynomials are
The BCH code with has the generator polynomial
It has minimal Hamming distance at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits. It is also denoted as: BCH code.
The BCH code with has the generator polynomial
It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits. It is also denoted as: BCH code.
The BCH code with has the generator polynomial
It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. It is also denoted as: BCH code.
The BCH code with and higher has the generator polynomial
This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. It is also denoted as: BCH code. In fact, this code has only two codewords: 000000000000000 and 111111111111111.

General BCH codes

General BCH codes differ from primitive narrow-sense BCH codes in two respects.
First, the requirement that be a primitive element of can be relaxed. By relaxing this requirement, the code length changes from to the order of the element
Second, the consecutive roots of the generator polynomial may run from instead of
Definition. Fix a finite field where is a prime power. Choose 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 1, and the order of modulo is
Therefore, the simplified definition is indeed a special case of the general one.

Special cases

A BCH code with is called a narrow-sense BCH code.
A BCH code with is called primitive.

The generator polynomial of a BCH code has coefficients from
In general, a cyclic code over with as the generator polynomial is called a BCH code over
The BCH code over and generator polynomial with successive powers of as roots is one type of Reed–Solomon code where the decoder alphabet is the same as the channel alphabet, all elements of . The other type of Reed Solomon code is an original view Reed Solomon code which is not a BCH code.

Properties

The generator polynomial of a BCH code has degree at most. Moreover, if and, the generator polynomial has degree at most.
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.
A BCH code has minimal Hamming distance at least.
Suppose that is a code word with fewer than non-zero terms. Then
Recall that are roots of hence of. This implies that satisfy the following equations, for each :
In matrix form, we have
The determinant of this matrix equals
The matrix is seen to be a Vandermonde matrix, and its determinant is
which is non-zero. It therefore follows that hence
A BCH code is cyclic.
A polynomial code of length is cyclic if and only if its generator polynomial divides Since is the minimal polynomial with roots it suffices to check that each of is a root of This follows immediately from the fact that is, by definition, an th root of unity.

Encoding

Because any polynomial that is a multiple of the generator polynomial is a valid BCH codeword, BCH encoding is merely the process of finding some polynomial that has the generator as a factor.
The BCH code itself is not prescriptive about the meaning of the coefficients of the polynomial; conceptually, a BCH decoding algorithm's sole concern is to find the valid codeword with the minimal Hamming distance to the received codeword. Therefore, the BCH code may be implemented either as a systematic code or not, depending on how the implementor chooses to embed the message in the encoded polynomial.

Non-systematic encoding: The message as a factor

The most straightforward way to find a polynomial that is a multiple of the generator is to compute the product of some arbitrary polynomial and the generator. In this case, the arbitrary polynomial can be chosen using the symbols of the message as coefficients.
As an example, consider the generator polynomial, chosen for use in the binary BCH code used by POCSAG and others. To encode the 21-bit message, we first represent it as a polynomial over :
Then, compute :
Thus, the transmitted codeword is.
The receiver can use these bits as coefficients in and, after error-correction to ensure a valid codeword, can recompute

Systematic encoding: The message as a prefix

A systematic code is one in which the message appears verbatim somewhere within the codeword. Therefore, systematic BCH encoding involves first embedding the message polynomial within the codeword polynomial, and then adjusting the coefficients of the remaining terms to ensure that is divisible by.
This encoding method leverages the fact that subtracting the remainder from a dividend results in a multiple of the divisor. Hence, if we take our message polynomial as before and multiply it by , we can then use Euclidean division of polynomials to yield:
Here, we see that is a valid codeword. As is always of degree less than , we can safely subtract it from without altering any of the message coefficients, hence we have our as
Over , this process is indistinguishable from appending a cyclic redundancy check, and if a systematic binary BCH code is used only for error-detection purposes, we see that BCH codes are just a generalization of the mathematics of cyclic redundancy checks.
The advantage to the systematic coding is that the receiver can recover the original message by discarding everything after the first coefficients, after performing error correction.

Decoding

There are many algorithms for decoding BCH codes. The most common ones follow this general outline:

Calculate the syndromes s_j for the received vector
Determine the number of errors t and the error locator polynomial Λ from the syndromes
Calculate the roots of the error location polynomial to find the error locations X_i
Calculate the error values Y_i at those error locations
Correct the errors

During some of these steps, the decoding algorithm may determine that the received vector has too many errors and cannot be corrected. For example, if an appropriate value of t is not found, then the correction would fail. In a truncated code, an error location may be out of range. If the received vector has more errors than the code can correct, the decoder may unknowingly produce an apparently valid message that is not the one that was sent.

Calculate the syndromes

The received vector is the sum of the correct codeword and an unknown error vector The syndrome values are formed by considering as a polynomial and evaluating it at Thus the syndromes are
for to
Since are the zeros of of which is a multiple, Examining the syndrome values thus isolates the error vector so one can begin to solve for it.
If there is no error, for all If the syndromes are all zero, then the decoding is done.

Calculate the error location polynomial

If there are nonzero syndromes, then there are errors. The decoder needs to figure out how many errors and the location of those errors.
If there is a single error, write this as where is the location of the error and is its magnitude. Then the first two syndromes are
so together they allow us to calculate and provide some information about .
If there are two or more errors,
It is not immediately obvious how to begin solving the resulting syndromes for the unknowns and
The first step is finding, compatible with computed syndromes and with minimal possible locator polynomial:
Three popular algorithms for this task are:

Peterson–Gorenstein–Zierler algorithm
Berlekamp–Massey algorithm
Sugiyama Euclidean algorithm