BCH code

Example

Let q = 2 and m = 4 (therefore n = 15). We will consider different values of d for GF(16) = GF(2⁴) based on the reducing polynomial z⁴ + z + 1, using primitive element α(z) = z. There are fourteen minimum polynomials m_i(x) with coefficients in GF(2) satisfying

${\displaystyle m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+1\right)}}=0.}$

The minimal polynomials are

${\displaystyle {\begin{aligned}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_{11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{aligned}}}$

The BCH code with ${\displaystyle d=2,3}$ has the generator polynomial

${\displaystyle g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1.\,}$

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. It is also denoted as: (15, 11) BCH code.

The BCH code with ${\displaystyle d=4,5}$ has the generator polynomial

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x))=m_{1}(x)m_{3}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{aligned}}}$

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. It is also denoted as: (15, 7) BCH code.

The BCH code with ${\displaystyle d=6,7}$ has the generator polynomial

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{aligned}}}$

It has minimal Hamming distance at least 7 and corrects up to three errors. Since the generator polynomial is of degree 10, this code has 5 data bits and 10 checksum bits. It is also denoted as: (15, 5) BCH code. (This particular generator polynomial has a real-world application, in the "format information" of the QR code.)

The BCH code with ${\displaystyle d=8}$ and higher has the generator polynomial

${\displaystyle {\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x))=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)\left(x^{4}+x^{3}+1\right)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{aligned}}}$

This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. It is also denoted as: (15, 1) BCH code. In fact, this code has only two codewords: 000000000000000 and 111111111111111 (a trivial repetition code).

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 ${\displaystyle \lambda _{1},\lambda _{2},\dots ,\lambda _{v}}$ of a polynomial

${\displaystyle \Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.}$

Now the procedure of the Peterson–Gorenstein–Zierler algorithm.^[8] Expect we have at least 2t syndromes s_c, ..., s_c+2t−1. Let v = t.

Forney algorithm

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

Let

${\displaystyle S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2}.}$

${\displaystyle v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).}$

And the error evaluator polynomial^[9]

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}}$

Finally:

${\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

where

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

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

${\displaystyle e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

For narrow-sense BCH codes, c = 1, so the expression simplifies to:

${\displaystyle e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.}$

Explanation of Forney algorithm computation

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

Consider ${\displaystyle S(x)\Lambda (x),}$ and for the sake of simplicity suppose ${\displaystyle \lambda _{k}=0}$ for ${\displaystyle k>v,}$ and ${\displaystyle s_{k}=0}$ for ${\displaystyle k>c+d-2.}$ Then

${\displaystyle S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.}$

${\displaystyle {\begin{aligned}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1\right)\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{aligned}}}$

We want to compute unknowns ${\displaystyle e_{j},}$ and we could simplify the context by removing the ${\displaystyle \left(x\alpha ^{i_{j}}\right)^{d-1}}$ terms. This leads to the error evaluator polynomial

${\displaystyle \Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.}$

Thanks to ${\displaystyle v\leqslant d-1}$ we have

${\displaystyle \Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).}$

Thanks to ${\displaystyle \Lambda }$ (the Lagrange interpolation trick) the sum degenerates to only one summand for ${\displaystyle x=\alpha ^{-i_{k}}}$

${\displaystyle \Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

To get ${\displaystyle e_{k}}$ we just should get rid of the product. We could compute the product directly from already computed roots ${\displaystyle \alpha ^{-i_{j}}}$ of ${\displaystyle \Lambda ,}$ but we could use simpler form.

As formal derivative

${\displaystyle \Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),}$

we get again only one summand in

${\displaystyle \Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).}$

So finally

${\displaystyle e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.}$

This formula is advantageous when one computes the formal derivative of ${\displaystyle \Lambda }$ form

${\displaystyle \Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}}$

yielding:

${\displaystyle \Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},}$

where

${\displaystyle i\cdot x:=\sum _{k=1}^{i}x.}$

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 ${\displaystyle s_{i}}$ restricts error word by condition

${\displaystyle s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.}$

We could write these conditions separately or we could create polynomial

${\displaystyle S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}}$

and compare coefficients near powers ${\displaystyle 0}$ to ${\displaystyle d-2.}$

${\displaystyle S(x){\stackrel {\{0,\cdots ,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.}$

Suppose there is unreadable letter on position ${\displaystyle k_{1},}$ we could replace set of syndromes ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ by set of syndromes ${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$ defined by equation ${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.}$ Suppose for an error word all restrictions by original set ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ of syndromes hold, than

${\displaystyle t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j=0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.}$

New set of syndromes restricts error vector

${\displaystyle f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)}$

the same way the original set of syndromes restricted the error vector ${\displaystyle e_{j}.}$ Except the coordinate ${\displaystyle k_{1},}$ where we have ${\displaystyle f_{k_{1}}=0,}$ an ${\displaystyle f_{j}}$ is zero, if ${\displaystyle e_{j}=0.}$ For the goal of locating error positions we could change the set of syndromes in the similar way to reflect all unreadable characters. This shortens the set of syndromes by ${\displaystyle k.}$

In polynomial formulation, the replacement of syndromes set ${\displaystyle \{s_{c},\cdots ,s_{c+d-2}\}}$ by syndromes set ${\displaystyle \{t_{c},\cdots ,t_{c+d-3}\}}$ leads to

${\displaystyle T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0}^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.}$

Therefore,

${\displaystyle xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).}$

After replacement of ${\displaystyle S(x)}$ by ${\displaystyle S(x)\Gamma (x)}$, one would require equation for coefficients near powers ${\displaystyle k,\cdots ,d-2.}$

One could consider looking for error positions from the point of view of eliminating influence of given positions similarly as for unreadable characters. If we found ${\displaystyle v}$ positions such that eliminating their influence leads to obtaining set of syndromes consisting of all zeros, than there exists error vector with errors only on these coordinates. If ${\displaystyle \Lambda (x)}$ denotes the polynomial eliminating the influence of these coordinates, we obtain

${\displaystyle S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.}$

In Euclidean algorithm, we try to correct at most ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$ errors (on readable positions), because with bigger error count there could be more codewords in the same distance from the received word. Therefore, for ${\displaystyle \Lambda (x)}$ we are looking for, the equation must hold for coefficients near powers starting from

${\displaystyle k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .}$

In Forney formula, ${\displaystyle \Lambda (x)}$ could be multiplied by a scalar giving the same result.

It could happen that the Euclidean algorithm finds ${\displaystyle \Lambda (x)}$ of degree higher than ${\displaystyle {\tfrac {1}{2}}(d-1-k)}$ having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors could be risky (especially with no other restrictions on received word). Usually after getting ${\displaystyle \Lambda (x)}$ of higher degree, we decide not to correct the errors. Correction could fail in the case ${\displaystyle \Lambda (x)}$ has roots with higher multiplicity or the number of roots is smaller than its degree. Fail could be detected as well by Forney formula returning error outside the transmitted alphabet.

Decoding of binary code without unreadable characters

Consider a BCH code in GF(2⁴) with ${\displaystyle d=7}$ and ${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$. (This is used in QR codes.) Let the message to be transmitted be [1 1 0 1 1], or in polynomial notation, ${\displaystyle M(x)=x^{4}+x^{3}+x+1.}$ The "checksum" symbols are calculated by dividing ${\displaystyle x^{10}M(x)}$ by ${\displaystyle g(x)}$ and taking the remainder, resulting in ${\displaystyle x^{9}+x^{4}+x^{2}}$ or [ 1 0 0 0 0 1 0 1 0 0 ]. These are appended to the message, so the transmitted codeword is [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ].

Now, imagine that there are two bit-errors in the transmission, so the received codeword is [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. In polynomial notation:

${\displaystyle R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}}$

In order to correct the errors, first calculate the syndromes. Taking ${\displaystyle \alpha =0010,}$ we have ${\displaystyle s_{1}=R(\alpha ^{1})=1011,}$ ${\displaystyle s_{2}=1001,}$ ${\displaystyle s_{3}=1011,}$ ${\displaystyle s_{4}=1101,}$ ${\displaystyle s_{5}=0001,}$ and ${\displaystyle s_{6}=1001.}$ Next, apply the Peterson procedure by row-reducing the following augmented matrix.

${\displaystyle \left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_{2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001\\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}}$

Due to the zero row, S_3×3 is singular, which is no surprise since only two errors were introduced into the codeword. However, the upper-left corner of the matrix is identical to [S_2×2 | C_2×1], which gives rise to the solution ${\displaystyle \lambda _{2}=1000,}$ ${\displaystyle \lambda _{1}=1011.}$ The resulting error locator polynomial is ${\displaystyle \Lambda (x)=1000x^{2}+1011x+0001,}$ which has zeros at ${\displaystyle 0100=\alpha ^{-13}}$ and ${\displaystyle 0111=\alpha ^{-5}.}$ The exponents of ${\displaystyle \alpha }$ correspond to the error locations. There is no need to calculate the error values in this example, as the only possible value is 1.