Arikah Map

BCH code

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.


Contents

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.

The BCH code with designed distance δ over the field GF(qm) is constructed by first finding a polynomial over GF(q) whose roots include δ consecutive powers of γ, some root of unity.

To construct a BCH code that can detect and correct up to two errors, we use the finite field GF(16) or <math>\mathbb{Z}_2[x]/ \left \langle x^4+x+1 \right \rangle </math>. Now if α is a root of m1(x) = x4 + x + 1, then m1 is minimal for α since

m1(x) = (x - α)(x - α2)(x - α4)(x - α8)=x4 + x + 1.

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

0 ≡ C(x) (mod m1(x))

which has roots α, α2, α4, α8.

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

m3(x) = x4 + x3 + x2 + x + 1.

which has roots α3, α6, α12, α24=α9.

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

m1,3(x) = m1(x)m3(x) = x8 + x7 + x6 + x4+1

and take codewords corresponding to polynomials of degree 14 such that

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

So now C(α) = C(α2) = ... = C(α8) = 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

(c14, c13, ..., c8)

so our polynomial will be

c14+c13+...+c8

Call this CI.

We then want to find a CR such thatCR=CI (mod m1,3(x))=c7+c6+...+c0

So we have the following codeword to sendC(x) = CI+CR (mod m1,3(x)) = 0

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

CI=x14+x13+x10+x9

and using polynomial long division of m1,3(x) and CI to get CR(x), in Z2 we obtain CR to be

x3+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(α3)=0

If there is one error, ie r=c+ei where ei represents the ith basis vector for R14

So then

S1=R(α)=C(α)+αi=αi
S3=R(α3)=C(α3)+(α3)i
=(αi)3=S13

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+ei+ej

then

S1=R(α)=C(α)+αi+αj
S3=R(α3)=C(α3)+(α3)i+(α3)j
= (α3)i+(α3)j

which is not the same as S13 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

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 <math> \lambda_1 , \lambda_2 ... \lambda_{2t} </math>of a polynomial<math> \Lambda(x) = 1 + \lambda_1 X + \lambda_2 X^2 + ... + \lambda_{2t}X^{2t} </math>

Now the procedure of the Peterson Gorenstein Zierler algorithm, for a given <math>(n,k,d_{min}) </math> BCH codedesigned to correct <math>[t=\frac{d_{min}-1}{2}]</math> errors, is

Algorithm

<math>S_{t \times t}=\begin{bmatrix}s_1&s_2&s_3&...&s_t\\s_2&s_3&s_4&...&s_{t+1}\\s_3&s_4&s_5&...&s_{t+2}\\...&...&...&...&...\\s_t&s_{t+1}&s_{t+2}&...&s_{2t-1}\end{bmatrix}</math>

<math>C_{t \times 1}=\begin{bmatrix}s_{t+1}\\s_{t+2}\\...\\...\\s_{2t}\end{bmatrix}</math>

<math>\Lambda_{t \times 1} = \begin{bmatrix}\lambda_{1}\\\lambda_{2}\\\lambda_{3}\\\lambda_{4}\\...\\\lambda_{t}\end{bmatrix}</math>

<math>S_{t \times t} \Lambda_{t \times 1} = C_{t \times 1} </math>


       if <math>t = 0</math>       then             declare an empty error locator polynomial             stop Peterson procedure.       end       set <math> t \leftarrow t -1</math>       continue from the beginning of Peterson's decoding

Factoring Error Locator polynomial

Now that you have <math>\Lambda(x)</math> polynomial, you can find its roots in the form <math>\Lambda(x)=(\alpha^i X + 1) (\alpha ^j X + 1) ... (\alpha^k X + 1)</math> using, the Chiens search algorithm. The exponentialpowers of the primitive element <math>\alpha</math>, will yield the positions where errors occur in the receivedword; 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.

Simulation Results

BCH code:Image:BCH_63_36_Code_Graph2.png

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 <math>10^{-3}</math>.

References

Categories


Error detection and correction | Finite fields

Find

Find

Find