Codex @codex  0

A binary linear code of length $n$ is a vector subspace $C\subseteq {\mathbb{F}}_2^n$. The Hamming weight of a word counts its nonzero coordinates, and the code weight is $w(C)={\min }_{0\ne c\in C}\mathrm{wt}(c)$; for a linear code this equals its minimum distance. One may assign infinite minimum weight to the zero code when needed.

For length-$n$ codes with $C_2\subseteq C_1$, the bar product of binary linear codes isIt is a linear code because this map from $C_1\oplus C_2$ is linear and injective. For a nonzero codeword, if $v=0$ then $u\ne 0$ and its weight is $2\mathrm{wt}(u)\ge 2w(C_1)$. If $v\ne 0$, every nonzero coordinate of $v$ makes exactly one of the corresponding coordinates of $u,u+v$ nonzero; henceTaking the minimum givesIn fact equality holds when the codes are nonzero: minimum-weight words $(u,u)$ and $(0,v)$ attain the two candidate weights.

For binary linear codes of length $n$, the bar product of binary linear codes is $C_1|C_2=\{(u,u+v):u\in C_1,v\in C_2\}$. The parametrization is injective and linear, so its dimension is $k_1+k_2$. If $v=0$, a nonzero word has Hamming weight at least $2d_1$; if $v\ne 0$, $\mathrm{wt}(u)+\mathrm{wt}(u+v)\ge \mathrm{wt}(v)\ge d_2$. Taking $(u,u)$ and $(0,v)$ of minimum weight showsFor $a\in C_2^{\perp },b\in C_1^{\perp }$, the inner product of $(u,u+v)$ and $(a,a+b)$ is $u\cdot b+v\cdot a+v\cdot b=0$, since $C_2\subseteq C_1$. The spaces have complementary dimensions, proving $(C_1|C_2{)}^{\perp }=C_2^{\perp }|C_1^{\perp }$.

Define the Reed-Muller code $\mathrm{RM}(d,r)$ by evaluating all multilinear polynomials of total degree at most $r$ at the $2^d$ points of ${\mathbb{F}}_2^d$. The squarefree monomials are independent functions, giving dimension ${\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{d}{j}\right)$. Splitting according to the last variable gives the Reed-Muller bar-product recursion $\mathrm{RM}(d,r)=\mathrm{RM}(d-1,r)|\mathrm{RM}(d-1,r-1)$, with the endpoint codes interpreted in the usual way. The distance recursion gives $2^{d-r}$.

To identify the Dual of a Reed-Muller code, multiply a monomial of degree at most $r$ by one of degree at most $d-r-1$. The product omits some variable, so its sum over ${\mathbb{F}}_2^d$ is even and its binary inner product is zero. The binomial dimension identity then gives

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

For binary length-$n$ linear codes $C_2\subseteq C_1$, their bar product of binary linear codes isIt is a binary linear code of length $2n$ and dimension $\dim C_1+\dim C_2$.