Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 4 / 3I (Coding and Cryptography)

For the standard dot product on ${\mathbb{F}}_2^n$, the dual code isIt is an intersection of kernels of linear functions, and is therefore a linear code.

Let $\sigma$ denote cyclic right shift. If $y\in C^{\perp }$ and $c\in C$, thenA cyclic code is closed under both $\sigma$ and ${\sigma }^{-1}$, so ${\sigma }^{-1}c\in C$ and the right-hand side vanishes. Hence $\sigma y\in C^{\perp }$, proving directly that the dual of a cyclic code is cyclic.

Identify words with polynomials in ${\mathbb{F}}_2[X]/(X^n-1)$. If the generator polynomial of a cyclic code is the monic divisor $g(X)$ andthen the generator polynomial of $C^{\perp }$ is the monic reciprocalEquivalently, the parity-check polynomial of one code becomes, after reversal, the generator polynomial of its dual.

Over ${\mathbb{F}}_2$, subtraction equals addition. The polynomial $X^7-1$ has the factorizationThe two cubic factors have no root in ${\mathbb{F}}_2$, so they are irreducible, and they are reciprocal to one another. PutEvery cyclic code corresponds to one monic divisor of $X^7-1$. The complete list isThus the two cubic generators give the two cyclic coordinate orientations of Hamming's $[7,4,3]$ code. Their duals have generators $(X+1)f$ and $(X+1)f^{\ast }$ and are the $[7,3,4]$ simplex codes. The remaining four are the familiar whole-space, even-weight, repetition, and zero codes. This is the complete classification of binary cyclic codes of length seven.