Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 11H / Solution

For length-$n$ binary linear codes $C_2\subseteq C_1$, their bar product of binary linear codes isThe map $(u,v)\mapsto (u,u+v)$ is injective and linear, soIf $d_i$ is the minimum distance of $C_i$, thenFor $v\ne 0$ this is at least $d_2$; for $v=0$ a nonzero word has weight at least $2d_1$. Words $(0,v)$ and $(u,u)$ attain these bounds, proving

A parity-check matrix $P$ for a code $C$ is a matrix satisfying $C=\ker P$. A pair $(x,y)$ belongs to $C_1|C_2$ exactly whenThus a parity-check matrix isThis is the parity-check matrix of a bar product.

The Reed-Muller code $\mathrm{RM}(d,r)$ is the length-$2^d$ binary code obtained by evaluating every square-free polynomial in $d$ Boolean variables of degree at most $r$ on all points of ${\mathbb{F}}_2^d$. Equivalently,The square-free monomials form a basis, soA word in $\mathrm{RM}(d,1)$ evaluates an affine function $a_0+a\cdot x$. The two constant functions have weights $0$ and $2^d$. Every nonconstant affine function takes each value equally often, so all other codewords have weight $2^{d-1}$.

A monomial of degree $j$ has weight $2^{d-j}$. Hence every generator, and therefore every codeword, has even weight when $r<d$. For $r=d$, the monomial $x_1\cdots x_d$ has weight one. All words have even weight exactly for $0\le r\le d-1$.