BCH Codes

We are now ready to define single error-correcting BCH codes. In fact, it can be proven thata single error-correcting BCH code is isomorphic to a Hamming Code, which is a single error correcting linear code. Further, we will assume know that the codelength $n=2^m-1$, so we have what is considered a primitive BCH code. In this way, we will better be able to decode single errors.

We want to construct codes of length $n$ over a finite field $\mathbb{F}$. Start by factoring $x^n-1$ into irreducibles over $\mathbb{F}$.

$$f(x)=f_1(x)f_2(x)...f_k(x)$$

If $x^n-1$ is not seperable in $\mathbb{F}$, extend $\mathbb{F}$ to $\ensuremath{\mathbb{F}}'$ and write

$$x^n-1=(x-1)(x-\alpha)(a-\alpha^2)...(x-\alpha^{n-1})$$

where $\{\alpha^k\}$ are the $n$ distinct roots of unity in the extension of $\mathbb{F}$. Each of the powers of $\alpha$ is also a root of some $f_i(x)$. Then for each $\alpha^i$, define $q_i(x)$ to be the polynomial $f_k(x)$ such that $f_k(\alpha)=0.$ Notice that each of the $q_i(x)$ are the minimal polynomials for $\alpha^i$ and that they need not be distinct. This follows since $\alpha^i$ and $\alpha^j$ may have the same minimal polynomial.

Definition 10   A BCH code of length $n$ with designed distance $d$ is a code with generating polynomial

$$g(x)=\;\textnormal{lcm}\;\bigg(q_{k+1}(x),q_{k+2}(x),...,q_{k+d-1}(x)\bigg)$$

for some integer $k$.

Here is an example of finding a generating polynomial for such a code. Let $\ensuremath{\mathbb{F}}=\ensuremath{\mathbb{Z}}_5$ and let $n=4$. We start by factoring $x^4-1$ over $\ensuremath{\mathbb{Z}}_5$ to get

$$x^4-1\equiv\;(x-1)(x-2)(x-3)(x-4)$$

Then of all the roots $\{1,2,3,4\}$ we must determine which is a primitive $4^{th}$ root of unity. That means there is some element such that $\alpha^4=1$ and $\alpha^k\ne 1$ for $1\le k<4$. The root 2 satisfies this condition. Let $\alpha=2$. Thus the $q_i(x)$ are labeled as follows

$$q_0(x)=x-1\;\;\;\;\;q_1(x)=x-2\;\;\;\;\;q_2(x)=x-4\;\;\;\;q_3(x)=x-3$$

since

$$q_0(\alpha^0)=0\;\;\;\;q_1(\alpha^1)=0\;\;\;\; q_2(\alpha^2)=0\;\;\;\;q_3(\alpha^3)=0$$

Now suppose we were looking for a code of distance $3$. We can choose $k$ arbitrarlily, so let $k=0$. So the generating polynomial of $C$ is

$$g(x)=$$lcm$$\;\bigg(q_{0+1}(x),q_{0+2}(x)\bigg)=(x-2)(x-4)$$

or

$$g(x)=x^2+4x+3$$

Then the first row of the generating matrix is the row vector

$$(3,4,1,0)$$

Because we have defined a BCH code to be cyclic we get the complete generating matrix from cyclic shifts of the generating code vector.

$$\left(\begin{array}{cccc} 3&4&1&0\\ 0&3&4&1\\ \end{array}\right)$$

which is a cyclic $[4,2]$ code.

We now must prove that this BCH code has minimum weight at least $d$.

Theorem 6   A BCH code of designed distance $d$ has minimum weight at least $d$

Proof. Since $q_j(x)$ divides $g(x)$ for $k+1\le j\le k+d-1$, and $q_j(\alpha^j)=0$, we have

$$g(\alpha^{k+1})=g(\alpha^{k+2})=...=g(\alpha^{k+d-1})=0$$

Letting $l=k+1$ and $\delta=d-2$, theorem 4 thus gaurantees that the minimum weight is at least $d=\delta+2$.
$\qedsymbol$

In the previous example the weight of the first row vector was 3, and since it is a cyclic code we know that the minumum weight is exactly 3. So theorem 4 tells us the exact minimum weight since $\delta=d-2=1$.

One of the advantages of this type of code is that there is a relatively simple way to decode.

Let $C$ be a BCH code with designed distance $d\ge 3$. Then $C$ is a cyclic code of some length $n$ with a generating polynomial $g(x)$. By Theorem 5, there is a an $\alpha$ such that

$$g(\alpha^{k+1})=g(\alpha^{k+2})=0$$

for some integer $k$.

Let

$$H=\left(\begin{array}{ccccc} 1&\alpha^{k+1}&\alpha^{2(k+1)}&...&\... ... 1&\alpha^{k+2}&\alpha^{2(k+2)}&...&\alpha^{(n-1)(k+2)}\\ \end{array}\right)$$

be a $2\times n$ Vandermonde matrix. Here is where the nice structure of cyclic codes comes into play. If $m(x)=c_0+c_1x+...+c_{n-1}x^{n-1}$ corresponds to a codeword in $C$ we know that $m(x)=g(x)h(x)$ and so

$$m(\alpha^{k+1})=m(\alpha^{k+2})=0$$

Because a Vandermonde matrix can easily be used in the technique of polynomial interpolation we can solve the following linear system

$$cH^T=(c_0,c_1,...,c_{n-1})\left(\begin{array}{cc} 1&1\\ \alpha^... ...s&\vdots\\ \alpha^{(n-1)(k+1)}&\alpha^{(n-1)(k+2)}\\ \end{array}\right) =0$$

Therefore, any codeword received without an error will be a solution to this system. If a codeword is received with a single error it will not be a solution to the system. A received message with more than one error could be a solution since parity could still exists and the null space of the matrix may properly contain the codespace of $C$. Here is how the system can correct the single error.

Assume that a message $r$ is received with $r=c+e$ where $e=(0,0,...,1,...,0,0)$. Write $rH^T=(s_1,s_2)$ which is the syndrome as previously defined.

$$rH^T=(c+e)\left(\begin{array}{cc} 1&1\\ \alpha^{k+1}&\alpha^{k+... ...vdots&\vdots\\ \alpha^{(n-1)(k+1)}&\alpha^{(n-1)(k+2)}\\ \end{array}\right)$$

Thus

$$s_1 = r\cdot \bigg(1,\alpha^{k+1},\alpha^{2(k+1)},...,\alpha^{(n-1)(k+1)}\bigg)^T$$

$$= (c+e)\cdot \bigg(1,\alpha^{k+1},\alpha^{2(k+1)},...,\alpha^{(n-1)(k+1)}\bigg)^T$$

$$= c\cdot \bigg(1,\alpha^{k+1},\alpha^{2(k+1)},...,\alpha^{(n-1)(k+1)}\bigg)^T+$$

$$e\cdot \bigg(1,\alpha^{k+1},\alpha^{2(k+1)},...,\alpha^{(n-1)(k+1)}\bigg)^T$$

$$= e\cdot \bigg(1,\alpha^{k+1},\alpha^{2(k+1)},...,\alpha^{(n-1)(k+1)}\bigg)^T$$

because the inner product of any code vector with $H^T$ equals zero. Similarly,

$$s_2=e\cdot \bigg(1,\alpha^{k+2},\alpha^{2(k+2)},...,\alpha^{(n-1)(k+2)}\bigg)^T$$

Since the error vector has only a single nonzero entry in the $j$th spot, we know that

$$s_1=\alpha^{(j-1)(k+1)}\;\;$$and$$\;\;s_2=\alpha^{(j-1)(k+2)}$$

So the error is in the $j$th entry and is the $j-1$st power of the $n$th root of unity $\alpha$.

If we are working over the binary field $\ensuremath{\mathbb{Z}}_2$ then we are done because we know that $e_j=1$. Simply change the $j$th entry in the message $r$ from zero to one, or one to zero.. Now what if we are working over another finite field?

Then $e_j$ is still the $j-1$st power of $\alpha$. We then know that the error vector is

$$e=(0,0,...,\alpha^{j-1},...,0)$$

and we can subtract this error vecor from the received codeword $r$ to get the original codeword $c$.

What about correcting multiple errors? Lets first consider a double-error correcting code.