A BCH (Bose, Ray-Chaudhuri, Hocquenghem) code is a much studied code within the study of coding theory and more specifically error-correcting codes. 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. Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected. ... In information theory and coding, an error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. ... A digital system is one that uses discrete numbers, especially binary numbers, or non-numeric symbols such as letters or icons, for input, processing, transmission, storage, or display, rather than a continuous spectrum of values (an analog system). ... Phase-shift keying (PSK) is a digital modulation scheme that conveys data by changing, or modulating, the phase of a reference signal (the carrier wave). ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ... In mathematics and computer science, a numerical digit is a symbol, e. ...

Construction

BCH codes use field theory and polynomials over finite fields. To detect errors a check polynomial can be constructed so the receiving end can detect if some errors had occurred. Field theory is a branch of mathematics which studies the properties of fields. ... In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. ...

The BCH code with designed distance δ over the field GF(q^m) is constructed by first finding a polynomial over GF(q) whose roots include δ consecutive powers of γ, some root of unity. In mathematics, the nth roots of unity or de Moivre numbers are all the complex numbers which yield 1 when raised to a given power n. ...

To construct a BCH code that can detect and correct up to two errors, we use the finite field GF(16) or . Now if α is a root of m₁(x) = x⁴ + x + 1, then m₁ is minimal for α since In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. ... In mathematics, the minimal polynomial of an object α is the monic polynomial p of least degree such that p(α)=0. ...

m₁(x) = (x - α)(x - α²)(x - α⁴)(x - α⁸)=x⁴ + x + 1.

If we wish to construct a code to correct 1 error we use m₁(x). Our codewords will be all the polynomials C(x) satisfying

C(x) ≡ 0 (mod m₁(x))

which has roots α, α², α⁴, α⁸.

This does not allow us to choose many codewords - so we look for the minimal polynomial for the missing power of α from above - α³, and then the minimal polynomial for this is

m₃(x) = x⁴ + x³ + x² + x + 1.

which has roots α³, α⁶, α¹², α²⁴=α⁹.

We take codewords having all of these as roots, so we form the polynomial

m_1,3(x) = m₁(x)m₃(x) = x⁸ + x⁷ + x⁶ + x⁴+1

and take codewords corresponding to polynomials of degree 14 such that

C(x) ≡ 0 (mod m_1,3(x))

So now C(α) = C(α²) = ... = C(α⁸) = 0. (*)

Now in GF(16) we have 15 nonzero elements, and thus our polynomial will be of degree 14 with 8 check and 7 information bits - we have 8 check bits since we have (*).

Encoding

Construct our information codeword as

(c₁₄, c₁₃, ..., c₈)

so our polynomial will be

c₁₄+c₁₃+...+c₈

Call this C_I.

We then want to find a C_R such that C_R=C_I (mod m_1,3(x))=c₇+c₆+...+c₀

So we have the following codeword to send C(x) = C_I+C_R (mod m_1,3(x)) = 0

For example, if we are to encode (1,1,0,0,1,1,0)

C_I=x¹⁴+x¹³+x¹⁰+x⁹

and using polynomial long division of m_1,3(x) and C_I to get C_R(x), in Z₂ we obtain C_R to be In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of lower degree, a generalized version of the familiar arithmetic technique called long division. ...

x³+1

So then the codeword to send is

(1,1,0,0,1,1,0, 0,0,0,0,1,0,0,1)

Decoding

BCH decoding is split into the following 4 steps

1. Calculate the 2t syndrome values, for the received vector R
2. Calculate the error locator polynomials
3. Calculate the roots of this polynomial, to get error location positions.
4. If non-binary BCH, Calculate the error values at these error locations.

The following steps are illustrated below. Suppose we receive a codeword vector r (the polynomial R(x)).

If there is no error R(α)=R(α³)=0

If there is one error, ie r=c+e_i where e_i represents the ith basis vector for R¹⁴

So then

S₁=R(α)=C(α)+αⁱ=αⁱ

S₃=R(α³)=C(α³)+(α³)ⁱ

=(αⁱ)³=S₁³

so we can recognize one error. A change in the bit position shown by α's power will aid us correct that error.

If there are two errors

r=c+e_i+e_j

then

S₁=R(α)=C(α)+αⁱ+α^j

S₃=R(α³)=C(α³)+(α³)ⁱ+(α³)^j

= (α³)ⁱ+(α³)^j

which is not the same as S₁³ so we can recognize two errors. Further algebra can aid us in correcting these two errors.

Original source (first two paragraphs) from Federal Standard 1037C Federal Standard 1037C entitled Telecommunications: Glossary of Telecommunication Terms is a U.S. Federal Standard, issued by the General Services Administration pursuant to the Federal Property and Administrative Services Act of 1949, as amended. ...

The above text has been taken from: http://bch-code.foosquare.com/

BCH Decoding algorithms

Popular decoding algorithms are,

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

Peterson Gorenstein Zierler Algorithm

Assumptions

Peterson's algorithm, is the step 2, of the generalized BCH decoding procedure. We use Peterson's algorithm, to calculate the error locator polynomial coefficients λ₁,λ₂...λ_2t of a polynomial Λ(x) = 1 + λ₁X + λ₂X² + ... + λ_2tX^2t

Now the procedure of the Peterson Gorenstein Zierler algorithm, for a given (n,k,d_min) BCH code designed to correct errors, is

Algorithm

• First generate the Matrix of 2t syndromes,
• Next generate the S_txt matrix with the elements, Syndrome values,

• Generate a c_tx1 matrix with, elements,

• Let Λ denote the unknown polynomial coefficients, which are given,using,

• Form the matrix equation

• If the determinant of matrix exists, then we can actually, find an inverse of this matrix, and solve for the values of unknown Λ values.

• If , then follow

 if t = 0 then declare an empty error locator polynomial stop Peterson procedure. end set  continue from the beginning of Peterson's decoding 

• After you have values of Λ you have with you the error locator polynomial.
• Stop Peterson procedure.

Factoring Error Locator polynomial

Now that you have Λ(x) polynomial, you can find its roots in the form Λ(x) = (αⁱX + 1)(α^jX + 1)...(α^kX + 1) using, the Chiens 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.

Correcting Errors

For the case of binary BCH, you can directly correct the received vectors, at the positions of the powers of primitive elements, of the error locator polynomial factors. Finally, just flip the bits for the received word, at these positions, and we have the corrected code word, from BCH decoding.

We may also use Berlekamp-Massey algorithm for determining the error locator polynomial, and hence solve the BCH decoding problem. The Berlekamp-Massey algorithm is a algorithm for finding the shortest linear feedback shift register (LFSR) for a given output sequence. ...

Simulation Results

Image File history File links BCH_63_36_Code_Graph2. ...

The simulation results for a AWGN BPSK system using a (63,36,5) BCH code are shown in this figure. A coding gain of almost 2 dB is observed at a bit error rate 10 ^{− 3}.

References

• S. Lin and D. Costello. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ, 2004.
• Step by step decoding instructions (pdf file).
• Federal Standard 1037c: http://federal-standard-1037c.foosquare.com/
• Galois Field Calculator: http://www.geocities.com/myopic_stargazer/gf_calc.zip
• Decoding Algorithms for BCH codes: http://students.uta.edu/mx/mxa6471/research/ecc-report.pdf
• Source code for BCH channel simulation: http://students.uta.edu/mx/mxa6471/research/ecc-code.tgz