Past exam of the mathematics course of the University of Cambridge / 2005 / ii / Paper 3 / 12J (Coding and Cryptography)

A linear length-$n$ cyclic code is a subspace closed under cyclic coordinate shifts. Identify a word with its polynomial modulo $X^n-1$; multiplying by $X$ performs the shift. Thus a cyclic code is an ideal of ${\mathbb{F}}_q[X]/(X^n-1)$. Its preimage in the polynomial ring is an ideal containing $X^n-1$, so the Euclidean algorithm gives a unique monic generator $g$ dividing $X^n-1$. The generator polynomial of a cyclic code is $g$ and the check polynomial of a cyclic code is $h=(X^n-1)/g$; a word lies in the code exactly when $hc\equiv 0(\mathrm{mod}{X}^n-1)$.

For the binary length-seven code, the given $h$ factors withThis cubic has no binary root and is irreducible. Let $\alpha$ be its root in ${\mathbb{F}}_8$. Since the nonzero multiplicative group has prime order seven and $\alpha \ne 1$, its seven powers enumerate all nonzero elements. The condition $c(\alpha )=0$ gives a three-row binary parity-check matrix whose columns are precisely the seven nonzero vectors of ${\mathbb{F}}_2^3$. This is Hamming's code in a cyclic coordinate order. It has dimension four, and minimum distance three: no one or two distinct nonzero columns sum to zero, while $g$ itself has weight three. Its sixteen radius-one balls have total size $16(1+7)=128$, confirming the original perfect Hamming code.

It actually contains its dual code in this coordinate order. Each parity-check row has four ones, and any two distinct rows have two simultaneous ones, so $H{H}^T=0$ over ${\mathbb{F}}_2$. The row space $C^{\perp }$ therefore lies in $\ker H=C$. Equivalently the dual generator is the reciprocal check polynomialwhich is divisible by $g$. Hence there is a three-dimensional subcode equal to the dual, and in any other coordinate order it is equivalent to that dual.