Polynomial Codes

With knowledge of polynomial rings and finite fields, it is now possible to derive more sophisticated codes than those of . 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].

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{aligned}\end{aligned}\], where the degree of \(f(x)\) is at most \(n - 1\). For example, the polynomial corresponding to the \(5\)-tuple \((\codeword{10011})\) is \[\begin{aligned}\end{aligned}\]. 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 \((\codeword{01101})\).

Let us fix a nonconstant polynomial \(g(x)\) in \({\mathbb Z}_2[x]\) of degree \(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.

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{aligned}\end{aligned}\] can be considered to be the ring of polynomials of the form \[\begin{aligned}\end{aligned}\] 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\).

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.

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{aligned}\end{aligned}\], then the cyclic code \(\langle g(t) \rangle\) in \(R_n\) is called the BCH code of length \(n\) and distance \(d\). By , the minimum distance of \(C\) is at least \(d\).

Condensed — the full section is in Judson, Abstract Algebra: Theory and Applications.