Cyclic Codes

Generator polynomials, ideals modulo x^n-1, and polynomial encoding.

The idea

A cyclic code is a linear code closed under the cyclic shift: move every symbol of a codeword one place to the right, wrapping the last symbol around to the front, and the result must again be a codeword. This symmetry lets a single polynomial describe the entire code.

Identify the vector $(c_0, c_1, \ldots, c_{n-1})$ with the polynomial $c(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1}.$ Multiplying by $x$ raises every exponent by one, and reducing modulo $x^{n} - 1$ replaces the overflowing $x^{n}$ by $1$, returning the last symbol to the front. Multiplication by $x$ is exactly the cyclic shift. In the ring $\mathbb{F}_q[x]/(x^{n}-1)$, a cyclic code is therefore closed under addition and under multiplication by $x$, hence under multiplication by every polynomial: it is an ideal.

Every ideal of this ring consists of the multiples of one monic polynomial of least degree in it, the generator polynomial $g(x)$, and $g(x)$ divides $x^{n} - 1$: otherwise the remainder of $x^{n}-1$ on division by $g$ would be a nonzero codeword of degree below $\deg g$. So a cyclic code of length $n$ amounts to a choice of divisor of $x^{n}-1$. Its dimension is $k = n - \deg g$, and a word belongs to the code if and only if $g(x)$ divides its polynomial.

Ways to work on it

• Walkthrough. Generator polynomial, dimension, and polynomial encoding of a cyclic code.
• Practice. Read off a cyclic code's dimension from its generator polynomial.
• Hardest. Systematic encoding via the remainder modulo the generator polynomial.

Not sure where to start? Take the ten-question placement test.