# BCH code

In coding theory, the BCH codes form a class of cyclic error-correcting codes that are constructed using finite fields. BCH codes were invented in 1959 by French mathematician Alexis Hocquenghem, and independently in 1960 by Raj Bose and D. K. Ray-Chaudhuri. The acronym BCH comprises the initials of these inventors' names.

One of the key features of BCH codes is that during code design, there is a precise control over the number of symbol errors correctable by the code. In particular, it is possible to design binary BCH codes that can correct multiple bit errors. Another advantage of BCH codes is the ease with which they can be decoded, namely, via an algebraic method known as syndrome decoding. This simplifies the design of the decoder for these codes, using small low-power electronic hardware.

BCH codes are used in applications such as satellite communications, compact disc players, DVDs, disk drives, solid-state drives and two-dimensional bar codes.

## Definition and illustration

### Primitive narrow-sense BCH codes

Given a prime power Template:Mvar and positive integers Template:Mvar and Template:Mvar with dqm − 1, a primitive narrow-sense BCH code over the finite field GF(q) with code length n = qm − 1 and distance at least Template:Mvar is constructed by the following method.

Let Template:Mvar be a primitive element of GF(qm). For any positive integer Template:Mvar, let mi(x) be the minimal polynomial of αi over GF(q). The generator polynomial of the BCH code is defined as the least common multiple g(x) = lcm(m1(x),…,md − 1(x)). It can be seen that g(x) is a polynomial with coefficients in GF(q) and divides xn − 1. Therefore, the polynomial code defined by g(x) is a cyclic code.

#### Example

Let q=2 and m=4 (therefore n=15). We will consider different values of Template:Mvar. There is a primitive root α in GF(16) satisfying

Template:NumBlk

its minimal polynomial over GF(2) is

$m_{1}(x)=x^{4}+x+1.$ The minimal polynomials of the first seven powers of α are

$m_{1}(x)=m_{2}(x)=m_{4}(x)=x^{4}+x+1,\,$ $m_{3}(x)=m_{6}(x)=x^{4}+x^{3}+x^{2}+x+1,\,$ $m_{5}(x)=x^{2}+x+1,\,$ $m_{7}(x)=x^{4}+x^{3}+1.\,$ The BCH code with $d=2,3$ has generator polynomial

It has minimal Hamming distance at least 3 and corrects up to one 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

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

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

This code has minimal Hamming distance 15 and corrects 7 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 primitive narrow-sense BCH codes in two respects.

### Special cases

The generator polynomial $g(x)$ of a BCH code has coefficients from $\mathrm {GF} (q).$ In general, a cyclic code over $\mathrm {GF} (q^{p})$ with $g(x)$ as the generator polynomial is called a BCH code over $\mathrm {GF} (q^{p}).$ The BCH code over $\mathrm {GF} (q^{m})$ with $g(x)$ as the generator polynomial is called a Reed–Solomon code. In other words, a Reed–Solomon code is a BCH code where the decoder alphabet is the same as the channel alphabet.

## Properties

Proof: each minimal polynomial $m_{i}(x)$ has degree at most $m.$ $p(x)=b_{1}x^{k_{1}}+\cdots +b_{d-1}x^{k_{d-1}},{\text{ where }}k_{1} $p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.$ In matrix form, we have

${\begin{bmatrix}\alpha ^{ck_{1}}&\alpha ^{ck_{2}}&\cdots &\alpha ^{ck_{d-1}}\\\alpha ^{(c+1)k_{1}}&\alpha ^{(c+1)k_{2}}&\cdots &\alpha ^{(c+1)k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(c+d-2)k_{1}}&\alpha ^{(c+d-2)k_{2}}&\cdots &\alpha ^{(c+d-2)k_{d-1}}\\\end{bmatrix}}{\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{d-1}\end{bmatrix}}={\begin{bmatrix}0\\0\\\vdots \\0\end{bmatrix}}.$ The determinant of this matrix equals

$\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det {\begin{pmatrix}1&1&\cdots &1\\\alpha ^{k_{1}}&\alpha ^{k_{2}}&\cdots &\alpha ^{k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(d-2)k_{1}}&\alpha ^{(d-2)k_{2}}&\cdots &\alpha ^{(d-2)k_{d-1}}\\\end{pmatrix}}=\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det(V).$ The matrix $V$ is seen to be a Vandermonde matrix, and its determinant is

$\det(V)=\prod _{1\leq i 3. A BCH code is cyclic.

## Decoding

There are many algorithms for decoding BCH codes. The most common ones follow this general outline:

1. Calculate the syndromes sj for the received vector
2. Determine the number of errors t and the error locator polynomial Λ(x) from the syndromes
3. Calculate the roots of the error location polynomial to find the error locations Xi
4. Calculate the error values Yi at those error locations
5. Correct the errors

During some of these steps, the decoding algorithm may determine that the received vector has too many errors and cannot be corrected. For example, if an appropriate value of t is not found, then the correction would fail. In a truncated (not primitive) code, an error location may be out of range. If the received vector has more errors than the code can correct, the decoder may unknowingly produce an apparently valid message that is not the one that was sent.

### Calculate the syndromes

$s_{j}=R(\alpha ^{j})=C(\alpha ^{j})+E(\alpha ^{j})$ If there is no error, $s_{j}=0$ for all $j.$ If the syndromes are all zero, then the decoding is done.

### Calculate the error location polynomial

If there are nonzero syndromes, then there are errors. The decoder needs to figure out how many errors and the location of those errors.

If there is a single error, write this as $E(x)=e\,x^{i},$ where $i$ is the location of the error and $e$ is its magnitude. Then the first two syndromes are

$s_{c}=e\,\alpha ^{c\,i}$ $s_{c+1}=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}$ so together they allow us to calculate $e$ and provide some information about $i$ (completely determining it in the case of Reed–Solomon codes).

If there are two or more errors,

$E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,$ It is not immediately obvious how to begin solving the resulting syndromes for the unknowns $e_{k}$ and $i_{k}.$ First step is finding locator polynomial

$\Lambda (x)=\prod _{j=1}^{t}(x\alpha ^{i_{j}}-1)$ compatible with computed syndromes and with minimal possible $t.$ Two popular algorithms for this task are:

#### Peterson–Gorenstein–Zierler algorithm

Peterson's algorithm is the step 2 of the generalized BCH decoding procedure. Peterson's algorithm is used to calculate the error locator polynomial coefficients $\lambda _{1},\lambda _{2},\dots ,\lambda _{v}$ of a polynomial

$\Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.$ Now the procedure of the Peterson–Gorenstein–Zierler algorithm. Expect we have at least 2t syndromes sc,...,sc+2t−1. Let v = t.

$S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.$ $C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.$ $\Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.$ • Form the matrix equation
$S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.$ if $v=0$ then
declare an empty error locator polynomial
stop Peterson procedure.
end
set $v\leftarrow v-1$ continue from the beginning of Peterson's decoding by making smaller $S_{v\times v}$ ### Factor error locator polynomial

Now that you have the $\Lambda (x)$ polynomial, its roots can be found in the form $\Lambda (x)=(\alpha ^{i_{1}}x-1)(\alpha ^{i_{2}}x-1)\cdots (\alpha ^{i_{v}}x-1)$ by brute force for example using the Chien search algorithm. The exponential powers of the primitive element $\alpha$ will yield the positions where errors occur in the received word; hence the name 'error locator' polynomial.

The zeros of Λ(x) are αi1, ..., αiv.

### Calculate error values

Once the error locations are known, the next step is to determine the error values at those locations. The error values are then used to correct the received values at those locations to recover the original codeword.

For the case of binary BCH, (with all characters readable) this is trivial; just flip the bits for the received word at these positions, and we have the corrected code word. In the more general case, the error weights $e_{j}$ can be determined by solving the linear system

{\begin{aligned}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \\&{}\ \vdots \end{aligned}} #### Forney algorithm

However, there is a more efficient method known as the Forney algorithm.

Than if syndromes could be explained by an error word, which could be nonzero only on positions $i_{k}$ , then error values are

$e_{k}=-{\alpha ^{i_{k}}\Omega (\alpha ^{-i_{k}}) \over \alpha ^{c\cdot i_{k}}\Lambda '(\alpha ^{-i_{k}})}.$ For narrow-sense BCH codes, c = 1, so the expression simplifies to:

$e_{k}=-{\Omega (\alpha ^{-i_{k}}) \over \Lambda '(\alpha ^{-i_{k}})}.$ #### Explanation of Forney algorithm computation

It is based on Lagrange interpolation and techniques of generating functions.

$S(x)=\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}=\sum _{j=1}^{v}e_{j}\alpha ^{c\,i_{j}}\sum _{i=0}^{d-2}(\alpha ^{i_{j}})^{i}x^{i}=\sum _{j=1}^{v}e_{j}\alpha ^{c\,i_{j}}{(x\alpha ^{i_{j}})^{d-1}-1 \over x\alpha ^{i_{j}}-1}.$ $S(x)\Lambda (x)=S(x)\lambda _{0}\prod _{\ell =1}^{v}(\alpha ^{i_{\ell }}x-1)=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{c\,i_{j}}{(x\alpha ^{i_{j}})^{d-1}-1 \over x\alpha ^{i_{j}}-1}\prod _{\ell =1}^{v}(\alpha ^{i_{\ell }}x-1).$ We could gain form of polynomial:

$S(x)\Lambda (x)=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{c\,i_{j}}((x\alpha ^{i_{j}})^{d-1}-1)\prod _{\ell \in \{1,\dots ,v\}\setminus \{j\}}(\alpha ^{i_{\ell }}x-1).$ We want to compute unknowns $e_{j},$ and we could simplify the context by removing the $(x\alpha ^{i_{j}})^{d-1}$ terms. This leads to the error evaluator polynomial

$\Omega (x)=S(x)\,\Lambda (x){\pmod {x^{d-1}}}.$ $\Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{c\,i_{j}}\prod _{\ell \in \{1,\dots ,v\}\setminus \{j\}}(\alpha ^{i_{\ell }}x-1).$ Look at $\Omega (\alpha ^{-i_{k}}).$ Thanks to $\Lambda$ (the Lagrange interpolation trick) the sum degenerates to only one summand

$\Omega (\alpha ^{-i_{k}})=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\dots ,v\}\setminus \{k\}}(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1).$ To get $e_{k}$ we just should get rid of the product. We could compute the product directly from already computed roots $\alpha ^{-i_{j}}$ of $\Lambda ,$ but we could use simpler form.

$\Lambda '(\alpha ^{-i_{k}})=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\dots ,v\}\setminus \{k\}}(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1).$ So finally

$e_{k}=-{\alpha ^{i_{k}}\Omega (\alpha ^{-i_{k}}) \over \alpha ^{c\cdot i_{k}}\Lambda '(\alpha ^{-i_{k}})}.$ This formula is advantageous when one computes the formal derivative of $\Lambda$ form its $\Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}$ form, gaining

$\Lambda '(x)=\Sigma _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},$ ### Decoding based on extended Euclidean algorithm

The process of finding both the polynomial Λ and the error values could be based on the Extended Euclidean algorithm. Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let $k_{1},...,k_{k}$ be positions of unreadable characters. One creates polynomial localising these positions $\Gamma (x)=\prod _{i=1}^{k}(x\alpha ^{k_{i}}-1).$ Set values on unreadable positions to 0 and compute the syndromes.

As we have already defined for the Forney formula let $S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.$ The main advantage of the algorithm is that it meanwhile computes $\Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)$ required in the Forney formula.

#### Explanation of the decoding process

The goal is to find a codeword which differs from the received word minimally as possible on readable positions. When expressing the received word as a sum of nearest codeword and error word, we are trying to find error word with minimal number of non-zeros on readable positions. Syndrom $s_{i}$ restricts error word by condition $s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.$ We could write these conditions separately or we could create polynomial $S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}$ and compare coefficients near powers $0$ to $d-2.$ $S(x){\textstyle {\{0,\ldots ,\,d-2\} \atop =}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.$ In polynomial formulation, the replacement of syndromes set