BCH-Code

BCH code ( Bose - Chaudhuri - Hocquenghem ) error correcting codes are cyclic, which are employed in digital signal processing and data storage. The name BCH results from the initial letters of the three scientists who have developed this code: RC Bose, DK Ray - Chaudhuri Hocquenghem and A.. BCH codes correct number of 1- bit error in a longer user data word.

Definition

Let be a primitive root of unity in an extension field of the finite field. Be, and C is the cyclic code generator polynomial is the product of the various minimal polynomials. ( Then there is C so from all with ), then we say that C is a BCH code with planned minimum distance, where C has the minimum distance.

In case one speaks of a BCH code in the ordinary sense.

If an m exists with (ie, is a generator of the multiplicative group of a field ), then one speaks of a primitive BCH code.

A Reed- Solomon code is a primitive BCH code in the ordinary sense, is considered for the. Here, the minimal polynomials are therefore of the shape.

Areas of application

  • The so-called Reed -Solomon codes are special BCH codes and are used for example for error correction on audio CDs.
  • The BCH code is used for the securing of the TPS data of the DVB -T standard.

BCH (15, 7, 5)

As an example, a (n = 15, L = 7, dmin = 5 ) where BCH code. The parameters n, l, d min are to be interpreted as follows. The code generated code words of length n = 15 bits, of which l = 7 bits contain the encoded information and k = n - l bits of redundancy for the correction of transmission errors serve. The parameter dmin is the minimum Hammingsdistanz the code.

The rule is: There can be up to detect single-bit transmission error, it can be corrected to single-bit transmission errors of up. Burst errors of up to bits are detected.

A BCH code is usually described by its generator polynomial. In the given example is the generator polynomial. The number of check bits k can always be found reading from the generator. It is true.

Encode

For encoding BCH codes, the multiplication or the division method can be used.

Multiplication method

When multiplication method to be coded Quellkodewort from l = 7 bits is simply multiplied by the generator polynomial of the BCH codes. The rule is:. This is a (x) for the encoded Kanalkodewort, a * (x) represents the uncoded Quellkodewort. The multiplication can be performed with both polynomials as well as a binary representation of the polynomials.

Here we want to give a diagrammatic example in binary representation:

The given generator polynomial can be binary as the result represent ( the result is to be interpreted here as ).

As to be encoded Quellkodewort used in our example, or.

In order to obtain the encoded Kanalkodewort, we just need to now so a * multiply by g:

Division method

The division method makes it possible to accurately identify a given Quellkodewort that Kanalkodewort which has the given Quellkodewort as a prefix, which is why it is said that the method provides a systematic code. For a given generator polynomial and a Quellkodewort is used to calculate the associated Kanalkodewort by division method as follows:

That is, one must determine the remainder of the polynomial division and subtract this from. Using the example from above:

The division into coefficient notation is then:

100101100000000: 111010001 = 1100111    111111010     001010110      010101100       101011000        100010010         110000110          --------          01010111 This applies.

Decode

The decoding can be carried out according to the following pattern by various methods:

Conventional algorithms for decoding of BCH codes are the Berlekamp -Massey algorithm, or Peterson - Gorenstein - Zierler algorithm.

Example

If the code word is transmitted from the above example, without any error, a remainder of the division is zero. The division into coefficient notation is then:

100101101010111: 111010001 = 1100111    111010001     001010011      010100110       111010001        100111001         111010001          --------          00000000 If the codeword corrupted during transmission, for example, 101101011010111 ( points 3, 7 and 8), is given by the polynomial a different from 0 error syndrome:

101101011010111: 111010001 = 1111100    101110100     101001011      100110100       111001011        000110101         001101011          --------          01101001 literature

  • Shu Lin, Daniel J. Costello: Error Control Coding. Fundamentals and applications. 2nd edition. Prentice Hall, Upper Saddle River NJ 2004, ISBN 0-13-042672-5.
  • Robert H. Morelos - Zaragoza: The Art of Error Correcting Coding. 2nd edition. Wiley, New York, NY 2006, ISBN 0-470-01558-6.
  • Theoretical computer science
  • Coding Theory
Dijen K. Ray-Chaudhuri Minimal polynomial (linear algebra) Berlekamp–Massey algorithm
110391
de