Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 3K (Coding and Cryptography)

The Reed-Muller code is spanned by the evaluation vectors of the square-free monomialsform a basis: every Boolean function has a unique algebraic normal form, so the monomials remain independent after evaluation on ${\mathbb{F}}_2^d$. ThusInduction using the decomposition $(u,u+v)$, with $u\in \mathrm{RM}(d-1,r)$ and $v\in \mathrm{RM}(d-1,r-1)$, gives the lower bound $2^{d-r}$ for every nonzero weight. The monomial $x_1\cdots x_r$ attains it, so the minimum distance is

The Mariner code is $\mathrm{RM}(5,1)$ with parameters $[32,6,16]$. Its information rate is $6/32=3/16$, and it correctserrors, a proportion $7/32$ of a codeword. The binary Hamming code of length $31$ has parameters $[31,26,3]$: its rate $26/31$ is much higher, but it corrects only one error, a proportion $1/31$.

A word of $\mathrm{RM}(d,1)$ is the evaluation of an affine Boolean functionIf $a=0$, the two constants have weights $0$ and $2^d$. If $a\ne 0$, choose $v$ with $a\cdot v=1$. Translation $x\mapsto x+v$ pairs every input where $f=0$ with one where $f=1$. Hence every one of the other codewords has weight $2^{d-1}$.