BCH code

BCH codes (Bose-Chaudhuri-Hocquenghem codes) are cyclical error-correcting codes that are used in digital signal processing and data storage . The name BCH is derived from the first letters of the three scientists who developed this code: RC Bose , DK Ray-Chaudhuri and A. Hocquenghem (1908–1990). BCH codes correct several 1-bit errors in a longer user data word.

definition

Let be a primitive -th root of unity in an extension field of the finite field . Be , and C is the cyclic code whose generator is the product of different minimal polynomials of is. (Then C consists of all with ), then C is called a BCH code with a planned minimum distance , where C has the minimum distance . ${\ displaystyle \ beta}$ ${\ displaystyle n}$ ${\ displaystyle \ mathbb {F} _ {q}}$ ${\ displaystyle l, \ delta \ in \ mathbb {N}}$ ${\ displaystyle \ delta \ geq 2}$ ${\ displaystyle \ beta ^ {l}, \ dots, \ beta ^ {l + \ delta -2}}$ ${\ displaystyle f \ in \ mathbb {F} _ {q} [x] / (x ^ {n} -1)}$ ${\ displaystyle f (\ beta ^ {l}) = \ dots = f (\ beta ^ {l + \ delta -2}) = 0}$ ${\ displaystyle \ delta}$ ${\ displaystyle d \ geq \ delta}$

In this case , one speaks of a BCH code in the usual sense . ${\ displaystyle l = 1}$

If an m exists with (i.e. is a generator of the multiplicative group of a field ), then one speaks of a primitive BCH code. ${\ displaystyle n = q ^ {m} -1}$ ${\ displaystyle \ beta}$ ${\ displaystyle \ mathbb {F} _ {q ^ {m}}}$

A Reed-Solomon code is a primitive BCH code in the ordinary sense to which applies. So here the minimal polynomials are of the form . ${\ displaystyle n = q-1}$ ${\ displaystyle x- \ beta ^ {i} \ in \ mathbb {F} _ {q} [x], i = 1 \ ldots \ delta -1}$

Areas of application

The so-called Reed-Solomon codes are special BCH codes and are used e.g. B. used to correct errors on audio CDs .
The BCH code is also used to back up the TPS data in the DVB-T standard.
The POCSAG and FLEX paging protocols use the BCH (31,21) code

BCH (15, 7, 5)

A BCH code is given as an example . The parameters are to be interpreted as follows. The code generates code words with a length of bits , bits of which contain the coded information and bits of redundancy are used to correct transmission errors. The parameter indicates the minimum Hamming distance of the code. ${\ displaystyle (n = 15, k = 7, d_ {min} = 5)}$ ${\ displaystyle n, k, d_ {min}}$ ${\ displaystyle n = 15}$ ${\ displaystyle k = 7}$ ${\ displaystyle nk}$ ${\ displaystyle d_ {min}}$

The following applies: transmission errors of up to single bit errors can be detected, transmission errors of up to single bit errors can be corrected. Bundle errors of up to bits are recognized. ${\ displaystyle d _ {\ mathrm {min}} -1}$ ${\ displaystyle (d _ {\ mathrm {min}} -1) / 2}$ ${\ displaystyle f _ {\ mathrm {b}} \ leq k}$

A BCH code is usually described by its generator polynomial. In the example given, the generator polynomial is . The number of check bits nk can always be read from the generator polynomial. It applies . ${\ displaystyle g (x) = x ^ {8} + x ^ {7} + x ^ {6} + x ^ {4} +1}$ ${\ displaystyle nk = \ operatorname {degree} (g)}$

For the dimension of the code applies: . ${\ displaystyle dimC = n-degree (g) = 15-8 = 7 = k}$

Encode

The multiplication or division method can be used for coding with BCH codes.

Multiplication method

During the multiplication method for encoding Quellkodewort out is bits simply multiplied by the generator polynomial of the BCH code. The following applies: . Stands for the coded channel code word , stands for the uncoded source code word. The multiplication can be carried out both with polynomials and with a binary representation of the polynomials. ${\ displaystyle l = 7}$ ${\ displaystyle a (x) = a ^ {*} (x) \ cdot g (x)}$ ${\ displaystyle a (x)}$ ${\ displaystyle a ^ {*} (x)}$

Here we want to calculate an example in binary representation:

The given generator polynomial can be represented in binary as the sequence (the sequence is to be interpreted as ). ${\ displaystyle g (x) = x ^ {8} + x ^ {7} + x ^ {6} + x ^ {4} +1}$ ${\ displaystyle g = 111010001}$ ${\ displaystyle g (x) = 1 \ cdot x ^ {8} +1 \ cdot x ^ {7} +1 \ cdot x ^ {6} +0 \ cdot x ^ {5} +1 \ cdot x ^ { 4} +0 \ cdot x ^ {3} +0 \ cdot x ^ {2} +0 \ cdot x ^ {1} +1 \ cdot x ^ {0}}$

In our example, or serves as the source code word to be coded . ${\ displaystyle a ^ {*} = 1001011}$ ${\ displaystyle a ^ {*} (x) = 1 \ cdot x ^ {6} +0 \ cdot x ^ {5} +0 \ cdot x ^ {4} +1 \ cdot x ^ {3} +0 \ cdot x ^ {2} +1 \ cdot x ^ {1} +1 \ cdot x ^ {0}}$

In order to get the encoded channel codeword, we now simply have to multiply by: ${\ displaystyle a ^ {*}}$ ${\ displaystyle g}$

${\ displaystyle a = a ^ {*} \ cdot g = 1001011 \ cdot 111010001 = 111100010111011}$

Division procedure

The division method makes it possible for a given source code word to determine precisely that channel code word which has the given source code word as a prefix, which is why it is said that the method delivers a systematic code. For a given generator polynomial and a source code word , the associated channel code word is calculated using the division method as follows: ${\ displaystyle g}$ ${\ displaystyle a ^ {*}}$ ${\ displaystyle a}$

${\ displaystyle a: = a ^ {*} \ cdot x ^ {k} - \ left (a ^ {*} \ cdot x ^ {k} \ right) {\ bmod {g}}}$

That means you have to find the remainder of the polynomial division and subtract it from. Using the example from above: ${\ displaystyle \ left (a ^ {*} \ cdot x ^ {k} \ right): g}$ ${\ displaystyle a ^ {*} \ cdot x ^ {k}}$

${\ displaystyle {\ begin {array} {ccccc} g & = & x ^ {8} + x ^ {7} + x ^ {6} + x ^ {4} +1 & {\ mathrel {\ widehat {=}}} & 111010001 \\ a ^ {*} & = & x ^ {6} + x ^ {3} + x + 1 & {\ mathrel {\ widehat {=}}} & 1001011 \\ a ^ {*} \ cdot x ^ {k } & = & x ^ {14} + x ^ {11} + x ^ {9} + x ^ {8} & {\ mathrel {\ widehat {=}}} & 100101100000000 \ end {array}}}$

The division in coefficient notation is then:

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

This applies . ${\ displaystyle a = 100101100000000-01010111 = \ underbrace {1001011} _ {a ^ {*}} 01010111}$

Decode

The decoding can be done using various methods according to the following pattern:

Determination of the syndrome value (division remainder) by dividing the received channel code word by the generator polynomial . If the remainder is not equal to 0, one or more errors have occurred. ${\ displaystyle a (x)}$ ${\ displaystyle g (x)}$
Determine the error polynomial.
Determination of the zeros of the error polynomial to determine the error positions in the code word.
Determination of the error values

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

example

If the code word from the example above is transmitted without errors, the remainder of the division remains zero. The division in coefficient notation is then: ${\ displaystyle a: g}$

<!-- Berechnungen können hier nachgerechnet werden: http://www.flechtmann.net/crc/index.php -->
  100101101010111 : 111010001 = 1100111
   111010001
    001010011
     010100110
      111010001
       100111001
        111010001
         --------
         '''00000000'''

If the code word were falsified during transmission, for example to 10 1 101 01 1010111 (digits 3, 7 and 8), an error syndrome different from 0 would result after the polynomial division:

  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 .