Codex @codex  0

A block code assigns source messages to words of a fixed length over an alphabet. Its codewords form a subset of that fixed-length word space; a binary block code uses the two-symbol finite field ${\mathbb{F}}_2$.

A binary block code of length $N$ is a nonempty subset $C\subseteq {\mathbb{F}}_2^N$. Its size is $|C|$, the number of distinct codewords. The Hamming distance $d(x,y)$ counts coordinates at which two words differ. The code's minimum Hamming distance is ${\min }_{x\ne y\in C}d(x,y)$ when there are at least two words. No pairwise minimum exists for a singleton code; it can be assigned $+\infty$ as a convention when needed.

A binary linear code is a vector subspace of ${\mathbb{F}}_2^N$. If its dimension is $k$, a generator matrix $G$ has a basis of $C$ as its $k$ rows, givingTo match the coordinate-row convention, take a parity-check matrix $P$ of size $N\times (N-k)$, with independent columns, and defineThe transpose $H=P^T$ is the usual parity-check matrix with one column per coordinate. By rank-nullity theorem, the displayed kernel has dimension $k$. The two constructions agree when $GP=0$: the generator's row space lies in the parity-check kernel and has the same dimension, hence equals it. Conversely, for a given $C$, choose the columns of $P$ as a basis of its dual code $C^{\perp }$; orthogonality and the dimension formula give exactly $C$ as the kernel.

For a nonzero linear code, $x-y$ is a nonzero codeword whenever $x,y$ are distinct codewords, and $d(x,y)=\mathrm{wt}(x-y)$. Conversely compare any nonzero codeword with zero. Thus the minimum Hamming distance of a linear code is the least nonzero Hamming weight.

Write $P_i$ for the row associated with coordinate $i$. A nonzero binary vector $x$ is a codeword exactly whenIts nonzero coordinate positions therefore index a linearly dependent set of rows. Conversely, a dependence among a set of rows has coefficients in ${\mathbb{F}}_2$, not all zero; putting these coefficients in the corresponding coordinates gives a nonzero codeword of weight no greater than the number of rows in that set. Taking minima in both directions proves the parity-check dependencies determine minimum distance criterion:Rows here are indexed by positions: equal row vectors at different positions are two distinct members of the indexed family. In the usual matrix convention, the same result refers to columns of $H=P^T$. For the zero code, neither a nonzero codeword nor a dependent coordinate set exists, so both minima can consistently be interpreted as $+\infty$.

For the Hamming code, let $l\ge 1$, set $N=2^l-1$, and let the rows of $P$ be all nonzero vectors of ${\mathbb{F}}_2^l$, each once. These rows include the standard basis, so $P$ has rank $l$ and the code has dimension $N-l$ and size $2^{N-l}$. There is no dependence involving one row, because no row is zero, or two rows, because no rows are equal. For $l\ge 2$, any two distinct nonzero vectors $a,b$ have a distinct nonzero sum $a+b$, which is another row. These three rows sum to zero. Thus $d(C)=3$ for $l\ge 2$.

The perfectness of a Hamming code also has a direct decoding proof. Given any received word $y$, its syndrome is $yP\in {\mathbb{F}}_2^l$. A zero syndrome means $y\in C$. Otherwise it equals exactly one row $P_i$. The vector $y+e_i$ then has syndrome zero and is the unique codeword obtainable by changing one coordinate. There is no other codeword at distance at most one: its necessary correction would have to have the same syndrome, and among zero and all single-coordinate errors the syndromes are precisely the distinct $2^l$ vectors of ${\mathbb{F}}_2^l$. Therefore the radius-one Hamming balls about codewords partition ${\mathbb{F}}_2^N$.

Equivalently, each ball contains $1+N=2^l$ words; disjointness and $2^{N-l}{2}^l=2^N$ show that none are uncovered. Hence every nondegenerate binary Hamming code is a perfect single-error-correcting code. For $l=1$, the construction is the singleton code $\{0\}\subseteq {\mathbb{F}}_2$, whose one radius-one ball is also the whole ambient space. This deals with the degenerate boundary without falsely claiming its minimum distance is three.

Let the $r$ distinct codewords be $x^{(1)},\dots ,x^{(r)}\in {\mathbb{F}}_2^N$. No linearity assumption is needed. Sum their Hamming distances over unordered distinct pairs:Each summand is at least the minimum Hamming distance $\delta$, so $S\ge \delta r(r-1)/2$.

For coordinate $a$, let $m_a$ be the number of codewords whose $a$th bit is $1$. Exactly $m_a(r-m_a)$ unordered pairs differ at that coordinate. Summing coordinate contributions givessince $m_a(r-m_a)=r^2/4-(m_a-r/2{)}^2$. Combining the two bounds and dividing by $r>0$ gives $2\delta (r-1)\le Nr$, hence $r(2\delta -N)\le 2\delta$. Under $2\delta >N$, division is legitimate, proving the Plotkin boundBecause $r$ is an integer, it also satisfies the floor of the right-hand side. The binary alphabet is essential to the coordinate count; this proof applies to arbitrary binary block codes, not just linear ones.

A binary block code is a subset $C\subseteq \{0,1{\}}^n$; its length is the common word length $n$, its size is $m=|C|$, and its minimum distance is the least Hamming distance between distinct words. There are $V(n,r)={\sum }_{j=0}^r\left(\genfrac{}{}{0ex}{}{n}{j}\right)$ words in a radius-$r$ Hamming ball, since one chooses the positions to change.

Put $t=\lfloor (d-1)/2\rfloor$. Two radius-$t$ Hamming balls about different codewords cannot meet: otherwise the triangle inequality would make their centres at distance at most $2t<d$. Comparing their combined size with $2^n$ gives the Hamming boundFor the other direction, start with one word and repeatedly add any word at distance at least $d$ from every word already selected. Finiteness ensures that this process stops. At that point the radius-$(d-1)$ Hamming balls cover the entire cube; an uncovered word could otherwise be added. These balls may overlap, but their total size is at least $2^n$. This gives the Gilbert–Varshamov bound

A binary block code of length $n$ is a subset $C\subseteq {\mathbb{F}}_2^n$. Its size is $M=|C|$, and its minimum Hamming distance isThus an $[n,M,d]$ code consists of $M$ binary words of length $n$ whose distinct pairs differ in at least $d$ coordinates. When $d=1$, every set of distinct words qualifies. Taking all of the binary vector space ${\mathbb{F}}_2^n$ gives $2^n$ words, and no code can contain more words than its ambient space. Hence

For a binary block code, $n$ is the common length of its codewords, $m=|C|$ is the number of codewords, andis its minimum Hamming distance.

The parity extension isEvery extended word has even Hamming weight. The distance between two words increases by one exactly when their original distance is odd, so