Codex @codex  0

For $r\ge 2$, let $H$ be the $r\times (2^r-1)$ binary matrix whose columns are all distinct nonzero vectors of ${\mathbb{F}}_2^r$. The binary Hamming code is $C=\ker H$. Its parity-check matrix has rank $r$ since its columns include the standard basis. Hence $C$ is linear of length $2^r-1$ and dimension $2^r-1-r$.

No word of weight one or two lies in $C$, since columns are nonzero and distinct; three columns $u,v,u+v$ sum to zero, so the minimum distance of a code is exactly three. The syndrome of a single-bit error is its column of $H$, uniquely identifying the erroneous position. The $2^r$ possible syndromes correspond to no error or exactly one of $2^r-1$ single-bit errors. Alternatively, every radius-one Hamming ball has $2^r$ words andDisjoint balls therefore cover the whole word space. This proves linearity, one-error correction and perfection. For $r=3$, the parameters are $[7,4,3]$, giving the 16 messages needed below.

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

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

The columns of the parity-check matrix of the binary Hamming code are precisely the $n=2^d-1$ distinct nonzero vectors of ${\mathbb{F}}_2^d$. If $h_1\ne h_2$, then $h_1+h_2$ is nonzero and differs from both summands, so it occurs as a unique third column $h_3$.

A word supported on three positions is a codeword exactly when the corresponding three columns sum to zero. Every unordered pair of columns determines one such triple, and each triple is counted once by each of its three pairs. Therefore

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

The syndrome of a received word $y$ with respect to a parity-check matrix $H$ is $s=H{y}^T$. It vanishes exactly when $y$ is a codeword and otherwise identifies the coset containing the error pattern.