Codex @codex  0

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.

Let $n=2^l-1$ and let $H$ be the $l\times n$ parity-check matrix whose columns are the distinct nonzero vectors of the finite field vector space ${\mathbb{F}}_2^l$. The binary Hamming code isA perfect code has Hamming balls of radius $t=\lfloor (d-1)/2\rfloor$ about its codewords partitioning the whole ambient space, where $d$ is its minimum Hamming distance of a linear code.

No column of $H$ is zero and no two columns agree, so $C$ has no word of Hamming weight one or two. Three suitable columns sum to zero, so $d=3$. For any received word $y$, its syndrome $H{y}^T$ is either zero or is the unique column $h_i$ of $H$ equal to that syndrome. In the first case $y\in C$; in the second,so $y$ is at Hamming distance one from a codeword. Uniqueness follows from $d=3$. Thus the radius-one balls partition ${\mathbb{F}}_2^n$, and the code is perfect.

For $l=3$, the dual code is the binary simplex code of length seven. Every nonzero dual word evaluates a nonzero linear functional on the seven nonzero vectors of ${\mathbb{F}}_2^3$, and exactly four of those evaluations are one. Hence every nonzero word of $C^{\perp }$ has weight

Adding the all-one codeword is a bijection from $C$ to itself, and it replaces every bit by its complement. It therefore sends weight $j$ to weight $n-j$, provingThe code has one word of weight zero and, since its minimum Hamming distance is three, no words of weight one or two. Combining this with part (i) gives

Write $1_n$ for the all-one column vector. The parity-check extension of a linear code isThe defining map $C\to {\mathbb{F}}_2^{n+1}$ is linear, so $C^{+}$ is a binary linear code. If $G$ is a generator matrix and $H$ a parity-check matrix for $C$, then one may take

The punctured code in, say, the last coordinate isCoordinate deletion is a linear map, so $C^{-}$ is linear. Its generator matrix $G^{-}$ is obtained by deleting the last column of $G$. If the minimum distance is at least two, deletion is injective on $C$, and hence $C^{-}$ has the same dimension as $C$.

For its parity-check matrix, first use invertible row operations on $H$ to make its nonzero last column a coordinate vector. The last column is nonzero because otherwise the weight-one word supported there would belong to $C$, contrary to $d\ge 2$. Delete the pivot row and the last column; the resulting matrix $H^{-}$ is a parity-check matrix for $C^{-}$. Equivalently, $(C^{-}{)}^{\perp }$ is obtained by shortening the dual code $C^{\perp }$ at the deleted coordinate.

Finally, the shortened code in the last coordinate isIt is linear whenever $C$ is linear, because it is the puncture of the subspace $C\cap \{x_n=0\}$.