- BCH code
In

coding theory the**BCH codes**form a class of parameterised error-correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose and Ray-Chaudhuri [*Page 189, cite book*] . The acronym "BCH" comprises the initials of these inventors' names.

last = Reed

first = Irving, S.

authorlink = Irving S. Reed

title = Error-Control Coding for Data Networks

publisher =Kluwer Academic Publishers

isbn = 0-7923-8528-4The principal advantage of BCH codes is the ease with which they can be decoded, via an elegant algebraic method known as

syndrome decoding . This allows very simple electronic hardware to perform the task, obviating the need for a computer, and meaning that a decoding device may be made small and low-powered. As a class of codes, they are also highly flexible, allowing control over block length and acceptable error thresholds, meaning that a custom code can be designed to a given specification (subject to mathematical constraints).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 multilevelphase-shift keying whenever the number of levels is aprime 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. []Federal Standard 1037C , 1996.**Construction**A BCH code is a

polynomial code over afinite field with a particularly chosen generator polynomial. It is also acyclic code .**Simplified BCH codes**For ease of exposition, we first describe a special class of BCH codes. General BCH codes are described in the next section.

**Definition.**Fix afinite field $GF(q)$, where $q$ is a prime power. Also fix positive integers $m$, $n$, and $d$ such that $n=q^m-1$ and $2\; leq\; d\; leq\; n$. We will construct apolynomial code over $GF(q)$ with code length $n$, whose minimumHamming distance is at least $d$.What remains to be specified is the generator polynomial of this code.Let $alpha$ be a primitive $n$th root of unity in $GF(q^m)$. For all $i$, let $m\_i(x)$ be the minimal polynomial of $alpha^i$ with coefficients in $GF(q)$. The generator polynomial of the BCH code is defined as the

least common multiple $g(x)\; =\; \{\; m\; lcm\}(m\_1(x),ldots,m\_\{d-1\}(x))$.**Example**Let $q=2$ and $m=4$ (therefore $n=15$). We will consider different values of $d$. There is a primitive root $alphain\; GF(16)$ satisfying :$alpha^4+alpha+1=0$ (1);its minimal polynomial over $GF(2)$ is :$m\_1(x)\; =\; x^4+x+1$. Note that in $GF(2)$, the equation $(a+b)^2\; =\; a^2\; +\; 2ab\; +\; b^2\; =\; a^2\; +\; b^2$ holds, and therefore$m\_1(alpha^2)\; =\; m\_1(alpha)^2\; =\; 0$.Thus $alpha^2$ is a root of $m\_1(x)$, and therefore :$m\_2(x)\; =\; m\_1(x)\; =\; x^4+x+1$.To compute $m\_3(x)$, notice that, by repeated application of (1), we have the following linear relations:

* $1\; =\; 0alpha^3\; +\; 0alpha^2\; +\; 0alpha\; +\; 1$

* $alpha^3\; =\; 1alpha^3\; +\; 0alpha^2\; +\; 0alpha\; +\; 0$

* $alpha^6\; =\; 1alpha^3\; +\; 1alpha^2\; +\; 0alpha\; +\; 0$

* $alpha^9\; =\; 1alpha^3\; +\; 0alpha^2\; +\; 1alpha\; +\; 0$

* $alpha^\{12\}\; =\; 1alpha^3\; +\; 1alpha^2\; +\; 1alpha\; +\; 1$Five right-hand-sides of length four must be linearly dependent, and indeed we find a linear dependency $alpha^\{12\}+alpha^9+alpha^6+alpha^3+1=0$.Since there is no smaller degree dependency, the minimal polynomial of $alpha^3$ is :$m\_3(x)\; =\; x^4+x^3+x^2+x+1$.Continuing in a similar manner, we find:$m\_4(x)\; =\; m\_2(x)\; =\; x^4+x+1,,$:$m\_5(x)\; =\; x^2+x+1,,$:$m\_6(x)\; =\; m\_3(x)\; =\; x^4+x^3+x^2+x+1,,$:$m\_7(x)\; =\; x^4+x^3+1.,$

The BCH code with $d=1,2,3$ has generator polynomial

:$d(x)\; =\; m\_1(x)\; =\; x^4+x+1.,$

It has minimal Hamming distance at least 3 and corrects up to 1 error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.

The BCH code with $d=4,5$ has generator polynomial

:$d(x)\; =\; \{\; m\; lcm\}(m\_1(x),m\_3(x))\; =\; (x^4+x+1)(1+x+x^2+x^3+x^4)\; =\; x^8+x^7+x^6+x^4+1.,$

It has minimal Hamming distance at least 5 and corrects up to 2 errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.

The BCH code with $d=6,7$ has generator polynomial

:$egin\{align\}d(x)\; \{\}\; =\; \{\; m\; lcm\}(m\_1(x),m\_3(x),m\_5(x))\; \backslash \; \{\}\; =\; (x^4+x+1)(1+x+x^2+x^3+x^4)(x^2+x+1)\; \backslash \; \{\}\; =\; x^\{10\}+x^8+x^5+x^4+x^2+x+1.end\{align\}$

It has minimal Hamming distance at least 7 and corrects up to 3 errors. This code has 5 data bits and 10 checksum bits.

The BCH code with $d=8$ and higher have generator polynomial

:$egin\{align\}d(x)\; \{\}\; =\; \{\; m\; lcm\}(m\_1(x),m\_3(x),m\_5(x),m\_7(x))\; \backslash \; \{\}\; =\; (x^4+x+1)(1+x+x^2+x^3+x^4)(x^2+x+1)(x^4+x^3+1)\; \backslash \; \{\}\; =\; x^\{14\}+x^\{13\}+x^\{12\}+cdots+x^2+x+1.end\{align\}$

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

**General BCH codes**General BCH codes differ from the simplified case discussed above in two respects. First, one replaces the requirement $n=q^m-1$ by a more general condition. Second, the consecutive roots of the generator polynomial may run from $alpha^c,ldots,alpha^\{c+d-2\}$ instead of $alpha,ldots,alpha^\{d-1\}$.

**Definition.**Fix a finite field $GF(q)$, where $q$ is a prime power. Chose positive integers $m,n,d,c$ such that $2leq\; dleq\; n$, $\{\; m\; gcd\}(n,q)=1$, and $m$ is themultiplicative order of $q$ modulo $n$.As before, let $alpha$ be a primitive $n$th root of unity in $GF(q^m)$, and let $m\_i(x)$ be the minimal polynomial over $GF(q)$ of $alpha^i$ for all $i$. The generator polynomial of the BCH code is defined as the

least common multiple $g(x)\; =\; \{\; m\; lcm\}(m\_c(x),ldots,m\_\{c+d-2\}(x))$.**Note:**if $n=q^m-1$ as in the simplified definition, then $\{\; m\; gcd\}(n,q)$ is automatically 1, and the order of $q$ modulo $n$ is automatically $m$. Therefore, the simplified definition is indeed a special case of the general one.**Properties**1. The generator polynomial of a BCH code has degree at most $(d-1)m$. Moreover, if $q=2$ and $c=1$, the generator polynomial has degree at most $dm/2$.

:Proof: each minimal polynomial $m\_i(x)$ has degree at most $m$. Therefore, the least common multiple of $d-1$ of them has degree at most $(d-1)m$. Moreover, if $q=2$, then $m\_i(x)\; =\; m\_\{2i\}(x)$ for all $i$. Therefore, $g(x)$ is the least common multiple of at most $d/2$ minimal polynomials $m\_i(x)$ for odd indices $i$, each of degree at most $m$.

2. A BCH code has minimal Hamming distance at least $d$. Proof: We only give the proof in the simplified case; the general case is similar. Suppose that $p(x)$ is a code word with fewer than $d$ non-zero terms. Then

:$p(x)\; =\; b\_1x^\{j\_1\}\; +\; cdots\; +\; b\_\{d-1\}x^\{j\_\{d-1,\; ext\{\; where\; \}j\_1\{d-1\}.\; math>$

Recall that $alpha^1,ldots,alpha^\{d-1\}$ are roots of $g(x)$, hence of $p(x)$. This implies that $b\_1,ldots,b\_\{d-1\}$ satisfy the following equations, for $i=1,ldots,d-1$::$p(alpha^i)\; =\; b\_1alpha^\{ij\_1\}\; +\; b\_2alpha^\{ij\_2\}\; +\; cdots\; +\; b\_\{d-1\}alpha^\{ij\_\{d-1\; =\; 0$.Dividing this by $alpha^\{ij\_1\}$, and writing $k\_l\; =\; j\_l\; -\; j\_1$, we get:$b\_1\; +\; b\_2alpha^\{ik\_2\}\; +\; cdots\; +\; b\_\{d-1\}alpha^\{ik\_\{d-1\; =\; 0$for all $i$, or equivalently:$egin\{bmatrix\}1\; alpha^\{k\_2\}\; cdots\; alpha^\{k\_\{d-1\; \backslash 1\; alpha^\{2k\_2\}\; cdots\; alpha^\{2k\_\{d-1\; \backslash vdots\; vdots\; vdots\; \backslash 1\; alpha^\{(d-1)k\_2\}\; cdots\; alpha^\{(d-1)k\_\{d-1\; \backslash end\{bmatrix\}egin\{bmatrix\}b\_1\; \backslash \; b\_2\; \backslash \; vdots\; \backslash \; b\_\{d-1\}end\{bmatrix\}=\; egin\{bmatrix\}0\; \backslash \; 0\; \backslash \; vdots\; \backslash \; 0end\{bmatrix\}$This matrix is seen to be a

Vandermonde matrix , and its determinant is :$det(V)\; =\; prod\_\{1le\; i\}\; (alpha^\{k\_j\}-alpha^\{k\_i\})\; math>,which\; is\; non-zero.\; It\; therefore\; follows\; that$ b\_1,ldots,b\_\{d-1\}=0$,\; hence$ p(x)=0$.$3. A BCH code is cyclic.

Proof: A polynomial code of length $n$ is cyclic if and only if its generator polynomial divides $x^n-1$. Since $g(x)$ is the minimal polynomial with roots $alpha^c,ldots,alpha^\{c+d-2\}$, it suffices to check that each of $alpha^c,ldots,alpha^\{c+d-2\}$ is a root of $x^n-1$. This follows immediately from the fact that $alpha$ is, by definition, an $n$th root of unity.

**Special cases*** A BCH code with $c=1$ is called a "narrow-sense BCH code".

* A BCH code with $n=q^m-1$ is called "primitive".Therefore, the "simplified" BCH codes we considered above were just the primitive narrow-sense codes.

* A narrow-sense BCH code with $n=q-1$ is called a "

Reed-Solomon code ".**Decoding**BCH decoding is split into the following four steps

# Calculate the 2"t" syndrome values, for the received vector "R"

# Calculate the error locator polynomials

# Calculate the roots of this polynomial, to get error location positions.

# 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(alpha)\; =\; R(alpha^3)\; =\; 0$

If there is one error (i.e. $r\; =\; c\; +\; e\_i$ where $e\_i$ represents the $i^\{th\}$

basis vector for $mathbb\{R\}^\{14\}$.So then:$S\_1\; =\; R(alpha)\; =\; C(alpha)\; +\; alpha^i\; =\; alpha^i$:$S\_3\; =\; R(alpha^3)\; =C(alpha^3)\; +\; (alpha^3)^i\; =(alpha^i)^3\; =S\_1^3$

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

If there are two errors:$r\; =\; c\; +\; e\_i\; +\; e\_k$

then

:$S\_1\; =\; R(alpha)\; =\; C(alpha)\; +\; alpha^i\; +\; alpha^k$:$S\_3\; =R(alpha^3)\; =C(alpha^3)\; +\; (alpha^3)^i\; +\; (alpha^3)^k\; =(alpha^3)^i\; +\; (alpha^3)^k$

which is

**not**the same as $S\_1^3$ 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://web.archive.org/web/20070516074824/http://bch-code.foosquare.com/ http://bch-code.foosquare.com/*]**BCH decoding algorithms**Popular decoding algorithms are,

# Peterson Gorenstein Zierler algorithm

# 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 $lambda\_1\; ,\; lambda\_2,\; dots,\; lambda\_\{t\}$of a polynomial$Lambda(x)\; =\; 1\; +\; lambda\_1\; x\; +\; lambda\_2\; x^2\; +\; cdots\; +\; lambda\_\{t\}x^\{t\}$

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

**Algorithm*** First generate the Matrix of $2t$ syndromes,

* Next generate the $S\_\{t\; imes\; t\}$ matrix with the elements, syndrome values, ::$S\_\{t\; imes\; t\}=egin\{bmatrix\}s\_1s\_2s\_3dotss\_t\backslash s\_2s\_3s\_4dotss\_\{t+1\}\backslash s\_3s\_4s\_5dotss\_\{t+2\}\backslash dotsdotsdotsdotsdots\backslash s\_ts\_\{t+1\}s\_\{t+2\}dotss\_\{2t-1\}end\{bmatrix\}$* Generate a $c\_\{tx1\}$ matrix with, elements, ::$C\_\{t\; imes\; 1\}=egin\{bmatrix\}s\_\{t+1\}\backslash s\_\{t+2\}\backslash vdots\backslash vdots\backslash s\_\{2t\}end\{bmatrix\}$

* Let $Lambda$ denote the unknown polynomial coefficients, which are given,using::$Lambda\_\{t\; imes\; 1\}\; =\; egin\{bmatrix\}lambda\_\{1\}\backslash lambda\_\{2\}\backslash lambda\_\{3\}\backslash lambda\_\{4\}\backslash vdots\backslash lambda\_\{t\}end\{bmatrix\}$

* Form the matrix equation ::$S\_\{t\; imes\; t\}\; Lambda\_\{t\; imes\; 1\}\; =\; C\_\{t\; imes\; 1,\}$

* If the determinant of matrix $S\_\{t\; imes\; t\}$ exists, then we can actually, find an inverse of this matrix, and solve for the values of unknown $Lambda$ values.

* If $det(S\_\{t\; imes\; t\})\; =\; 0$, then follow if $t\; =\; 0$ then declare an empty error locator polynomial stop Peterson procedure. end set $t\; leftarrow\; t\; -1$ continue from the beginning of Peterson's decoding

* After you have values of $Lambda$ you have with you the error locator polynomial.

* Stop Peterson procedure.**Factoring error locator polynomial**Now that you have $Lambda(x)$ polynomial, you can find its roots in the form $Lambda(x)=(alpha^i\; x\; +\; 1)\; (alpha\; ^j\; x\; +\; 1)\; cdots\; (alpha^k\; x\; +\; 1)$ using, the

Chien search algorithm. The exponentialpowers of the primitive element $alpha$, 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.**imulation results**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\}$.

**Citations****References*** S. Lin and D. Costello. Error Control Coding: Fundamentals and Applications. Prentice-Hall, Englewood Cliffs, NJ, 2004.

* Galois Field Calculator: http://www.geocities.com/myopic_stargazer/gf_calc.zip

* W.J. Gilbert and W.K. Nicholson. Modern Algebra with Applications, 2nd edition. Wiley, 2004.

* R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999.

* F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Code, New York: North-Holland Publishing Company, 1977.

* Irving S. Reed and Xuemin Chen, Error-Control Coding for Data Networks", Boston: Kluwer Academic Publishers, 1999.

*Wikimedia Foundation.
2010.*