Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section22.2Polynomial Codes

With knowledge of polynomial rings and finite fields, it is now possible to derive more sophisticated codes than those of Chapter 8. First let us recall that an \((n, k)\)-block code consists of a one-to-one encoding function \(E:{\mathbb Z}^{k}_{2} \rightarrow {\mathbb Z}^{n}_{2}\) and a decoding function \(D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{k}_{2}\). The code is error-correcting if \(D\) is onto. A code is a linear code if it is the null space of a matrix \(H \in {\mathbb M}_{k \times n}({\mathbb Z}_2)\).

We are interested in a class of codes known as cyclic codes. Let \(\phi : {\mathbb Z}_2^k \rightarrow {\mathbb Z}_2^n\) be a binary \((n,k)\)-block code. Then \(\phi\) is a cyclic code if for every codeword \((a_1, a_2, \ldots, a_n )\), the cyclically shifted \(n\)-tuple \((a_n, a_1, a_2, \ldots, a_{n - 1} )\) is also a codeword. Cyclic codes are particularly easy to implement on a computer using shift registers [2, 3].

Example22.14

Consider the \((6,3)\)-linear codes generated by the two matrices \begin{equation*}G_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \quad \text{and} \quad G_2 = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}.\end{equation*} Messages in the first code are encoded as follows: \begin{equation*}\begin{array}{rclccrcl} (000) & \mapsto & (000000) & & & (100) & \mapsto & (100100) \\ (001) & \mapsto & (001001) & & & (101) & \mapsto & (101101) \\ (010) & \mapsto & (010010) & & & (110) & \mapsto & (110110) \\ (011) & \mapsto & (011011) & & & (111) & \mapsto & (111111). \end{array}\end{equation*} It is easy to see that the codewords form a cyclic code. In the second code, 3-tuples are encoded in the following manner: \begin{equation*}\begin{array}{rclccrcl} (000) & \mapsto & (000000) & & & (100) & \mapsto & (111100) \\ (001) & \mapsto & (001111) & & & (101) & \mapsto & (110011) \\ (010) & \mapsto & (011110) & & & (110) & \mapsto & (100010) \\ (011) & \mapsto & (010001) & & & (111) & \mapsto & (101101). \end{array}\end{equation*} This code cannot be cyclic, since \((101101)\) is a codeword but \((011011)\) is not a codeword.

SubsectionPolynomial Codes

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\). Any binary \(n\)-tuple can be interpreted as a polynomial in \({\mathbb Z}_2[x]\). Stated another way, the \(n\)-tuple \((a_0, a_1, \ldots, a_{n - 1} )\) corresponds to the polynomial \begin{equation*}f(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n - 1},\end{equation*} where the degree of \(f(x)\) is at most \(n - 1\). For example, the polynomial corresponding to the 5-tuple \((10011)\) is \begin{equation*}1 + 0 x + 0 x^2 + 1 x^3 + 1 x^4 = 1 + x^3 + x^4.\end{equation*} Conversely, with any polynomial \(f(x) \in {\mathbb Z}_2[x]\) with \(\deg f(x) \lt n\) we can associate a binary \(n\)-tuple. The polynomial \(x + x^2 + x^4\) corresponds to the 5-tuple \((01101)\).

Let us fix a nonconstant polynomial \(g(x)\) in \({\mathbb Z}_2[x]\) of degree \mbox{\(n - k\)}. We can define an \((n,k)\)-code \(C\) in the following manner. If \((a_0, \ldots, a_{k - 1})\) is a \(k\)-tuple to be encoded, then \(f(x) = a_0 + a_1 x + \cdots + a_{k - 1} x^{k - 1}\) is the corresponding polynomial in \({\mathbb Z}_2[x]\). To encode \(f(x)\), we multiply by \(g(x)\). The codewords in \(C\) are all those polynomials in \({\mathbb Z}_2[x]\) of degree less than \(n\) that are divisible by \(g(x)\). Codes obtained in this manner are called polynomial codes.

Example22.15

If we let \(g(x)= 1 + x^3\), we can define a \((6,3)\)-code \(C\) as follows. To encode a 3-tuple \(( a_0, a_1, a_2 )\), we multiply the corresponding polynomial \(f(x) = a_0 + a_1 x + a_2 x^2\) by \(1 + x^3\). We are defining a map \(\phi : {\mathbb Z}_2^3 \rightarrow {\mathbb Z}_2^6\) by \(\phi : f(x) \mapsto g(x) f(x)\). It is easy to check that this map is a group homomorphism. In fact, if we regard \({\mathbb Z}_2^n\) as a vector space over \({\mathbb Z}_2\), \(\phi\) is a linear transformation of vector spaces (see Exercise 20.4.15, Chapter 20). Let us compute the kernel of \(\phi\). Observe that \(\phi ( a_0, a_1, a_2 ) = (000000)\) exactly when \begin{align*} 0 + 0x + 0x^2 + 0x^3 + 0x^4 + 0 x^5 & = (1 + x^3) ( a_0 + a_1 x + a_2 x^2 )\\ & = a_0 + a_1 x + a_2 x^2 + a_0 x^3 + a_1 x^4 + a_2 x^5. \end{align*} Since the polynomials over a field form an integral domain, \(a_0 + a_1 x + a_2 x^2\) must be the zero polynomial. Therefore, \(\ker \phi = \{ (000) \}\) and \(\phi\) is one-to-one.

To calculate a generator matrix for \(C\), we merely need to examine the way the polynomials \(1\), \(x\), and \(x^2\) are encoded: \begin{align*} (1 + x^3) \cdot 1 & = 1 + x^3\\ (1 + x^3)x & = x + x^4\\ (1 + x^3)x^2 & = x^2 + x^5. \end{align*} We obtain the code corresponding to the generator matrix \(G_1\) in Example 22.14. The parity-check matrix for this code is \begin{equation*}H = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}.\end{equation*} Since the smallest weight of any nonzero codeword is 2, this code has the ability to detect all single errors.

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)\). The factor ring \begin{equation*}R_n = {\mathbb Z}_2[x]/ \langle x^n - 1 \rangle\end{equation*} can be considered to be the ring of polynomials of the form \begin{equation*}f(t) = a_0 + a_1 t + \cdots + a_{n-1} t^{n-1}\end{equation*} that satisfy the condition \(t^n = 1\). 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] / \langle x^n - 1 \rangle\). In this manner we can interpret a linear code as a subset of \({\mathbb Z}[x] / \langle x^n - 1 \rangle\).

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\), then \begin{equation*}tf(t) = a_{n-1} + a_0 t + \cdots + a_{n-2} t^{n-1}\end{equation*} is the cyclically shifted word obtained from multiplying \(f(t)\) by \(t\). The following theorem gives a beautiful classification of cyclic codes in terms of the ideals of \(R_n\).

Proof

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\). Fortunately, the ideals in \(R_n\) are easy to describe. The natural ring homomorphism \(\phi : {\mathbb Z}_2[x] \rightarrow R_n\) defined by \(\phi[f(x)] = f(t)\) is a surjective homomorphism. The kernel of \(\phi\) is the ideal generated by \(x^n - 1\). By Theorem 16.34, every ideal \(C\) in \(R_n\) is of the form \(\phi(I)\), where \(I\) is an ideal in \({\mathbb Z}_2[x]\) that contains \(\langle x^n - 1 \rangle\). 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 = \langle g(x) \rangle\) for some unique monic polynomial in \({\mathbb Z}_2[x]\). Since \(\langle x^n - 1 \rangle\) is contained in \(I\), it must be the case that \(g(x)\) divides \(x^n - 1\). Consequently, every ideal \(C\) in \(R_n\) is of the form \begin{equation*}C = \langle g(t) \rangle = \{ f(t)g(t) : f(t) \in R_n \text{ and } g(x) \mid (x^n - 1) \text{ in } {\mathbb Z}_2[x] \}.\end{equation*} The unique monic polynomial of the smallest degree that generates \(C\) is called the minimal generator polynomial of \(C\).

Example22.17

If we factor \(x^7 - 1\) into irreducible components, we have \begin{equation*}x^7 - 1 = (1 + x)(1 + x + x^3)(1+ x^2 + x^3).\end{equation*} We see that \(g(t) = (1 + t + t^3)\) generates an ideal \(C\) in \(R_7\). This code is a \((7, 4)\)-block code. As in Example 22.15, it is easy to calculate a generator matrix by examining what \(g(t)\) does to the polynomials 1, \(t\), \(t^2\), and \(t^3\). A generator matrix for \(C\) is \begin{equation*}G = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}.\end{equation*}

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]\). 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\), then the \(n \times k\) matrix \begin{equation*}G = \begin{pmatrix} g_0 & 0 & \cdots & 0 \\ g_1 & g_0 & \cdots & 0 \\ \vdots & \vdots &\ddots & \vdots \\ g_{n-k} & g_{n-k-1} & \cdots & g_0 \\ 0 & g_{n-k} & \cdots & g_{1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & g_{n-k} \end{pmatrix}\end{equation*} is a generator matrix for the code \(C\) with generator polynomial \(g(t)\). The parity-check matrix for \(C\) is the \((n-k) \times n\) matrix \begin{equation*}H = \begin{pmatrix} 0 & \cdots & 0 & 0 & h_k & \cdots & h_0 \\ 0 & \cdots & 0 & h_k & \cdots & h_0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ h_k & \cdots & h_0 & 0 & 0 & \cdots & 0 \end{pmatrix}.\end{equation*} We will leave the details of the proof of the following proposition as an exercise.

Example22.19

In Example 22.17, \begin{equation*}x^7 - 1 = g(x) h(x) = (1 + x + x^3)(1 + x + x^2 + x^4).\end{equation*} Therefore, a parity-check matrix for this code is \begin{equation*}H = \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 \end{pmatrix}.\end{equation*}

To determine the error-detecting and error-correcting capabilities of a cyclic code, we need to know something about determinants. If \(\alpha_1, \ldots, \alpha_n\) are elements in a field \(F\), then the \(n \times n\) matrix \begin{equation*}\begin{pmatrix} 1 & 1 & \cdots & 1 \\ \alpha_1 & \alpha_2 & \cdots & \alpha_n \\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ \alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_n^{n-1} \end{pmatrix}\end{equation*} 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 following theorem gives us an estimate on the error detection and correction capabilities for a particular generator polynomial.

Proof

SubsectionBCH Codes

Some of the most important codes, discovered independently by A. Hocquenghem in 1959 and by R. C. Bose and D. V. Ray-Chaudhuri in 1960, are BCH codes. The European and transatlantic communication systems both use BCH codes. Information words to be encoded are of length 231, and a polynomial of degree 24 is used to generate the code. Since \(231 + 24 = 255 = 2^8-1\), we are dealing with a \((255, 231)\)-block code. This BCH code will detect six errors and has a failure rate of 1 in 16 million. One advantage of BCH codes is that efficient error correction algorithms exist for them.

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 \geq 0\). Suppose that \(\omega\) is a primitive \(n\)th root of unity over \({\mathbb Z}_2\), and let \(m_i(x)\) be the minimal polynomial over \({\mathbb Z}_2\) of \(\omega^i\). If \begin{equation*}g(x) = \lcm[ m_1(x), m_{2}(x), \ldots, m_{2r}(x)],\end{equation*} then the cyclic code \(\langle g(t) \rangle\) in \(R_n\) is called the BCH code of length \(n\) and distance \(d\). By Theorem 22.21, the minimum distance of \(C\) is at least \(d\).

Proof
Example22.23

It is easy to verify that \(x^{15} - 1 \in {\mathbb Z}_2[x]\) has a factorization \begin{equation*}x^{15} - 1 = (x + 1)(x^2 + x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1),\end{equation*} where each of the factors is an irreducible polynomial. Let \(\omega\) be a root of \(1 + x + x^4\). The Galois field \(\gf(2^4)\) is \begin{equation*}\{ a_0 + a_1 \omega + a_2 \omega^2 + a_3 \omega^3 : a_i \in {\mathbb Z}_2 \text{ and } 1 + \omega + \omega^4 = 0 \}.\end{equation*} By Example 22.8, \(\omega\) is a primitive 15th root of unity. The minimal polynomial of \(\omega\) is \(m_1(x) = 1 + x + x^4\). It is easy to see that \(\omega^2\) and \(\omega^4\) are also roots of \(m_1(x)\). The minimal polynomial of \(\omega^3\) is \(m_2(x) = 1 + x + x^2 + x^3 + x^4\). Therefore, \begin{equation*}g(x) = m_1(x) m_2(x) = 1 + x^4 + x^6 + x^7 + x^8\end{equation*} has roots \(\omega\), \(\omega^2\), \(\omega^3\), \(\omega^4\). Since both \(m_1(x)\) and \(m_2(x)\) divide \(x^{15} - 1\), the BCH code is a \((15, 7)\)-code. If \(x^{15} -1 = g(x)h(x)\), then \(h(x) = 1 + x^4 + x^6 + x^7\); therefore, a parity-check matrix for this code is \begin{equation*}\left( \begin{array}{ccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right).\end{equation*}