Cyclic codes

Let $F$ be a finite field with $q$ elements.

Here's a constructive definition of a cyclic code of length $n$.

• Pick a monic polynomial $g(x)\in F[x]$ dividing $x^n-1$. This is called the generating polynomial of the code.
• For each polynomial $p(x)\in F[x]$, compute
  $$p(x)g(x)\ ({\rm mod}\ x^n-1).$$
  Denote the answer by $c_0+c_1x+...+c_{n-1}x^{n-1}$.
• ${\bf c} =(c_0,c_1,...,c_{n-1})$ is a code word in $C$. Every codeword in $C$ arises in this way (from some $p(x)$).

Since polynomial multiplication can be performed quickly on a computer, this construction illustrated one reason why cyclic codes have such fast encoding algorithms. The ``polynomial notation'' for the code is to call $c_0+c_1x+...+c_{n-1}x^{n-1}$ the code word (instead of $(c_0,c_1,...,c_{n-1})$).

Example 3.10.1   Let $g(x)=x^3+1 \in \mathbb{F}_2[x]$. This divides $x^{15}-1$. Let us compute the four codewords corresponding to $p(x)=1,x,x^2,x^{14}$. The first 3 are easy:

$$1\cdot g(x) = x^3+1 \leftrightarrow {\bf c}=(1,0,0,1,0,0,0,0,0,0,0,0,0,0,0),$$

$$x\cdot g(x) = x^4+x \leftrightarrow {\bf c}=(0,1,0,0,1,0,0,0,0,0,0,0,0,0,0),$$

$$x^2\cdot g(x) = x^5+x^2 \leftrightarrow {\bf c}=(0,0,1,0,0,1,0,0,0,0,0,0,0,0,0),$$

$$x^{14}\cdot g(x) = x^{17}+x^{14} \ ({\rm mod}\ x^{15}-1)=x^{14} +x^2 \leftrightarrow {\bf c}=(0,0,1,0,0,1,0,0,0,0,0,0,0,0,1).$$

Another way to characterize a cyclic code is as follows: A $q$-ary cyclic code is a linear code $C\subset F^n$ with the following property: if ${\bf c}=(c_0,c_1,...,c_{n-1})\in C$ then $(c_{n-1},c_0,...,c_{n-2})\in C$, for all ${\bf c}\in C$. Though the above constructive definition might be easier to understand, this one is much simpler.

If ${\bf c}=(c_0,c_1,...,c_{n-1})\in C$ is a non-zero code word in $C$ such that the degree of

$$g(x)=c_0+c_1x+...+c_{n-1}x^{n-1}\in F[x]$$

is minimum and such that $g(x)$ is monic then $g(x)$ is called a generating polynomial of $C$.

Remark 3.10.2   We shall not worry too much about showing that these definitions describe the same code. However, here are some hints for the reader who wants to prove it for him/herself. The fact that this polynomial $g(x)$ satisfies the property described in the above constructive definition requires Lemma 3.10.4 below. You must also show that the space $V$ in the Lemma is a principal ideal generated by $g(x)$.

Example 3.10.3   A simple example is the code

$$C=\{(0,0,0,0),(1,0,1,0),(0,1,0,1),(1,1,1,1)\} \subset \mathbb{F}_2^4.$$

The polynomial $g(x)=1+x^2$ is a generating polynomial.

It is easy to generate a cyclic code. Pick a vector ${\bf w}_1 =(v_1,v_2,...,v_r,0,...0)\in F^n$. Form $n-r$ cyclically shifted vectors

$${\bf w}_2=(0,v_1,v_2,...,v_r,0,...0),\ ...,{\bf w}_{n-r+1} =(0,...,0,v_1,v_2,...,v_r).$$

These form the basis of a cyclic code $C=span({\bf w}_1,...,{\bf w}_{n-r+1})$.

Let us associate to each code word ${\bf c}=(c_0,c_1,...,c_{n-1})\in C$ the polynomial

$$p_{{\bf c}}(x)=c_0+c_1x+...+c_{n-1}x^{n-1}\in F[x].$$

This correspondence is ``linear'', i.e., the sum of the code words is associated to the sum of the polynomials, $p_{{\bf c}+{\bf c'}}(x)=p_{{\bf c}}(x)+p_{{\bf c'}}(x)$ for all ${\bf c},{\bf c'}\in C$, and the scalar multiple of a code word is associated to the scalar muliple of the polynomial, $p_{a{\bf c}}(x)=ap_{{\bf c}}(x)$ for all ${\bf c}\in C$ and $a\in F$. Note that

$$xp_{{\bf c}}(x)\equiv c_0x+c_1x^2+...+c_{n-1}x^{n} \equiv c_{n-1}+c_0x+c_1x^2+...+c_{n-2}x^{n-1} \ ({\rm mod}\ x^n-1),$$

since for polynomials modulo $x^n-1$ we may identify $x^n$ with $1$.

In other words, we have the following result.

Lemma 3.10.4   A cyclic code $C\subset F^n$ may be identified with (via ${\bf c}\longmapsto p_{{\bf c}}(x)$) a $F$-vector space of polynomials $V\subset F[x]/(x^n-1)$. In other words, the elements of $C$ are in 1-1 correspondence with the elements of $V$ and this correspondence preserves the vector space operations of addition and scalar multiplication.

In fact, the image $V$ of $C$ is an ideal in the ring $F[x]/(x^n-1)$. Conversely, any such ideal is the image of some cyclic code under the map $c\longmapsto p_c(x)$.

Many codes we've run across already are equivalent to a cyclic code, including the Hamming codes and their dual codes.

Example 3.10.5   The binary code $C$ of length $7$ with generator polynomial $x^3 + x + 1$ has generator matrix

$$G= \left(\begin {array}{ccccccc} 1&0&1&1&0&0&0\\ \noalign{\medsk... ...medskip }0&0&1&0&1&1&0\\ \noalign{\medskip }0&0&0&1&0&1&1 \end {array}\right)$$

Its elements, sorted according to their weight, are

$$\begin{array}{c} C=\{(0, 0, 0, 0, 0, 0, 0), (0, 0, 0, 1, 0, ... ... (1, 1, 0, 1, 0, 0, 1), \\ (1, 1, 1, 1, 1, 1, 1)\} \end{array}$$

This code is equivalent to the Hamming $(7,4,3)$-code.

Let $C$ be a cyclic code of length $n$ with generator $g(x)\in \mathbb{F}_q[x]$. The polynomial

$$h(x)=(x^n-1)/g(x),$$

is called the check polynomial of $C$. This terminology is motivated by the following property.

Proposition 3.10.6   Let $C$ be as above. Let ${\bf v}=(v_0,v_1,...,v_{n-1})\in \mathbb{F}_q^n$. ${\bf v}\in C$ if and only if

$$(v_0+v_1x+...+v_{n-1}x^{n-1})h(x) \equiv 0 \ ({\rm mod}\ x^n-1).$$

proof: By the constructive definition of a cyclic code above, we know ${\bf v}\in C$ if and only if $v_0+v_1x+...+v_{n-1}x^{n-1}=p(x)g(x)$, for some polynomial $p(x)\in \mathbb{F}_q[x]$. In this case,

$$(v_0+v_1x+...+v_{n-1}x^{n-1})h(x) = p(x)g(x)h(x)=p(x)(x^n-1) \equiv 0 \ ({\rm mod}\ x^n-1).$$

Conversely, if $(v_0+v_1x+...+v_{n-1}x^{n-1})h(x) \equiv 0 \ ({\rm mod}\ x^n-1)$ then there is a polynomial $p(x)$ for which $(v_0+v_1x+...+v_{n-1}x^{n-1})h(x) =p(x)(x^n-1)$. By definition of $h(x)$, this is equivalent to saying $v_0+v_1x+...+v_{n-1}x^{n-1}=p(x)g(x)$. $\Box$

Example 3.10.7   Let $g(x)=(x-2)(x-4)=x^2+4x+3\in \mathbb{F}_5[x]$. This polynomial divides $x^4-1$ in $\mathbb{F}_5 [x]$. Let $C$ denote the cyclic code of length $4$ generated by $g(x)$. Its check polynomial is

$$h(x)=(x^4-1)/g(x)=x^2+x+3.$$

The codeword $c=(1,4,0,2)$ (note $1+4x+2x^3=(2+2x)g(x)$, so $c$ is a codeword by the constructive definition of a cyclic code) satisfies $(1+4x+2x^3)h(x) \equiv 0$ since

$$(1+4x+2x^3)(x^2+x+3)\equiv 10x^3+5x^2+15x+5 \ ({\rm mod}\ x^4-1),$$

which is 0 in $\mathbb{F}_5 [x]$.

Definition 3.10.8   Let $n$ be a positive integer relatively prime to $q$ and let $\alpha$ be a primitive n-th root of unity. Each generator polynomial g of a cyclic code C of length n has a factorization of the form

$$g(x) = (x - \alpha^{k_1})...(x - \alpha^{k_r}),$$

where $\{k_1,...,k_r\} \subset \{0,...,n-1\}$. The numbers $\alpha^{k_i}$, $1 \leq i \leq r$, are called the zeros of the code $C$. They do not depend on the choice of $g$.

Definition 3.10.9   If $k_1=b$, $k_2=b+1$, ..., $k_{b+\delta}=b+\delta-2$, then $C$ is called a Reed-Solomon code of designed distance $\delta$. Here $b\geq 1$ is an integer (often $b=1$).