Past exam of the mathematics course of the University of Cambridge / 2007 / ii / Paper 3 / 4G / Solution

The polynomials are over ${\mathbb{F}}_2$, and multiplication gives $gh=X^7+1=X^7-1$. A cyclic code of length seven generated by a degree-three polynomial has dimension $7-3=4$: the multiples $ag$ with $\mathrm{deg}a<4$ are distinct representatives, so its rank is four.

The root $\alpha$ has order seven in ${\mathbb{F}}_8^{\times }$: it is neither zero nor one, and the multiplicative group has prime order seven. A weight-one word cannot vanish at $\alpha$. A weight-two word $X^i+X^j$, with distinct indices between zero and six, cannot vanish either, because that would give ${\alpha }^{i-j}=1$. Every codeword vanishes at $\alpha$, so its nonzero weight is at least three. Since $g$ itself has weight three,From ${\alpha }^3=\alpha +1$ obtain ${\alpha }^4={\alpha }^2+\alpha$ and ${\alpha }^5={\alpha }^2+\alpha +1$. Therefore $r(\alpha )={\alpha }^5+{\alpha }^3+\alpha ={\alpha }^2+\alpha ={\alpha }^4$. The one-bit error $X^4$ has precisely this syndrome, so correcting it givesIts distance from the received word is one. The minimum distance three makes this nearest codeword unique: two codewords each at distance one from the received word would be at distance at most two from each other.