Open main menu

In coding theory, the BCH codes or Bose–Chaudhuri–Hocquenghem codes form a class of cyclic error-correcting codes that are constructed using polynomials over a finite field (also called Galois field). BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Bose and D. K. Ray-Chaudhuri.[1][2][3] The name Bose–Chaudhuri–Hocquenghem (and the acronym BCH) arises from the initials of the inventors' surnames (mistakenly, in the case of Ray-Chaudhuri).

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,[4] compact disc players, DVDs, disk drives, solid-state drives[5] and two-dimensional bar codes.

Contents

Definition and illustrationEdit

Primitive narrow-sense BCH codesEdit

Given a prime number q and prime power qm with positive integers m and d such that dqm − 1, a primitive narrow-sense BCH code over the finite field (or Galois field) GF(q) with code length n = qm − 1 and distance at least d is constructed by the following method.

Let α be a primitive element of GF(qm). For any positive integer i, let mi(x) be the minimal polynomial with coefficients in GF(q) of αi. The generator polynomial of the BCH code is defined as the least common multiple g(x) = lcm(m1(x),…,md − 1(x)). It can be seen that g(x) is a polynomial with coefficients in GF(q) and divides xn − 1. Therefore, the polynomial code defined by g(x) is a cyclic code.

ExampleEdit

Let q=2 and m=4 (therefore n=15). We will consider different values of d. For GF(16) = GF(24) based on the polynomial x4+x+1 with primitive root α=x+0 there are minimum polynomials mi(x) with coefficients in GF(2) satisfying

 

The minimal polynomials of the fourteen powers of α are

 
 
 
 

The BCH code with   has 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.

The BCH code with   has 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.

The BCH code with   has 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. (This particular generator polynomial has a real-world application, in the format patterns of the QR code.)

The BCH code with   and higher has generator polynomial

 

This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.

General BCH codesEdit

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 casesEdit

  • 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 (syndromes) alphabet is the same as the channel (data and generator polynomial) alphabet, all elements of   .[6] The other type of Reed Solomon code is an original view Reed Solomon code which is not a BCH code.

PropertiesEdit

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  .

A BCH code has minimal Hamming distance at least  .

Proof

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.

Proof

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.

EncodingEdit

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 factorEdit

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 (31, 21) binary BCH code used by POCSAG and others. To encode the 21-bit message {101101110111101111101}, we first represent it as a polynomial over  :

 

Then, compute (also over  ):

 

Thus, the transmitted codeword is {1100111010010111101011101110101}.

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 prefixEdit

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 (non-message) 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   (to "shift" the message out of the way of the remainder), 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   (which is the degree of  ), we can safely subtract it from   without altering any of the message coefficients, hence we have our   as

 

Over   (i.e. with binary BCH codes), 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.

DecodingEdit

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

  1. Calculate the syndromes sj for the received vector
  2. Determine the number of errors t and the error locator polynomial Λ(x) from the syndromes
  3. Calculate the roots of the error location polynomial to find the error locations Xi
  4. Calculate the error values Yi at those error locations
  5. 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 (not primitive) 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 syndromesEdit

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[7]

 

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 polynomialEdit

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   (completely determining it in the case of Reed–Solomon codes).

If there are two or more errors,

 

It is not immediately obvious how to begin solving the resulting syndromes for the unknowns   and   First step is finding locator polynomial

  compatible with computed syndromes and with minimal possible  

Two popular algorithms for this task are:

  1. Peterson–Gorenstein–Zierler algorithm
  2. Berlekamp–Massey algorithm

Peterson–Gorenstein–Zierler algorithmEdit

Peterson's algorithm is the step 2 of the generalized BCH decoding procedure. Peterson's algorithm is used to calculate the error locator polynomial coefficients   of a polynomial

 

Now the procedure of the Peterson–Gorenstein–Zierler algorithm.[8] Expect we have at least 2t syndromes sc,...,sc+2t−1. Let v = t.

  • Start by generating the   matrix with elements that are syndrome values
 
  • Generate a   vector with elements
 
  • Let   denote the unknown polynomial coefficients, which are given by
 
  • Form the matrix equation
 
  • If the determinant of matrix   is nonzero, then we can actually find an inverse of this matrix and solve for the values of unknown   values.
  • If   then follow
       if  
       then
             declare an empty error locator polynomial
             stop Peterson procedure.
       end
       set  
       continue from the beginning of Peterson's decoding by making smaller  
  • After you have values of  , you have with you the error locator polynomial.
  • Stop Peterson procedure.

Factor error locator polynomialEdit

Now that you have the   polynomial, its roots can be found in the form   by brute force for example using the Chien search algorithm. The exponential powers of the primitive element   will yield the positions where errors occur in the received word; hence the name 'error locator' polynomial.

The zeros of Λ(x) are αi1, ..., αiv.

Calculate error valuesEdit

Once the error locations are known, the next step is to determine the error values at those locations. The error values are then used to correct the received values at those locations to recover the original codeword.

For the case of binary BCH, (with all characters readable) this is trivial; just flip the bits for the received word at these positions, and we have the corrected code word. In the more general case, the error weights   can be determined by solving the linear system

 

Forney algorithmEdit

However, there is a more efficient method known as the Forney algorithm.

Let

 
 

And the error evaluator polynomial[9]

 

Finally:

 

where

 

Than if syndromes could be explained by an error word, which could be nonzero only on positions  , then error values are

 

For narrow-sense BCH codes, c = 1, so the expression simplifies to:

 

Explanation of Forney algorithm computationEdit

It is based on Lagrange interpolation and techniques of generating functions.

Consider   and for the sake of simplicity suppose   for   and   for   Then

 
 

We want to compute unknowns   and we could simplify the context by removing the   terms. This leads to the error evaluator polynomial

 

Thanks to   we have

 

Thanks to   (the Lagrange interpolation trick) the sum degenerates to only one summand for  

 

To get   we just should get rid of the product. We could compute the product directly from already computed roots   of   but we could use simpler form.

As formal derivative

 

we get again only one summand in

 

So finally

 

This formula is advantageous when one computes the formal derivative of   form

 

yielding:

 

where

 

Decoding based on extended Euclidean algorithmEdit

An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama's adaptation of the Extended Euclidean algorithm.[10] Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let   be positions of unreadable characters. One creates polynomial localising these positions   Set values on unreadable positions to 0 and compute the syndromes.

As we have already defined for the Forney formula let  

Let us run extended Euclidean algorithm for locating least common divisor of polynomials   and   The goal is not to find the least common divisor, but a polynomial   of degree at most   and polynomials   such that   Low degree of   guarantees, that   would satisfy extended (by  ) defining conditions for  

Defining   and using   on the place of   in the Fourney formula will give us error values.

The main advantage of the algorithm is that it meanwhile computes   required in the Forney formula.

Explanation of the decoding processEdit

The goal is to find a codeword which differs from the received word minimally as possible on readable positions. When expressing the received word as a sum of nearest codeword and error word, we are trying to find error word with minimal number of non-zeros on readable positions. Syndrom   restricts error word by condition

 

We could write these conditions separately or we could create polynomial

 

and compare coefficients near powers   to  

 

Suppose there is unreadable letter on position   we could replace set of syndromes   by set of syndromes   defined by equation   Suppose for an error word all restrictions by original set   of syndromes hold, than

 

New set of syndromes restricts error vector

 

the same way the original set of syndromes restricted the error vector   Except the coordinate   where we have   an   is zero, if   For the goal of locating error positions we could change the set of syndromes in the similar way to reflect all unreadable characters. This shortens the set of syndromes by  

In polynomial formulation, the replacement of syndromes set   by syndromes set   leads to

 

Therefore,

 

After replacement of   by  , one would require equation for coefficients near powers  

One could consider looking for error positions from the point of view of eliminating influence of given positions similarly as for unreadable characters. If we found   positions such that eliminating their influence leads to obtaining set of syndromes consisting of all zeros, than there exists error vector with errors only on these coordinates. If   denotes the polynomial eliminating the influence of these coordinates, we obtain

 

In Euclidean algorithm, we try to correct at most   errors (on readable positions), because with bigger error count there could be more codewords in the same distance from the received word. Therefore, for   we are looking for, the equation must hold for coefficients near powers starting from

 

In Forney formula,   could be multiplied by a scalar giving the same result.

It could happen that the Euclidean algorithm finds   of degree higher than   having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors could be risky (especially with no other restrictions on received word). Usually after getting   of higher degree, we decide not to correct the errors. Correction could fail in the case   has roots with higher multiplicity or the number of roots is smaller than its degree. Fail could be detected as well by Forney formula returning error outside the transmitted alphabet.

Correct the errorsEdit

Using the error values and error location, correct the errors and form a corrected code vector by subtracting error values at error locations.

Decoding examplesEdit

Decoding of binary code without unreadable charactersEdit

Consider a BCH code in GF(24) with   and  . (This is used in QR codes.) Let the message to be transmitted be [1 1 0 1 1], or in polynomial notation,   The "checksum" symbols are calculated by dividing   by   and taking the remainder, resulting in   or [ 1 0 0 0 0 1 0 1 0 0 ]. These are appended to the message, so the transmitted codeword is [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].

Now, imagine that there are two bit-errors in the transmission, so the received codeword is [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. In polynomial notation:

 

In order to correct the errors, first calculate the syndromes. Taking   we have           and   Next, apply the Peterson procedure by row-reducing the following augmented matrix.

 

Due to the zero row, S3×3 is singular, which is no surprise since only two errors were introduced into the codeword. However, the upper-left corner of the matrix is identical to [S2×2 | C2×1], which gives rise to the solution     The resulting error locator polynomial is   which has zeros at   and   The exponents of   correspond to the error locations. There is no need to calculate the error values in this example, as the only possible value is 1.

Decoding with unreadable charactersEdit

Suppose the same scenario, but the received word has two unreadable characters [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. We replace the unreadable characters by zeros while creating the polynom reflecting their positions   We compute the syndromes   and   (Using log notation which is independent on GF(24) isomorphisms. For computation checking we can use the same representation for addition as was used in previous example. Hexadecimal description of the powers of   are consecutively 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 with the addition based on bitwise xor.)

Let us make syndrome polynomial

 

compute

 

Run the extended Euclidean algorithm:

 

We have reached polynomial of degree at most 3, and as

 

we get

 

Therefore,

 

Let   Don't worry that   Find by brute force a root of   The roots are   and   (after finding for example   we can divide   by corresponding monom   and the root of resulting monom could be found easily).

Let

 
 

Let us look for error values using formula

 

where   are roots of     We get

 

Fact, that   should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decoding with unreadable characters with a small number of errorsEdit

Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Again, replace the unreadable characters by zeros while creating the polynom reflecting their positions   Compute the syndromes   and   Create syndrome polynomial

 
 

Let us run the extended Euclidean algorithm:

 

We have reached polynomial of degree at most 3, and as

 

we get

 

Therefore,

 

Let   Don't worry that   The root of   is  

Let

 
 

Let us look for error values using formula   where   are roots of polynomial     We get

 

The fact that   should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

CitationsEdit

  1. ^ Reed & Chen 1999, p. 189
  2. ^ Hocquenghem 1959
  3. ^ Bose & Ray-Chaudhuri 1960
  4. ^ "Phobos Lander Coding System: Software and Analysis" (PDF). Retrieved 25 February 2012.
  5. ^ "Sandforce SF-2500/2600 Product Brief". Retrieved 25 February 2012.
  6. ^ Gill n.d., p. 3
  7. ^ Lidl & Pilz 1999, p. 229
  8. ^ Gorenstein, Peterson & Zierler 1960
  9. ^ Gill n.d., p. 47
  10. ^ Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa, and Toshihiko Namekawa. A method for solving key equation for decoding Goppa codes. Information and Control, 27:87–99, 1975.

ReferencesEdit

Primary sourcesEdit

Secondary sourcesEdit

Further readingEdit