Codex @codex  0

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

The standard name is the Reed-Muller code. For $0\le d\le m$, evaluate all multilinear polynomials over ${\mathbb{F}}_2$ of total degree at most $d$ at every point of ${\mathbb{F}}_2^m$. These evaluation vectors form $RM(m,d)$, of length $2^m$. Distinct multilinear polynomials have distinct evaluations: induct on the variables using $f=g+x_{m}h$ and the two restrictions $g,g+h$. Thus the monomials of degree at most $d$ are independent andFor minimum weight, use the same splitting. A nonzero $h$ has weight at least $2^{m-d}$ by induction, and $\mathrm{wt}(g)+\mathrm{wt}(g+h)\ge \mathrm{wt}(h)$. If $h=0$, the two identical halves give the same lower bound by induction on $g$. The endpoint $d=m$ has minimum weight one, and $d=0$ is the repetition code. A product of $d$ distinct variables has exactly $2^{m-d}$ nonzero evaluations, soHere distance equals minimum nonzero weight because the code is linear.

Every monomial of degree at most $d-1$ in $d$ variables has an even number of ones, and parity is additive over ${\mathbb{F}}_2$. Thus every word of $RM(d,d-1)$ has even weight. If $x\in RM(m,r)$ and $y\in RM(m,m-r-1)$, their coordinatewise product is an evaluation of degree at most $m-1$, even after reducing $X_i^2=X_i$. Its weight is therefore even, so $⟨x,y⟩=0$. This proves the asserted inclusion in the dual code. Finallyby binomial symmetry. The dimensions agree with that of the orthogonal complement, proving $RM(m,r{)}^{\perp }=RM(m,m-r-1)$ for $0\le r<m$.

Work over the finite field ${\mathbb{F}}_2$. Reduce polynomials modulo $X_i^2-X_i$, so their monomials are square-free. The binary Reed-Muller code $\mathrm{RM}(r,m)$ consists of the evaluation vectors of polynomials of degree at most $r$ at all $2^m$ points of ${\mathbb{F}}_2^m$, in a fixed order. This is a linear code of length $2^m$ and dimension ${\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{m}{j}\right)$, for $0\le r\le m$. Square-free monomials give independent evaluation functions, as follows inductively by splitting according to the last variable.

The minimum Hamming distance of a linear code equals its least nonzero Hamming weight. The result isHere $r=0$ is the repetition code, while $r=m$ is the full binary vector space and has distance one. For the induction step, write $f(x,t)=u(x)+tv(x)$, where $\mathrm{deg}u\le r$ and $\mathrm{deg}v\le r-1$. Its evaluation vector is $(u,u+v)$, the Reed-Muller bar-product recursion. If $v=0$, its nonzero Hamming weight is at least $2d(r,m-1)=2^{m-r}$, with the full-space endpoint treated as above. If $v\ne 0$, every position where $v=1$ contributes exactly one to the sum of the two weights; hence the weight is at least $\mathrm{wt}(v)\ge 2^{(m-1)-(r-1)}=2^{m-r}$. The monomial $X_1\cdots X_r$ is one exactly on $2^{m-r}$ points, attaining the bound. Degrees greater than $m$ give the same full code; the zero code at negative degree has no nonzero word whose weight could define a finite minimum.

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

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