Error-Correcting Codes: Introduction

Error-correcting codes underlie the physical layer of essentially all digital storage and communication. Compact discs and DVDs use Reed–Solomon codes (a generalization of the ideas here to larger alphabets) to survive scratches; deep-space probes such as Voyager used convolutional and Reed–Solomon codes to recover images sent across billions of kilometers with a vanishingly weak signal. Computer memory (ECC RAM) uses extended Hamming codes (adding one more overall parity bit to also detect, though not correct, double errors) to guard against cosmic-ray-induced bit flips. QR codes use Reed–Solomon coding to remain scannable even when partially obscured or damaged. In cryptography, the McEliece cryptosystem builds public-key encryption directly on the hardness of decoding a general linear code, using the Hamming-type structure as its trapdoor. In statistics and combinatorial design, the sphere-packing bound proved above is a special case of general packing bounds studied alongside Finite Projective Planes, since perfect codes and projective/Steiner-type designs share the same "exact covering" combinatorial signature — indeed the columns of the parity-check matrix $H$ above, viewed as the seven nonzero points of the Fano plane $\mathrm{PG}(2,2)$, is not a coincidence: the Hamming code's incidence structure literally is the Fano plane's point set indexing.

:::quiz[For the $[7,4,3]$ Hamming code, if the syndrome computed from a received word is $(0,1,1)$ (reading rows top to bottom), which position was in error?]

• Position 2
• Position 3 ✓
• Position 6
• No error occurred

:::quiz[What makes the $[7,4,3]$ Hamming code "perfect"?]

• It has the largest possible dimension for its length
• The radius-1 balls around codewords exactly partition the ambient space ✓
• It can correct any 2-bit error
• Its generator matrix is the identity matrix

Ask the tutor: How does the Hamming code's construction generalize to correct two or more errors, as in BCH and Reed–Solomon codes?

Think of $\Sigma^n$ as the vertex set of the $n$-dimensional Boolean hypercube, where two vertices are joined by an edge exactly when they differ in one coordinate — precisely the object you already know from Boolean Algebras as the free Boolean lattice's covering graph. Hamming distance is graph distance in this cube. A code is then just a chosen set of vertices, and the code's power comes from how far apart, in graph distance, its chosen vertices are forced to be. If we place a "ball" of radius $t$ around each codeword — all strings within Hamming distance $t$ — then correcting up to $t$ errors is possible exactly when these balls are pairwise disjoint, so that any received (possibly corrupted) word lands in the ball of at most one codeword. This is a packing condition, the same combinatorial flavor of question that governs point-line configurations in Finite Projective Planes: how many objects can be placed so that pairwise "closeness" constraints are respected. When the balls not only stay disjoint but also exhaust the whole space, no vertex is wasted — this is the perfection condition that the Hamming code will satisfy exactly.

The subspace lattice of $\mathbb{F}_2^n$, ordered by inclusion, is a finite modular lattice; linear codes are simply elements of this lattice singled out by an extra metric requirement (a lower bound on pairwise Hamming distance among nonzero vectors' differences). This is the same "combinatorial design under order constraints" theme you saw with incidence structures: an incidence system becomes a projective plane once axioms of order and regularity are imposed, and a subspace becomes an error-correcting code once a distance axiom is imposed.

Example 1: A simple triple-repetition code and its limits. Let $C = \{000, 111\} \subset \mathbb{F}_2^3$, a linear code with parameters $[3,1,3]$ (length 3, one message bit, and minimum distance $d = d_H(000,111) = 3$). By the theorem, $t = \lfloor (3-1)/2 \rfloor = 1$, so this code corrects any single bit-flip. Suppose the message bit is $1$, encoded as $c = 111$, and the channel flips the second bit, producing $r = 101$. We check $d_H(r, 000) = 2$ and $d_H(r, 111) = 1$. Since $1 < 2$, nearest-codeword decoding correctly outputs $111$, hence message bit $1$. This matches the theorem's guarantee since only $1 \le t=1$ error occurred. Now suppose two bits flip: $c = 111 \to r = 001$. Then $d_H(r,000) = 1$ and $d_H(r,111) = 2$, so nearest-codeword decoding outputs $000$ — the wrong codeword. This is exactly the tightness phenomenon from part (3) of the theorem: with $2 = t+1$ errors, decoding can fail. Note the huge cost of this code: three symbols of channel bandwidth buy only one bit of message, a rate of $1/3$, to correct a single error. The Hamming code below will do far better.

Example 2: Constructing and decoding the Hamming $[7,4,3]$ code. We now build the celebrated Hamming code carrying $k=4$ message bits in $n=7$ transmitted bits, correcting any single error, using $n-k = 3$ parity checks — logarithmically many, since $2^3 - 1 = 7$. Construction. Index the seven coordinate positions $1,\dots,7$ by the nonzero vectors of $\mathbb{F}_2^3$, written as their binary representations:

Let $H$ be the $3\times 7$ parity-check matrix whose $i$-th column is the binary representation of $i$:

The code is $C = \{x \in \mathbb{F}_2^7 : Hx^\top = 0\}$, a linear subspace of dimension $k = 7 - \mathrm{rank}(H) = 7-3=4$ (the rank is $3$ because the seven columns include the three standard basis vectors $100,010,001$, forcing full row rank). Take an explicit, asymmetric message. Let the message be $m = (1,0,1,1) \in \mathbb{F}_2^4$, placed by convention in the "data" positions $3,5,6,7$ (the positions whose index is not a power of $2$), with positions $1,2,4$ reserved as parity bits, chosen so that $Hx^\top=0$. Concretely, position $1$ (binary $001$) checks the parity of all positions whose binary index has a $1$ in the last bit: positions $1,3,5,7$. Position $2$ ($010$) checks positions $2,3,6,7$. Position $4$ ($100$) checks positions $4,5,6,7$. With data bits $x_3=1,x_5=0,x_6=1,x_7=1$ (matching $m=(1,0,1,1)$ in order), we solve:

So the transmitted codeword is

Verify $Hc^\top = 0$: row 1 sums positions $1,3,5,7$: $0+1+0+1 = 2 \equiv 0$. Row 2 sums positions $2,3,6,7$: $1+1+1+1=4\equiv 0$. Row 3 sums positions $4,5,6,7$: $0+0+1+1=2\equiv 0$. All three checks vanish, confirming $c \in C$. Introduce a single error. Suppose the channel flips position $5$: received word is

Decode via the syndrome. Compute $s = Hr^\top \in \mathbb{F}_2^3$: Row 1 (positions $1,3,5,7$): $0+1+1+1 = 3 \equiv 1$. Row 2 (positions $2,3,6,7$): $1+1+1+1 = 4 \equiv 0$. Row 3 (positions $4,5,6,7$): $0+1+1+1 = 3 \equiv 1$. So $s = (1,0,1)$. Read as a binary number this is $101_2 = 5$ — exactly the position that was flipped! This is not a coincidence but the design principle: $H$'s $i$-th column is the binary representation of $i$, so if a single error occurs at position $j$, then $r = c + e_j$ (where $e_j$ is the standard basis vector), and

since $Hc^\top = 0$ because $c \in C$. Flipping the bit the syndrome names, position $5$, recovers exactly $c = (0,1,1,0,0,1,1)$, and stripping the parity positions $1,2,4$ recovers the message $m = (1,0,1,1)$ correctly.

We now prove the minimum distance $d=3$ carefully rather than asserting it, and prove perfection.