{ "cells": [ {"cell_type": "code", "execution_count":null, "metadata":{}, "source":["%%html\n\n\n\n\n\n\n"], "outputs":[]}, {"cell_type":"markdown", "metadata":{}, "source":["**Important:** to view this notebook properly you will need to execute the cell above, which assumes you have an Internet connection. It should already be selected, or place your cursor anywhere above to select. Then press the \"Run\" button in the menu bar above (the right-pointing arrowhead), or press Shift-Enter on your keyboard."]}, {"cell_type":"markdown", "metadata":{}, "source":["$\\newcommand{\\identity}{\\mathrm{id}}\n\\newcommand{\\notdivide}{\\nmid}\n\\newcommand{\\notsubset}{\\not\\subset}\n\\newcommand{\\lcm}{\\operatorname{lcm}}\n\\newcommand{\\gf}{\\operatorname{GF}}\n\\newcommand{\\inn}{\\operatorname{Inn}}\n\\newcommand{\\aut}{\\operatorname{Aut}}\n\\newcommand{\\Hom}{\\operatorname{Hom}}\n\\newcommand{\\cis}{\\operatorname{cis}}\n\\newcommand{\\chr}{\\operatorname{char}}\n\\newcommand{\\Null}{\\operatorname{Null}}\n\\newcommand{\\lt}{<}\n\\newcommand{\\gt}{>}\n\\newcommand{\\amp}{&}\n$"]}, {"cell_type":"markdown", "metadata":{}, "source":["

Section22.2Polynomial Codes

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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}\\text{.}$ 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)\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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 )\\text{,}$ 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].

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Example22.14

Consider the $(6,3)$-linear codes generated by the two matrices

\n\\begin{equation*}\nG_1 \n= \n\\begin{pmatrix}\n1 & 0 & 0 \\\\\n0 & 1 & 0 \\\\\n0 & 0 & 1 \\\\\n1 & 0 & 0 \\\\\n0 & 1 & 0 \\\\\n0 & 0 & 1 \n\\end{pmatrix}\n\\quad\n\\text{and}\n\\quad\nG_2 = \n\\begin{pmatrix}\n1 & 0 & 0 \\\\\n1 & 1 & 0 \\\\\n1 & 1 & 1 \\\\\n1 & 1 & 1 \\\\\n0 & 1 & 1 \\\\\n0 & 0 & 1\n\\end{pmatrix}.\n\\end{equation*}\n

Messages in the first code are encoded as follows:

\n\\begin{equation*}\n\\begin{array}{rclccrcl}\n(000) & \\mapsto & (000000) & & & (100) & \\mapsto & (100100) \\\\\n(001) & \\mapsto & (001001) & & & (101) & \\mapsto & (101101) \\\\\n(010) & \\mapsto & (010010) & & & (110) & \\mapsto & (110110) \\\\\n(011) & \\mapsto & (011011) & & & (111) & \\mapsto & (111111).\n\\end{array}\n\\end{equation*}\n

It is easy to see that the codewords form a cyclic code. In the second code, 3-tuples are encoded in the following manner:

\n\\begin{equation*}\n\\begin{array}{rclccrcl}\n(000) & \\mapsto & (000000) & & & (100) & \\mapsto & (111100) \\\\\n(001) & \\mapsto & (001111) & & & (101) & \\mapsto & (110011) \\\\\n(010) & \\mapsto & (011110) & & & (110) & \\mapsto & (100010) \\\\\n(011) & \\mapsto & (010001) & & & (111) & \\mapsto & (101101).\n\\end{array}\n\\end{equation*}\n

This code cannot be cyclic, since $(101101)$ is a codeword but $(011011)$ is not a codeword.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

SubsectionPolynomial Codes

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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, \\ldots, a_{n - 1} )$ corresponds to the polynomial

\n\\begin{equation*}\nf(x) = a_0 + a_1 x + \\cdots + a_{n-1} x^{n - 1},\n\\end{equation*}\n

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

\n\\begin{equation*}\n1 + 0 x + 0 x^2 + 1 x^3 + 1 x^4 = 1 + x^3 + x^4.\n\\end{equation*}\n

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)\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

Let us fix a nonconstant polynomial $g(x)$ in ${\\mathbb Z}_2[x]$ of degree $n - k\\text{.}$ 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]\\text{.}$ To encode $f(x)\\text{,}$ we multiply by $g(x)\\text{.}$ The codewords in $C$ are all those polynomials in ${\\mathbb Z}_2[x]$ of degree less than $n$ that are divisible by $g(x)\\text{.}$ Codes obtained in this manner are called polynomial codes.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Example22.15

If we let $g(x)= 1 + x^3\\text{,}$ we can define a $(6,3)$-code $C$ as follows. To encode a 3-tuple $( a_0, a_1, a_2 )\\text{,}$ we multiply the corresponding polynomial $f(x) = a_0 + a_1 x + a_2 x^2$ by $1 + x^3\\text{.}$ We are defining a map $\\phi : {\\mathbb Z}_2^3 \\rightarrow {\\mathbb Z}_2^6$ by $\\phi : f(x) \\mapsto g(x) f(x)\\text{.}$ 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\\text{,}$ $\\phi$ is a linear transformation of vector spaces (see Exercise 20.4.15, Chapter 20). Let us compute the kernel of $\\phi\\text{.}$ Observe that $\\phi ( a_0, a_1, a_2 ) = (000000)$ exactly when

\n\\begin{align*}\n0 + 0x + 0x^2 + 0x^3 + 0x^4 + 0 x^5 & = (1 + x^3) ( a_0 + a_1 x + a_2 x^2 )\\\\\n& = a_0 + a_1 x + a_2 x^2 + a_0 x^3 + a_1 x^4 + a_2 x^5.\n\\end{align*}\n

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\\text{,}$ we merely need to examine the way the polynomials $1\\text{,}$ $x\\text{,}$ and $x^2$ are encoded:

\n\\begin{align*}\n(1 + x^3) \\cdot 1 & = 1 + x^3\\\\\n(1 + x^3)x & = x + x^4\\\\\n(1 + x^3)x^2 & = x^2 + x^5. \n\\end{align*}\n

We obtain the code corresponding to the generator matrix $G_1$ in Example 22.14. The parity-check matrix for this code is

\n\\begin{equation*}\nH\n= \n\\begin{pmatrix}\n1 & 0 & 0 & 1 & 0 & 0 \\\\\n0 & 1 & 0 & 0 & 1 & 0 \\\\\n0 & 0 & 1 & 0 & 0 & 1 \n\\end{pmatrix}.\n\\end{equation*}\n

Since the smallest weight of any nonzero codeword is 2, this code has the ability to detect all single errors.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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

\n\\begin{equation*}\nR_n = {\\mathbb Z}_2[x]/ \\langle x^n - 1 \\rangle\n\\end{equation*}\n

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

\n\\begin{equation*}\nf(t) = a_0 + a_1 t + \\cdots + a_{n-1} t^{n-1}\n\\end{equation*}\n

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] / \\langle x^n - 1 \\rangle\\text{.}$ In this manner we can interpret a linear code as a subset of ${\\mathbb Z}[x] / \\langle x^n - 1 \\rangle\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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

\n\\begin{equation*}\ntf(t) = a_{n-1} + a_0 t + \\cdots + a_{n-2} t^{n-1}\n\\end{equation*}\n

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{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Theorem22.16

A linear code $C$ in ${\\mathbb Z}_2^n$ is cyclic if and only if it is an ideal in $R_n = {\\mathbb Z}[x] / \\langle x^n - 1 \\rangle\\text{.}$

Proof

Let $C$ be a linear cyclic code and suppose that $f(t)$ is in $C\\text{.}$ Then $t f(t)$ must also be in $C\\text{.}$ Consequently, $t^k f(t)$ is in $C$ for all $k \\in {\\mathbb N}\\text{.}$ Since $C$ is a linear code, any linear combination of the codewords $f(t), tf(t), t^2f(t), \\ldots, t^{n-1}f(t)$ is also a codeword; therefore, for every polynomial $p(t)\\text{,}$ $p(t)f(t)$ is in $C\\text{.}$ Hence, $C$ is an ideal.

Conversely, let $C$ be an ideal in ${\\mathbb Z}_2[x]/\\langle x^n + 1\\rangle\\text{.}$ Suppose that $f(t) = a_0 + a_1 t + \\cdots + a_{n - 1} t^{n - 1}$ is a codeword in $C\\text{.}$ Then $t f(t)$ is a codeword in $C\\text{;}$ that is, $(a_1, \\ldots, a_{n-1}, a_0)$ is in $C\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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 $\\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\\text{.}$ By Theorem 16.34, every ideal $C$ in $R_n$ is of the form $\\phi(I)\\text{,}$ where $I$ is an ideal in ${\\mathbb Z}_2[x]$ that contains $\\langle x^n - 1 \\rangle\\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 = \\langle g(x) \\rangle$ for some unique monic polynomial in ${\\mathbb Z}_2[x]\\text{.}$ Since $\\langle x^n - 1 \\rangle$ 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

\n\\begin{equation*}\nC = \\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] \\}.\n\\end{equation*}\n

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

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Example22.17

If we factor $x^7 - 1$ into irreducible components, we have

\n\\begin{equation*}\nx^7 - 1 = (1 + x)(1 + x + x^3)(1+ x^2 + x^3).\n\\end{equation*}\n

We see that $g(t) = (1 + t + t^3)$ generates an ideal $C$ in $R_7\\text{.}$ 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\\text{,}$ $t^2\\text{,}$ and $t^3\\text{.}$ A generator matrix for $C$ is

\n\\begin{equation*}\nG =\n\\begin{pmatrix}\n1 & 0 & 0 & 0 \\\\\n1 & 1 & 0 & 0 \\\\\n0 & 1 & 1 & 0 \\\\\n1 & 0 & 1 & 1 \\\\\n0 & 1 & 0 & 1 \\\\\n0 & 0 & 1 & 0 \\\\\n0 & 0 & 0 & 1\n\\end{pmatrix}.\n\\end{equation*}\n
"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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

\n\\begin{equation*}\nG = \n\\begin{pmatrix}\ng_0 & 0 & \\cdots & 0 \\\\\ng_1 & g_0 & \\cdots & 0 \\\\\n\\vdots & \\vdots &\\ddots & \\vdots \\\\\ng_{n-k} & g_{n-k-1} & \\cdots & g_0 \\\\\n0 & g_{n-k} & \\cdots & g_{1} \\\\\n\\vdots & \\vdots & \\ddots & \\vdots \\\\\n0 & 0 & \\cdots & g_{n-k}\n\\end{pmatrix}\n\\end{equation*}\n

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

\n\\begin{equation*}\nH =\n\\begin{pmatrix}\n0 & \\cdots & 0 & 0 & h_k & \\cdots & h_0 \\\\\n0 & \\cdots & 0 & h_k & \\cdots & h_0 & 0 \\\\\n\\cdots & \\cdots & \\cdots & \\cdots & \\cdots & \\cdots & \\cdots \\\\\nh_k & \\cdots & h_0 & 0 & 0 & \\cdots & 0 \n\\end{pmatrix}.\n\\end{equation*}\n

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

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Proposition22.18

Let $C = \\langle g(t) \\rangle$ be a cyclic code in $R_n$ and suppose that $x^n - 1 = g(x) h(x)\\text{.}$ Then $G$ and $H$ are generator and parity-check matrices for $C\\text{,}$ respectively. Furthermore, $HG = 0\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Example22.19

In Example 22.17,

\n\\begin{equation*}\nx^7 - 1 = g(x) h(x) = (1 + x + x^3)(1 + x + x^2 + x^4).\n\\end{equation*}\n

Therefore, a parity-check matrix for this code is

\n\\begin{equation*}\nH =\n\\begin{pmatrix}\n0 & 0 & 1 & 0 & 1 & 1 & 1 \\\\\n0 & 1 & 0 & 1 & 1 & 1 & 0 \\\\\n1 & 0 & 1 & 1 & 1 & 0 & 0\n\\end{pmatrix}.\n\\end{equation*}\n
"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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\\text{,}$ then the $n \\times n$ matrix

\n\\begin{equation*}\n\\begin{pmatrix}\n1 & 1 & \\cdots & 1 \\\\\n\\alpha_1 & \\alpha_2 & \\cdots & \\alpha_n \\\\\n\\alpha_1^2 & \\alpha_2^2 & \\cdots & \\alpha_n^2 \\\\\n\\vdots & \\vdots & \\ddots & \\vdots \\\\\n\\alpha_1^{n-1} & \\alpha_2^{n-1} & \\cdots & \\alpha_n^{n-1} \n\\end{pmatrix}\n\\end{equation*}\n

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.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Lemma22.20

Let $\\alpha_1, \\ldots, \\alpha_n$ be elements in a field $F$ with $n \\geq 2\\text{.}$ Then

\n\\begin{equation*}\n\\det\n\\begin{pmatrix}\n1 & 1 & \\cdots & 1 \\\\\n\\alpha_1 & \\alpha_2 & \\cdots & \\alpha_n \\\\\n\\alpha_1^2 & \\alpha_2^2 & \\cdots & \\alpha_n^2 \\\\\n\\vdots & \\vdots & \\ddots & \\vdots \\\\\n\\alpha_1^{n-1} & \\alpha_2^{n-1} & \\cdots & \\alpha_n^{n-1} \n\\end{pmatrix}\n= \\prod_{1 \\leq j \\lt i \\leq n} (\\alpha_i - \\alpha_j).\n\\end{equation*}\n

In particular, if the $\\alpha_i$'s are distinct, then the determinant is nonzero.

Proof

We will induct on $n\\text{.}$ If $n = 2\\text{,}$ then the determinant is $\\alpha_2 - \\alpha_1\\text{.}$ Let us assume the result for $n - 1$ and consider the polynomial $p(x)$ defined by

\n\\begin{equation*}\np(x) = \\det\n\\begin{pmatrix}\n1 & 1 & \\cdots & 1 & 1 \\\\\n\\alpha_1 & \\alpha_2 & \\cdots & \\alpha_{n-1} & x \\\\\n\\alpha_1^2 & \\alpha_2^2 & \\cdots & \\alpha_{n-1}^2 & x^2 \\\\\n\\vdots & \\vdots & \\ddots & \\vdots & \\vdots \\\\\n\\alpha_1^{n-1} & \\alpha_2^{n-1} & \\cdots & \\alpha_{n-1}^{n-1} & x^{n-1}\n\\end{pmatrix}.\n\\end{equation*}\n

Expanding this determinant by cofactors on the last column, we see that $p(x)$ is a polynomial of at most degree $n-1\\text{.}$ Moreover, the roots of $p(x)$ are $\\alpha_1, \\ldots, \\alpha_{n-1}\\text{,}$ since the substitution of any one of these elements in the last column will produce a column identical to the last column in the matrix. Remember that the determinant of a matrix is zero if it has two identical columns. Therefore,

\n\\begin{equation*}\np(x) = (x - \\alpha_1)(x - \\alpha_2) \\cdots (x - \\alpha_{n-1}) \\beta,\n\\end{equation*}\n

where

\n\\begin{equation*}\n\\beta = (-1)^{n + n} \\det\n\\begin{pmatrix}\n1 & 1 & \\cdots & 1 \\\\\n\\alpha_1 & \\alpha_2 & \\cdots & \\alpha_{n-1} \\\\\n\\alpha_1^2 & \\alpha_2^2 & \\cdots & \\alpha_{n-1}^2 \\\\\n\\vdots & \\vdots & \\ddots & \\vdots \\\\\n\\alpha_1^{n-2} & \\alpha_2^{n-2} & \\cdots & \\alpha_{n-1}^{n-2} \n\\end{pmatrix}.\n\\end{equation*}\n

By our induction hypothesis,

\n\\begin{equation*}\n\\beta = (-1)^{n+n} \\prod_{1 \\leq j \\lt i \\leq n-1} (\\alpha_i - \\alpha_j).\n\\end{equation*}\n

If we let $x = \\alpha_n\\text{,}$ the result now follows immediately.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

The following theorem gives us an estimate on the error detection and correction capabilities for a particular generator polynomial.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Theorem22.21

Let $C = \\langle g(t) \\rangle$ be a cyclic code in $R_n$ and suppose that $\\omega$ is a primitive $n$th root of unity over ${\\mathbb Z}_2\\text{.}$ If $s$ consecutive powers of $\\omega$ are roots of $g(x)\\text{,}$ then the minimum distance of $C$ is at least $s + 1\\text{.}$

Proof

Suppose that

\n\\begin{equation*}\ng( \\omega^r) = g(\\omega^{r + 1}) = \\cdots = g( \\omega^{r + s - 1}) = 0.\n\\end{equation*}\n

Let $f(x)$ be some polynomial in $C$ with $s$ or fewer nonzero coefficients. We can assume that

\n\\begin{equation*}\nf(x) = a_{i_0} x^{i_0} + a_{i_1} x^{i_1} + \\cdots + a_{i_{s - 1}} x^{i_{s - 1}}\n\\end{equation*}\n

be some polynomial in $C\\text{.}$ It will suffice to show that all of the $a_i$'s must be 0. Since

\n\\begin{equation*}\ng( \\omega^r) = g(\\omega^{r + 1}) = \\cdots = g( \\omega^{r + s - 1}) = 0\n\\end{equation*}\n

and $g(x)$ divides $f(x)\\text{,}$

\n\\begin{equation*}\nf( \\omega^r) = f(\\omega^{r + 1}) = \\cdots = f( \\omega^{r + s - 1}) = 0.\n\\end{equation*}\n

Equivalently, we have the following system of equations:

\n\\begin{align*}\na_{i_0} (\\omega^r)^{i_0} + a_{i_1} (\\omega^r)^{i_1} + \\cdots + a_{i_{s - 1}} (\\omega^r)^{i_{s - 1}} & = 0\\\\\na_{i_0} (\\omega^{r + 1})^{i_0} + a_{i_1} (\\omega^{r + 1})^{i_2} + \\cdots + a_{i_{s-1}} (\\omega^{r+1})^{i_{s-1}} & = 0\\\\\n& \\vdots \\\\\na_{i_0} (\\omega^{r + s - 1})^{i_0} + a_{i_1} (\\omega^{r + s - 1})^{i_1} + \\cdots + a_{i_{s - 1}} (\\omega^{r + s - 1})^{i_{s - 1}} & = 0.\n\\end{align*}\n

Therefore, $(a_{i_0}, a_{i_1}, \\ldots, a_{i_{s - 1}})$ is a solution to the homogeneous system of linear equations

\n\\begin{align*}\n(\\omega^{i_0})^r x_0 + (\\omega^{i_1})^r x_1 + \\cdots + (\\omega^{i_{s - 1}})^r x_{n - 1} & = 0\\\\\n(\\omega^{i_0})^{r + 1} x_0 + (\\omega^{i_1})^{r + 1} x_1 + \\cdots + (\\omega^{i_{s - 1}})^{r + 1} x_{n - 1} & = 0\\\\\n& \\vdots \\\\\n(\\omega^{i_0})^{r + s - 1} x_0 + (\\omega^{i_1})^{r + s - 1} x_1 + \\cdots + (\\omega^{i_{s - 1}})^{r + s - 1} x_{n - 1} & = 0.\n\\end{align*}\n

However, this system has a unique solution, since the determinant of the matrix

\n\\begin{equation*}\n\\begin{pmatrix}\n(\\omega^{i_0})^r & (\\omega^{i_1})^r & \\cdots & (\\omega^{i_{s-1}})^r \\\\\n(\\omega^{i_0})^{r+1} & (\\omega^{i_1})^{r+1} & \\cdots &\n(\\omega^{i_{s-1}})^{r+1} \\\\\n\\vdots & \\vdots & \\ddots & \\vdots \\\\\n(\\omega^{i_0})^{r+s-1} & (\\omega^{i_1})^{r+s-1} & \\cdots &\n(\\omega^{i_{s-1}})^{r+s-1} \n\\end{pmatrix}\n\\end{equation*}\n

can be shown to be nonzero using Lemma 22.20 and the basic properties of determinants (Exercise). Therefore, this solution must be $a_{i_0} = a_{i_1} = \\cdots = a_{i_{s - 1}} = 0\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

SubsectionBCH Codes

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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\\text{,}$ 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.

"]}, {"cell_type":"markdown", "metadata":{}, "source":["

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\\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

\n\\begin{equation*}\ng(x) = \\lcm[ m_1(x), m_{2}(x), \\ldots, m_{2r}(x)],\n\\end{equation*}\n

then the cyclic code $\\langle g(t) \\rangle$ 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{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Theorem22.22

Let $C = \\langle g(t) \\rangle$ be a cyclic code in $R_n\\text{.}$ The following statements are equivalent.

  1. The code $C$ is a BCH code whose minimum distance is at least $d\\text{.}$

  2. A code polynomial $f(t)$ is in $C$ if and only if $f( \\omega^i) = 0$ for $1 \\leq i \\lt d\\text{.}$

  3. The matrix

    \n\\begin{equation*}\nH =\n\\begin{pmatrix}\n1 & \\omega & \\omega^2 & \\cdots & \\omega^{n-1}\\\\\n1 & \\omega^2 & \\omega^{4} & \\cdots & \\omega^{(n-1)(2)} \\\\\n1 & \\omega^3 & \\omega^{6} & \\cdots & \\omega^{(n-1)(3)} \\\\\n\\vdots & \\vdots & \\vdots & \\ddots & \\vdots \\\\\n1 & \\omega^{2r} & \\omega^{4r} & \\cdots & \\omega^{(n-1)(2r)} \n\\end{pmatrix}\n\\end{equation*}\n

    is a parity-check matrix for $C\\text{.}$

Proof

(1) $\\Rightarrow$ (2). If $f(t)$ is in $C\\text{,}$ then $g(x) \\mid f(x)$ in ${\\mathbb Z}_2[x]\\text{.}$ Hence, for $i = 1, \\ldots, 2r\\text{,}$ $f( \\omega^i) = 0$ since $g( \\omega^i ) = 0\\text{.}$ Conversely, suppose that $f( \\omega^i) = 0$ for $1 \\leq i \\leq d\\text{.}$ Then $f(x)$ is divisible by each $m_i(x)\\text{,}$ since $m_i(x)$ is the minimal polynomial of $\\omega^i\\text{.}$ Therefore, $g(x) \\mid f(x)$ by the definition of $g(x)\\text{.}$ Consequently, $f(x)$ is a codeword.

(2) $\\Rightarrow$ (3). Let $f(t) = a_0 + a_1 t + \\cdots + a_{n - 1}v t^{n - 1}$ be in $R_n\\text{.}$ The corresponding $n$-tuple in ${\\mathbb Z}_2^n$ is ${\\mathbf x} = (a_0 a_1 \\cdots a_{n - 1})^{\\rm t}\\text{.}$ By (2),

\n\\begin{equation*}\nH {\\mathbf x} =\n\\begin{pmatrix}\na_0 + a_1 \\omega + \\cdots + a_{n-1} \\omega^{n-1} \\\\\na_0 + a_1 \\omega^2 + \\cdots + a_{n-1} (\\omega^2)^{n-1} \\\\\n\\vdots \\\\\na_0 + a_1 \\omega^{2r} + \\cdots + a_{n-1} (\\omega^{2r})^{n-1}\n\\end{pmatrix}\n=\n\\begin{pmatrix}\nf(\\omega) \\\\\nf(\\omega^2) \\\\\n\\vdots \\\\\nf(\\omega^{2r})\n\\end{pmatrix}\n= 0\n\\end{equation*}\n

exactly when $f(t)$ is in $C\\text{.}$ Thus, $H$ is a parity-check matrix for $C\\text{.}$

(3) $\\Rightarrow$ (1). By (3), a code polynomial $f(t) = a_0 + a_1 t + \\cdots + a_{n - 1} t^{n - 1}$ is in $C$ exactly when $f(\\omega^i) = 0$ for $i = 1, \\ldots, 2r\\text{.}$ The smallest such polynomial is $g(t) = \\lcm[ m_1(t),\\ldots, m_{2r}(t)]\\text{.}$ Therefore, $C = \\langle g(t) \\rangle\\text{.}$

"]}, {"cell_type":"markdown", "metadata":{}, "source":["
Example22.23

It is easy to verify that $x^{15} - 1 \\in {\\mathbb Z}_2[x]$ has a factorization

\n\\begin{equation*}\nx^{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),\n\\end{equation*}\n

where each of the factors is an irreducible polynomial. Let $\\omega$ be a root of $1 + x + x^4\\text{.}$ The Galois field $\\gf(2^4)$ is

\n\\begin{equation*}\n\\{ 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 \\}.\n\\end{equation*}\n

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\\text{.}$ It is easy to see that $\\omega^2$ and $\\omega^4$ are also roots of $m_1(x)\\text{.}$ The minimal polynomial of $\\omega^3$ is $m_2(x) = 1 + x + x^2 + x^3 + x^4\\text{.}$ Therefore,

\n\\begin{equation*}\ng(x) = m_1(x) m_2(x) = 1 + x^4 + x^6 + x^7 + x^8\n\\end{equation*}\n

has roots $\\omega\\text{,}$ $\\omega^2\\text{,}$ $\\omega^3\\text{,}$ $\\omega^4\\text{.}$ Since both $m_1(x)$ and $m_2(x)$ divide $x^{15} - 1\\text{,}$ the BCH code is a $(15, 7)$-code. If $x^{15} -1 = g(x)h(x)\\text{,}$ then $h(x) = 1 + x^4 + x^6 + x^7\\text{;}$ therefore, a parity-check matrix for this code is

\n\\begin{equation*}\n\\left(\n\\begin{array}{ccccccccccccccc}\n0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\\\\n0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\\\\n0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\\\\n0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\\\\n0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\\\\n0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\\\\n0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\\\\n1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\n\\end{array}\n\\right).\n\\end{equation*}\n
"]} ], "nbformat": 4, "nbformat_minor": 0, "metadata": {"kernelspec": {"display_name": "", "name": "sagemath"}, "language_info": {"codemirror_mode": {"name": "ipython", "version": 2}, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.8"}, "name": "section-poly-codes.ipynb"} }