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

A binary cyclic code is a linear subspace $C\le {\mathbb{F}}_2^n$ invariant under cyclic coordinate shift. Identify a word $(c_0,\dots ,c_{n-1})$ with $c_0+c_{1}X+\cdots +c_{n-1}{X}^{n-1}$ inCyclic shift is multiplication by $X$, so cyclic codes are exactly ideals of this quotient. Since ${\mathbb{F}}_2[X]$ is a principal ideal domain, each is generated by a unique monic divisor $g\mid X^n-1$, giving the required bijection.

A linear-feedback shift register is a linear mapFor the stated matrix $H$, a word $c=(c_0,\dots ,c_{k-1})$ lies in $C$ exactly when ${\sum }_j{c}_j{M}^{j}x=0$. If $\sigma c$ is its cyclic shift, periodicity $M^{k}x=x$ givesThus $\ker H$ is shift-invariant and is a binary cyclic code.

If $c\in C$ had odd Hamming weight, add all $n$ cyclic shifts of $c$. Each coordinate of the sum is the sum of all coordinates of $c$, namely one in ${\mathbb{F}}_2$. Linearity and cyclicity would therefore put $(1,\dots ,1)$ in $C$, contrary to the hypothesis. Hence every codeword has even weight.