Codex @codex  0

A linear code of length $n$ over ${\mathbb{F}}_q$ is a linear subspace $C\subseteq {\mathbb{F}}_q^n$. A parity-check matrix $P$ satisfies $C=\ker P$. Its minimum distance of a code is the least Hamming distance between distinct codewords, equivalently the least Hamming weight of a nonzero word, because differences remain in the code.

For the usual binary bar product of binary linear codes, take equal-length binary codes with $C_2\subseteq C_1$ and defineIt is linear, of length $2n$ and dimension $\dim C_1+\dim C_2$, since the parametrization is injective. If $v=0$ and the word is nonzero, its weight is $2\mathrm{wt}(u)\ge 2d(C_1)$. If $v\ne 0$, coordinatewise $\mathrm{wt}(u)+\mathrm{wt}(u+v)\ge \mathrm{wt}(v)\ge d(C_2)$. The words $(u,u)$ with $u$ of minimum nonzero weight and $(0,v)$ with $v$ of minimum weight achieve the two candidate bounds. ThusFor a word $(x,y)$, membership is equivalent to $P_{1}x=0$ and $P_2(x+y)=0$. Consequently a parity-check matrix of a bar product isThe same distance argument actually needs only equal block lengths and a common field, not nesting. Over a general field replace the second row block by $(-P_2,P_2)$, so it tests $y-x\in C_2$. The displayed binary construction uses the conventional nesting.

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$.