Abstract Algebra: Theory and Applications

We would like to find an easy method of obtaining cyclic linear codes. To accomplish this, we can use our knowledge of finite fields and polynomial rings over ${\mathbb{Z}}_2\text{.}$ Any binary $n$-tuple can be interpreted as a polynomial in ${\mathbb{Z}}_2[x]\text{.}$ Stated another way, the $n$-tuple $(a_0,a_1,\dots ,a_{n-1})$ corresponds to the polynomial

where the degree of $f(x)$ is at most $n-1\text{.}$ For example, the polynomial corresponding to the $5$-tuple $(10011)$ is

Conversely, with any polynomial $f(x)\in {\mathbb{Z}}_2[x]$ with $\mathrm{deg}f(x)<n$ we can associate a binary $n$-tuple. The polynomial $x+x^2+x^4$ corresponds to the $5$-tuple $(01101)\text{.}$

Rings of polynomials have a great deal of structure; therefore, our immediate goal is to establish a link between polynomial codes and ring theory. Recall that $x^n-1=(x-1)(x^{n-1}+\cdots +x+1)\text{.}$ The factor ring

can be considered to be the ring of polynomials of the form

that satisfy the condition $t^n=1\text{.}$ It is an easy exercise to show that ${\mathbb{Z}}_2^n$ and $R_n$ are isomorphic as vector spaces. We will often identify elements in ${\mathbb{Z}}_2^n$ with elements in $\mathbb{Z}[x]/⟨x^n-1⟩\text{.}$ In this manner we can interpret a linear code as a subset of $\mathbb{Z}[x]/⟨x^n-1⟩\text{.}$

The additional ring structure on polynomial codes is very powerful in describing cyclic codes. A cyclic shift of an $n$-tuple can be described by polynomial multiplication. If $f(t)=a_0+a_{1}t+\cdots +a_{n-1}{t}^{n-1}$ is a code polynomial in $R_n\text{,}$ then

is the cyclically shifted word obtained from multiplying $f(t)$ by $t\text{.}$ The following theorem gives a beautiful classification of cyclic codes in terms of the ideals of $R_n\text{.}$

Theorem 22.16 tells us that knowing the ideals of $R_n$ is equivalent to knowing the linear cyclic codes in ${\mathbb{Z}}_2^n\text{.}$ Fortunately, the ideals in $R_n$ are easy to describe. The natural ring homomorphism $\varphi :{\mathbb{Z}}_2[x]\to R_n$ defined by $\varphi [f(x)]=f(t)$ is a surjective homomorphism. The kernel of $\varphi$ is the ideal generated by $x^n-1\text{.}$ By Theorem 16.34, every ideal $C$ in $R_n$ is of the form $\varphi (I)\text{,}$ where $I$ is an ideal in ${\mathbb{Z}}_2[x]$ that contains $⟨x^n-1⟩\text{.}$ By Theorem 17.20, we know that every ideal $I$ in ${\mathbb{Z}}_2[x]$ is a principal ideal, since ${\mathbb{Z}}_2$ is a field. Therefore, $I=⟨g(x)⟩$ for some unique monic polynomial in ${\mathbb{Z}}_2[x]\text{.}$ Since $⟨x^n-1⟩$ is contained in $I\text{,}$ it must be the case that $g(x)$ divides $x^n-1\text{.}$ Consequently, every ideal $C$ in $R_n$ is of the form

The unique monic polynomial of the smallest degree that generates $C$ is called the minimal generator polynomial of $C\text{.}$

In general, we can determine a generator matrix for an $(n,k)$-code $C$ by the manner in which the elements $t^k$ are encoded. Let $x^n-1=g(x)h(x)$ in ${\mathbb{Z}}_2[x]\text{.}$ If $g(x)=g_0+g_{1}x+\cdots +g_{n-k}{x}^{n-k}$ and $h(x)=h_0+h_{1}x+\cdots +h_k{x}^k\text{,}$ then the $n\times k$ matrix

is a generator matrix for the code $C$ with generator polynomial $g(t)\text{.}$ The parity-check matrix for $C$ is the $(n-k)\times n$ matrix

We will leave the details of the proof of the following proposition as an exercise.

To determine the error-detecting and error-correcting capabilities of a cyclic code, we need to know something about determinants. If ${\alpha }_1,\dots ,{\alpha }_n$ are elements in a field $F\text{,}$ then the $n\times n$ matrix

is called the Vandermonde matrix. The determinant of this matrix is called the Vandermonde determinant. We will need the following lemma in our investigation of cyclic codes.

The idea behind BCH codes is to choose a generator polynomial of smallest degree that has the largest error detection and error correction capabilities. Let $d=2r+1$ for some $r\ge 0\text{.}$ Suppose that $\omega$ is a primitive $n$th root of unity over ${\mathbb{Z}}_2\text{,}$ and let $m_i(x)$ be the minimal polynomial over ${\mathbb{Z}}_2$ of ${\omega }^i\text{.}$ If

then the cyclic code $⟨g(t)⟩$ in $R_n$ is called the BCH code of length $n$ and distance $d\text{.}$ By Theorem 22.21, the minimum distance of $C$ is at least $d\text{.}$