Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 2 / 12G (Coding and Cryptography)

A cyclic binary code is a linear subspace of ${\mathbb{F}}_2^n$ invariant under cyclic shifts. Identify a word with its coefficient polynomial in ${\mathbb{F}}_2[X]/(X^n-1)$. Multiplication by $X$ is the shift, so the code is precisely an ideal of that quotient ring. Its inverse image in the polynomial ring is a principal ideal $(g)$ containing $(X^n-1)$; its unique monic generator divides $X^n-1$. Conversely each monic divisor generates such an ideal. Thus the bijection is with monic divisors; $g=1$ gives the full code and $g=X^n-1$ the zero code.

For odd $n$, some $m$ has $n\mid 2^m-1$, so the cyclic multiplicative group of ${\mathbb{F}}_{2^m}$ contains a primitive $n$th root $\alpha$. If a nonzero word with the specified roots had weight $w<\delta$, write its nonzero positions as $r_1,\dots ,r_w$. The root equations giveTheir matrix has determinant ${\prod }_j{\alpha }^{r_j}{\prod }_{j<l}({\alpha }^{r_l}-{\alpha }^{r_j})\ne 0$, by the Vandermonde formula and distinctness of the positions. Thus all coefficients would vanish, a contradiction. Hence minimum distance is at least $\delta$.

For $n=7$, choose $\alpha$ with minimal polynomial $X^3+X+1$. The roots $\alpha ,{\alpha }^2$ force also the conjugate ${\alpha }^4$, giving this cubic as generator. Its degree gives dimension four and its weight gives distance exactly three. Expressing $c(\alpha )=0$ in a basis of ${\mathbb{F}}_8$ gives a parity-check matrix with the seven distinct nonzero vectors of ${\mathbb{F}}_2^3$ as columns. This is the binary $[7,4,3]$ Hamming code. Its sixteen disjoint radius-one balls have $16(1+7)=128$ words, so one-error correction is perfect. The other primitive cubic produces an equivalent coordinate-permuted code.