Codex @codex  0

The Hamming bound packs disjoint balls of radius approximately $\delta n/2$. Taking logarithms and using the Hamming ball volume exponent gives the bound for $0\le \delta \le 1$.

// Target: algebra.bigb

Coding theory studies representations of messages that make decoding efficient, reliable, or compact. In channel coding, messages are mapped to separated codewords, so a corrupted word can still be recognized as coming from one particular message. In lossless source coding, a prefix code instead assigns short descriptions to frequent symbols. The objectives differ, but both exploit structure in the set of allowed words.

The simplest error-correction example sends $0$ as $000$ and $1$ as $111$. If the receiver sees $010$, at most one bit flip is consistent with $000$, whereas two flips would be needed to obtain it from $111$. A repetition code therefore recovers the original by taking the majority function of the received bits. The Hamming distance between the valid codewords is three: the spaces of one-error outputs around them do not overlap. This turns error correction into geometry in a discrete space.

The central tradeoff is between code rate and minimum distance. Additional separation makes correction possible but leaves fewer words available for messages at a fixed length. The Hamming bound counts disjoint error neighborhoods, while linear codes turn encoding and error detection into computations with matrices over finite fields. These connections explain why combinatorics, linear algebra, and probability theory all enter the subject.

Richard W. Hamming's Error Detecting and Error Correcting Codes appeared in the Bell System Technical Journal in April 1950, pp. 147–160. Its introduction motivates automatic correction through failures in digital computing, and its constructions go beyond detecting an error to identifying and correcting its location.^[ref]

For an $n$-qubit quantum code with projector $P$, the quantum code distance isHere the weight counts nonidentity tensor factors. Thus every error supported on fewer than $d$ qubits is detectable, by the Pauli expansion of a quantum error. A scalar action on the code, including a nonidentity stabilizer, is harmless and does not reduce this distance. For a stabilizer code, the equivalent definition minimizes weight among Pauli operators which commute with every stabilizer generator but act nontrivially on the logical information. The Knill--Laflamme condition then guarantees correction of all errors of weight at most $t=\lfloor (d-1)/2\rfloor$, since each pairwise product has weight at most $2t<d$.

Suppose the code encodes $k$ logical qubits and is nondegenerate for all errors through weight $t$. There aredistinct Pauli errors modulo phase: choose the $j$ affected positions and choose $X,Y$ or $Z$ at each. Each error is unitary, so its image of the code has dimension $2^k$. Nondegeneracy makes these images mutually orthogonal, equivalently the combined vectors $E_a|i_L⟩$ are orthonormal. They all lie in the physical Hilbert space of dimension $2^n$. Counting dimensions proves the quantum Hamming boundThis dimension argument requires nondegeneracy. For a degenerate code, different errors can share an image, as in the Shor code, and this counting proof cannot be applied unchanged.

For a binary classical code of $M$ words, the Hamming bound is $M{\sum }_{j=0}^t\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le 2^n$: disjoint Hamming balls around the words must fit into all binary strings. The quantum factor $3^j$ is needed because at each erroneous qubit there are three linearly independent nonidentity Pauli operators, not just a classical bit flip. A phase flip is invisible to a computational-basis classical record but changes a quantum superposition. A $Y$ error combines bit and phase effects, and the identity with $X,Y,Z$ spans every one-qubit operator. Quantum correction must protect amplitudes and coherences, and consequently count whole orthogonal logical subspaces rather than just classical words.

For parameters $[[5,1,3]]$, $t=1$, andThus a nondegenerate such code saturates the bound: the sixteen two-dimensional error images exhaust the physical space. It is a perfect quantum error-correcting code for single-qubit errors. It also has the smallest possible length for nondegenerate single-error protection of one logical qubit: for $1\le n\le 4$, the required inequality $1+3n\le 2^{n-1}$ fails.

Here is an explicit realization and its five-qubit stabilizer syndrome table. Write tensor products without multiplication symbols and useEach pair has an even number of anticommuting single-site factors, so the four stabilizer generators commute. Their binary Pauli labels are independent: no nonempty product has identity label. For example, the $X$-support at site three fixes the exponent of $g_3$ in such a product to zero, site five then fixes that of $g_2$, site one fixes that of $g_1$, and site two fixes that of $g_4$. Thus their group has sixteen elements and excludes $-I$. The common $+1$ eigenspace has projector $P={\prod }_{a=1}^4(I+g_a)/16$ and dimension $\mathrm{Tr}P=32/16=2$, since all nonidentity Pauli strings have zero trace.

Record a syndrome bit as one when an error anticommutes with the corresponding generator, in order $g_1,g_2,g_3,g_4$. Direct local commutation givesThese are all fifteen nonzero four-bit error syndromes; the identity has $0000$. Distinct errors in this list have a product with nonzero syndrome, so it anticommutes with some $g_a$. Inserting $g_{a}P=P$ on both sides gives $P{E}_b^{†}{E}_{c}P=-P{E}_b^{†}{E}_{c}P=0$. The diagonal product is the identity. Hence the Knill--Laflamme condition is exactly $C_{bc}={\delta }_{bc}$, proving nondegenerate correction. Measure the four commuting checks, apply the unique indicated Pauli error again, and every logical state is recovered. The Pauli expansion of a quantum error extends this recovery to an arbitrary one-qubit noise channel, not just the fifteen discrete errors.

The table also proves that every Pauli operator of weight one or two has nonzero syndrome: a weight-two operator is the product of distinct single-site errors, whose syndromes differ. Therefore the distance is at least three. The operators $\overline{X}=X^{\otimes 5}$ and $\overline{Z}=Z^{\otimes 5}$ commute with all four generators and anticommute with each other. They are nontrivial logical Pauli operators. Multiplication of $\overline{X}$ by $g_1$ gives $-IYYIX$, a weight-three operator with the same logical action; it cannot be scalar on the code because it anticommutes with the invertible logical operator $\overline{Z}$. This proves $d=3$ exactly.

The code consequently detects every two-qubit error and corrects two known-location erasures by the quantum erasure correction criterion, but it cannot correct all two-qubit errors of unknown location. A nontrivial weight-three logical operator can be split into a weight-one and a weight-two error, whose pairwise product violates the correction condition. It also saturates the quantum Singleton bound, since $n-k=4=2(d-1)$. These properties distinguish single-error perfectness from unrestricted protection against larger errors.

Write $A_2(N,\delta )$ for the largest number of codewords in a binary length-$N$ code with minimum Hamming distance at least $\delta$. The volume of a Hamming ball does not depend on its centre and isFor the Hamming bound, put $r=\lfloor (\delta -1)/2\rfloor$. The radius-$r$ Hamming balls around distinct codewords are disjoint: a point belonging to two such balls would, by the triangle inequality for Hamming distance, put their centres at distance at most $2r<\delta$. Counting points in the binary cube therefore gives

For the Gilbert–Varshamov bound, choose a code maximal under inclusion among those with minimum Hamming distance at least $\delta$, for example by successively adding any allowable word. Its radius-$(\delta -1)$ Hamming balls cover the cube. Otherwise an uncovered word would be at distance at least $\delta$ from every codeword and could be added, contradicting maximality. ThusThe lower bound is an existence assertion about a suitable code, while the upper bound holds for every such code. Together they give

Let $h_2(x)=-x{\log }_{2}x-(1-x){\log }_2(1-x)$ be the binary entropy. For $\delta =\lfloor \lambda N\rfloor$,The assumed Hamming ball volume exponent applies also to any integer radii $d_N$ with $d_N/N\to \theta \in (0,1/2)$. Indeed, for each small $\epsilon >0$ these radii eventually lie between $\lfloor (\theta -\epsilon )N\rfloor$ and $\lfloor (\theta +\epsilon )N\rfloor$. monotonicity of $v_N$ sandwiches its normalized logarithm between limits $h_2(\theta -\epsilon )$ and $h_2(\theta +\epsilon )$; continuity then lets $\epsilon$ tend to zero. Consequently the asymptotic Gilbert–Varshamov bound and asymptotic Hamming bound have respective exponential scalesEquivalently, the optimal code rate satisfiesThese are bounds on the rate, not a claim that the optimal rate has a known limit or equals either endpoint.

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

We give the bounds for an alphabet of size $q\ge 2$, including the binary case $q=2$. Let $C$ be a length-$n$ code with $M$ codewords and minimum Hamming distance at least $d$, where $1\le d\le n$. Write $A_q(n,d)$ for the maximum code size at a given distance andfor the number of words in a Hamming ball of radius $t$. The $j$th term chooses the changed coordinates and the $q-1$ alternative symbols in each.

For the Hamming bound, put $t=\lfloor (d-1)/2\rfloor$. Balls of radius $t$ around distinct codewords are disjoint: a common point would, by the triangle inequality, make their distance at most $2t<d$. Counting those balls inside the $q^n$ ambient words provesNo linearity is needed. For a linear code of dimension $k$ over ${\mathbb{F}}_q$, replace $M$ by $q^k$.

For the Gilbert–Varshamov bound, construct a code greedily, adding any word at distance at least $d$ from all previously selected words, until none remains. The process terminates because the space is finite. Its maximality implies that the radius-$(d-1)$ balls around its codewords cover the whole space: an uncovered word could have been added. These balls may overlap, but the size of their union is at most the sum of their sizes. Hence the constructed code has $M{V}_q(n,d-1)\ge q^n$, proving the existence boundOne may take the ceiling on the right because code size is integral.

For completeness, the sharper linear version is the Varshamov bound for linear codes. When $q$ is a prime power and $d\ge 2$, an $[n,k,\ge d]$ linear code exists providedSet $r=n-k$ and choose $n$ columns of an $r\times n$ parity-check matrix in order. When choosing column $l$, exclude all combinations of at most $d-2$ earlier columns, including the zero combination. There are at most ${\sum }_{j=0}^{d-2}\left(\genfrac{}{}{0ex}{}{l-1}{j}\right)(q-1{)}^j$ forbidden vectors, smaller than $q^r$ by the assumed inequality. A column can therefore be chosen. Inductively every set of at most $d-1$ chosen columns is independent: a relation involving the newest one would express it as a combination of at most $d-2$ earlier columns. The kernel has dimension at least $n-r=k$ and minimum Hamming distance at least $d$, since a low-weight kernel vector would be such a column relation. If its dimension is larger than $k$, take a $k$-dimensional subspace. This proves the stated linear existence claim; it does not assume the greedy nonlinear code was linear.

To derive the asymptotic bounds, define the q-ary entropywith the continuous endpoint conventions. Its derivative is ${\log }_q((q-1)(1-x)/x)$, so it is increasing on $[0,1-1/q]$ and has maximum one at $1-1/q$. Stirling's formula gives, uniformly for integer $0\le j\le n$,The sum defining $V_q$ is between its largest summand and $(n+1)$ times that summand. For radius fractions tending to $\rho \le 1-1/q$, monotonicity of $H_q$ makes the largest exponent tend to $H_q(\rho )$. Consequently the Hamming ball volume exponent isFor $\rho >1-1/q$, the exponent is one: use a radius fraction just below $1-1/q$ for a lower bound and $V_q\le q^n$ for an upper bound.

Set $d_n=\max \{1,\lceil \delta n\rceil \}$ and define the asymptotic rate-distance function byThe code rate is $n^{-1}{\log }_{q}M$ and the relative minimum distance is $d/n$. A limsup suffices; no unproved existence of a limit for optimal code sizes is required. The packing radii have fraction tending to $\delta /2$, so the finite Hamming bound and the volume exponent give the asymptotic Hamming boundThe covering radii have fraction tending to $\delta$, giving the asymptotic Gilbert–Varshamov boundFor larger $\delta$, this covering argument gives only the trivial lower bound zero, not the expression obtained by extending the decreasing information entropy function beyond its maximum.

The asymptotic lower bound is also achievable by linear codes over a finite field. For $\delta >0$ and sufficiently large $n$, take redundancy $r_n=\lfloor {\log }_q{V}_q(n-1,d_n-2)\rfloor +1$, so $q^{r_n}>V_q(n-1,d_n-2)$. The linear existence condition produces dimension at least $n-r_n$; its rate has liminf at least $1-H_q(\delta )$. At $\delta =0$, use the whole space, of rate one. In particular, for binary codes the bounds reduce towhere $h_2$ is the binary entropy function.

The original binary Hamming code has parameters $[7,4,3]$, so it has $2^4=16$ codewords. Its minimum distance three makes the radius-one balls about its codewords disjoint. Each ball hasvectors, and $16\cdot 8=128=2^7$, the size of the ambient space. Equality in the Hamming bound therefore shows that these balls partition ${\mathbb{F}}_2^7$: the code is perfect.

Puncturing gives a binary code of length $23$, size $2^{12}$, and distance at least $7$. Radius-three balls are disjoint andThe Hamming bound is an equality, so $G^{-}$ is perfect.