Linear and Cyclic Codes

Cyclic codes fall under the category of codes called linear codes.

Definition 6   A linear code of dimension $k$ and length $n$ over a field $\mathbb{F}$ is a $k$-dimensional subspace of $\ensuremath{\mathbb{F}}^n$. Such a code is called an $[n,k]$ code. If the minumum distance of the code is $d$, then the code is called an $[n,k,d]$ code.

The row-space of the following matrix forms a $[7,3,4]$ code.

$$\left(\begin{array}{ccccccc} 1&0&1&1&1&0&0\\ 0&1&0&1&1&1&0\\ 0&0&1&0&1&1&1\\ \end{array}\right)$$

Notice that there are 4 ones in each row.

Any binary n-vector can be thought of as the coeffiecients of an $nth$ degree polynomial in $\ensuremath{\mathbb{Z}}_2$. Looking at the first row in the matrix we can relate it to the polynomial

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

in the polynomial ring $\ensuremath{\mathbb{Z}}_2[x]$.

Given a linear code the following proposition is clear.

Proposition 1   Let $C$ be a linear code. Then $d(C)$ equals the smallest Hammming weight of all nonzero code vectors.

There are many different varieties of linear codes, such as the well known Hamming codes. We now want to consider a brand of linear codes called cyclic codes. Then we will define BCH codes, which are a specific type of cyclic code.

Definition 7   A linear code $C$ is called cyclic if

$$(c_1,c_2,...,c_n)\in C\;$$implies$$\;(c_n,c_1,c-2,...,c_{n-1})\in C$$

For example, if $(1,1,1,0,1,0)$ is in a cyclic code, then $(0,1,1,1,0,1)$ is also in the code. The definition is recursive and so every cyclic shift of the elements is in the code.

In order to formalize the discussion we can use the following isomorphism

$$(a_0,a_1,...,a_{n-1})\in\ensuremath{\mathbb{F}}^n_q\rightleftharpoons a_0+a_1x+...+a_{n-1}x^{n-1}\in\ensuremath{\mathbb{F}}_q[x]$$

between the $n$-dimensional vector space $\ensuremath{\mathbb{F}}^{n}_q$ and the residue class of polynomials $\ensuremath{\mathbb{F}}_q[x]/(x^n-1)$. Recall from algebra that

$$\ensuremath{\mathbb{F}}_q[x]/(x^n-1)=\bigg\{a_0+a_1x+...+a_{n-1}x^{n-1}\;\vert\; a_i\in\ensuremath{\mathbb{F}}_q,0\le i<n\bigg\}$$

We can now speak of codewords in $C$ as the polynomials $c(x)\in\ensuremath{\mathbb{F}}_q[x]/(x^n-1)$, and the following theorem follows

Theorem 2   A linear code $C$ in $\ensuremath{\mathbb{F}}^n_q$ is a cyclic code iff $C$ is an ideal in $\ensuremath{\mathbb{F}}_q[x]/(x^n-1)$.

Proof. $\big(\Longrightarrow\big)$ If $C$ is an ideal in $\ensuremath{\mathbb{F}}_q[x]/(x^n-1)$ and $c(x)=c_0+c_1x+c_{n-1}x^{n-1}$ is any codeword, then $xc(x)$ is also a codeword. Thus

$$(c_{n-1},c_0,c-1,...,c_{n-2})\in C$$

$\big(\Longleftarrow\big)$ If $C$ is cyclic, then for every codeword $c(x)$ the word $xc(x)$ is also a codeword. Therefore $x^ic(x)$ is in $C$ for every $i$, and since $C$ is linear $a(x)c(x)$ is in $C$ for every polynomial $a(x)$. It follows that $C$ is an ideal.
$\qedsymbol$

The next theorem states the general structure of cyclic codes.

Theorem 3   Let $C$ be a cyclic code of length $n$ over a finite field $\mathbb{F}$. To each codeword $(a_0,a_1,...,a_n-1)\in C$, associate the polynomial $a_0+a_1x+...+a_{n-1}x^{n-1}$ in $\ensuremath{\mathbb{F}}[x]$. Among all the nonzero polynomials obtained from $C$ in this way, let $g(x)$ have the smallest degree. We may assume that $g(x)$ is monic. This polynomial is called the generating polynomial for $C$. Then

1.$g(x)$ is uniquely determined by $C$.

2.$g(x)$ is a divisor of $x^n-1$.

3.$C$ is exactly the set of coefficients of the polynomials of the form
$g(x)f(x)$ with deg $(f)\le n-1$.

4. Write $x^n-1=g(x)h(x)$. Then $m(x)\in\ensuremath{\mathbb{F}}[x]/(x^n-1)$ corresponds
to an element of $C$ iff $h(x)m(x)\equiv 0 \;mod(x^n-1)$.

Proof. (1)The codespace is spanned by the rows of a matrix. Because the row space of the matrix is closed under subtraction the difference between any two vectors, or polynomials, in the space is still in the space. So if there was another monic generating polynomial $g_1(x)$ with minimum degree, then $g(x)-g_1(x)$ is also in the space. But this is a contradiction since this new polynomial has smaller degree than both $g(x)$ and $g_1(x)$.

(2)Divide $g(x)$ into $x^n-1$. By the division algorithm we get

$$x^n-1=g(x)h(x)+r(x)\;\Longrightarrow\; -r(x)\equiv\;g(x)h(x)\;$$mod$$(x^n-1)$$

where deg$r(x)<$deg$g(x)$.

But multipying $g(x)$ by powers of $x$ corresponds to a cyclic shift of the corresponding code vector and multiplication by a polynomial is thus a linear combination of the codevectors in the generating matrix and all of their cyclic shifts. So $r(x)$ is in the code space of $C$. Since deg$r(x)<$deg$g(x)$, $r(x)$ must be equal to zero. Thus $g(x)\mid x^n-1$. Notice then that $\ensuremath{\mathbb{F}}[x]/(x^n-1)$ is not a field since it has zero divisors.

(3)Let $m(x)$ correspond to an element in $C$. Divide $g(x)$ into $m(x)$

$$m(x)=g(x)f(x)+r_1(x)$$

with deg$r(x)<$deg$g(x)$. From (2) we know that $g(x)f(x)$ corresponds to a codeword and by assumption so does $m(x)$. So, since $C$ is closed under subtraction, $m(x)-g(x)f(x)$mod$(x^n-1)$ is also a codeword. But this is just $r_1(x)$ and has degree less than $g(x)$. It follows that $r_1(x)\equiv\;0$ and $m(x)$ is the product of the generating polynomial with another polynomial. Because each codeword has length $n$, deg $m(x)\le n-1$ so deg $f(x)\le n-1-$deg$g(x)$. Conversely, we have shown that the product of any two polynomials $g(x)f(x)$ is in $C$. Thus, these polynomials yield all of the code words of $C$.

(4)By (2) we can write $x^n-1=g(x)h(x)$. Let $m(x)$ correspond to an element in $C$. Then by (3)

$$h(x)m(x)=h(x)g(x)f(x)=(x^n-1)f(x)\equiv\;0\;$$mod$$\;(x^n-1)$$

Next suppose that $m(x)h(x)\equiv\;0$mod$(x^n-1)$. Then

$$m(x)h(x)=(x^n-1)q(x)=h(x)g(x)q(x)$$

for some polynomial $q(x)$. We can now divide through by $h(x)$ and get

$$m(x)=g(x)q(x)$$

and so $m(x)$ coresponds to a codeword of $C$.
$\qedsymbol$

Remark:There will be a unique polynomial $h(x)$ such that $g(x)h(x)=x^n-1$. When thinking of the codespace as a product of polynomials with $g(x)$ instead of the row space of a binary matrix, this polynomial $h(x)$ will take the place of the check matrix in the decoding process. Let $c(x)=b(x)g(x)$ be a codeword then

$$c(x)h(x)=b(x)g(x)h(x)=b(x)(x^n-1)$$

Then if $m=$deg$b(x)$ the coeffiecients of the $m$ highest powers match the coeffiecients of the $m$ lowest powers of x in the polynomial $c(x)h(x)$.

Further, if the generating polynomial $g(x)=g_0+g_1x+...+g_{n-k}x^{n-k}$ has degree $n-k$, then the codewords $g(x),xg(x),x^2g(x),...x^{k-1}g(x)$ form a basis for the codespae $C$ with a generating matrix

$$G=\left(\begin{array}{cccccccc} g_0&g_1&\dots&g_{n-k}&0&0&\dots&0... ...&0&\dots&&&&\dots&0\\ 0&0&\dots&&g_0&g_1&\dots&g_{n-k}\\ \end{array}\right)$$

and we can realize a code word as an information sequence $(a_0,a-1,...a_{k-1})$ times the matrix

$$\mathbf{a}G=\left(a_o+a_1x+...+a_{k-1}x^{k-1}\right)g(x)\;$$mod$$\;x^n-1$$

As stated before, we can treat the polynomial $h(x)$, having the condition that $g(x)h(x)\equiv 0$mod$x^n-1$, as the check polynomial of the code $C$. Knowing that we want $g_0h_i+g_1h_{i-1}+...+g_{n-k}h_{i-n-k}=0$ for $i=0,1,...,n-1$, it follows that the check matrix for the code is

$$H=\left(\begin{array}{cccccccc} 0&0&\dots&0&h_k&\dots&h_1&h_0\\ ... ... \vdots&&&&&&&\vdots\\ h_k&\dots&h_1&h_0&0&\dots&0&0\\ \end{array}\right)$$

Lets now consider an example using a $3\times 7$ matrix of 0's and 1's.

$$\left(\begin{array}{ccccccc} 1&0&1&1&1&0&0\\ 0&1&0&1&1&1&0\\ 0&0&1&0&1&1&1\\ \end{array}\right)$$

Because each of the three rows are linearly independent we know from linear algebra that the row space of the matrix is a 3-dimensional subspace of $\ensuremath{\mathbb{F}}^7$ where $\mathbb{F}$ is the field $\ensuremath{\mathbb{Z}}_2$. In fact, since the algorithm is based on left multiplication by a codevector, the row space is the range of the matrix. In essence, because each codevector corresponds to a polynomial, the codespace corresponds to cyclic shifts of the coefficients of polynomials, which is just all polynomial products $a(x)g(x)$ where $g(x)$ is the generating polynomial for the code $C$.

It turns out that in this case all the cyclic shifts of the first row vector account for every vector in the row space. Thus we have a cyclic code and the generating polynomial is

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

which corresponds to the first row of the generating matrix.

Also, $\left(x^4+x^3+x^2+1\right)\left(x^3+x^2+1\right)=x^7-1$ and so the check polynomial is

$$h(x)=x^3+x^2+1$$

and we get the following check matrix

$$H=\left(\begin{array}{ccccccc} 0&0&0&1&1&0&1\\ 0&0&1&1&0&1&0\\ 0&1&1&0&1&0&0\\ \end{array}\right)$$

Now taking the codeword $c_g$ corresponding to $g(x)$ we get

$$Hc_g=\left(\begin{array}{ccccccc} 0&0&0&1&1&0&1\\ 0&0&1&1&0&1&0... ...\begin{array}{c} 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ 0\\ \end{array}\right)\;$$mod$$\;2$$

In fact, for every codeword $c$ in the space $C$, the product $Hc$ will be the zero vector. This will be an extremely important detail when creating an algorithm for a single-error correcting BCH code.

Before going into any detail about BCH codes we need some basic results about finite fields.