Channels make errors, and the crudest defence is repetition: send each bit three times and take a majority vote. The error rate falls, but the rate collapses to 1/3; want more reliability and you send it five or seven times — so "almost never wrong" seems to demand that the rate go to zero.
Shannon said no. Every channel has a definite number $C$ (its capacity): so long as your rate $R<C$, there exists a code driving the error rate arbitrarily close to 0 with no loss of rate; once $R>C$, no code however clever can succeed. Fast and accurate are not a seesaw — they are separated by a cliff. The trick is not to armour bits one at a time but to encode in blocks: map a long message as a whole to a single point in a high-dimensional space. If the points sit far enough apart, noise can shove one around and it still lies closest to where it started.
$I(X;Y)$ is the mutual information between input $X$ and output $Y$ — how much of your uncertainty about $X$ is removed by seeing $Y$ (in bits). Capacity $C$ is its maximum over all input distributions $p(x)$: with the channel used to its utmost, how many bits can one use carry. For a channel that flips each bit with probability $p$, $C=1-H(p)$, where $H(p)=-p\log_2 p-(1-p)\log_2(1-p)$ is the entropy of the noise itself — the share the noise eats is subtracted exactly from the full bandwidth of 1.
The beauty is in the strangeness of the proof. Shannon constructed no good code at all; what he proved was that a code drawn at random from all codes already performs well on average, so good codes must exist — using randomness to prove that a deterministic object exists, the probabilistic method's most startling debut. The deeper beauty is the shape of the threshold: intuition expects a smooth trade-off curve, and mathematics hands back a sharp phase transition. Reliable communication turns out to be a phase transition, like water coming to a boil.
This limit is the origin of coordinates for the whole communications industry: every scheme is scored by "how many dB from Shannon". Turbo codes first came within 0.5 dB; LDPC codes now sit inside 5G data channels and SSD controllers. On the AI side, rate–distortion theory is the mathematical parent of variational autoencoders and the information-bottleneck view: training a representation is deciding which bits to keep under a capacity budget.
See each 7-bit string as a vertex of a 7-dimensional cube (128 of them); noise flipping one bit is a single step along an edge. Error correction becomes geometry: choose a set of vertices as "legal words", pairwise at least 3 steps apart — then the vertices within one step of each legal word form a small ball, the balls are disjoint, and any once-flipped string must land inside exactly one of them.
Hamming's construction is slicker still: of the 7 bits, 3 are parity checks, each covering a particular subset of positions. Write the pass/fail of the three checks as a three-bit binary number and that number is the index of the corrupted bit — the checks announce the street address of the error themselves.
An $[n,k,d]$ linear code encodes $k$ bits into $n$, any two codewords differing in at least $d$ places (the minimum Hamming distance), so it corrects $t=\lfloor (d-1)/2\rfloor$ errors; Hamming(7,4) is $[7,4,3]$. The columns of the parity-check matrix $H$ are exactly the 7 non-zero three-bit vectors; given a received $\mathbf r$, compute the syndrome $s=H\mathbf r$: $s=0$ means clean, otherwise $s$ read as a binary number is the index of the faulty column. The Hamming bound then says: $2^k$ balls of $\sum_{i\le t}\binom{n}{i}$ points each cannot exceed the whole space.
Put the numbers in: $2^4\times(1+7)=128=2^7$. The inequality is an equality — 128 vertices tiled seamlessly by 16 balls, none missed, none overlapping. This is a perfect code: the discrete counterpart of Kepler's packing problem, where the answer is not "about 74%" but exactly 100%. Such gems are vanishingly rare: in the binary case only the Hamming family and two Golay codes exist, proved exhaustive in 1973.
In 1947 Hamming's weekend batch jobs kept being discarded by the Bell Labs machine over a single wrong bit, and he demanded in exasperation: "If the machine can find the error, why can it not fix it?" — the whole discipline grew from that question. Today's server ECC memory runs SECDED (correct one bit, detect two), and every bit flip a cosmic ray induces in DRAM is repaired silently right there.
Two points determine a line. If the message I want to send is the two coefficients of a line, I do not send the coefficients — I sample 5 points on the line and send those. Lose three and it hardly matters: any surviving two reconstruct the line. Redundancy is not repeating the message; it is oversampling it.
In general: treat $k$ data symbols as the coefficients of a degree-$(k-1)$ polynomial, evaluate it at $n$ points, and send the values; any $k$ of them interpolate the original back. If a value is altered rather than lost, it strays off the curve and stands out among its collinear neighbours — which is why correcting an error costs twice what filling a gap costs: you must spend redundancy to find who is lying, then more to set it right.
Work in the finite field $\mathrm{GF}(2^8)$ — a "world of bytes" with exactly 256 elements and full arithmetic, generated by $\alpha$. The $k$ message bytes are the coefficients of $m(x)$, evaluated at $n\le 255$ points to give the codeword. The parameters are $[n,k,n-k+1]$: the minimum distance is exactly $n-k+1$, so it corrects $t=\lfloor (n-k)/2\rfloor$ corrupted symbols, or fills $n-k$ losses whose positions are known.
That $n-k+1$ was not cleverly engineered; it is the direct consequence of an elementary algebraic fact: two distinct degree-$(k-1)$ polynomials agree at no more than $k-1$ points, so two codewords differ in at least $n-k+1$ positions — and the Singleton bound says no code can exceed that, so Reed–Solomon sits flush against the ceiling. Lovelier still is the change of viewpoint: Hamming preserves distance by placing points geometrically, Reed–Solomon by algebra. Change the lens and optimality stops being the reward of a careful search and becomes an incidental corollary of a theorem.
A scratch on a CD ruins thousands of consecutive bits, but RS works in bytes, so a wholly destroyed byte counts as a single error — add interleaving to scatter the burst across code blocks and a 2.4 mm scratch still plays through. Closer to home is erasure coding in distributed storage: HDFS, Ceph and S3 replace three-way replication with RS(10,4), tolerating any 4 simultaneous disk failures while storage overhead drops from 200% to 40%. The cost curve of cloud storage was pushed down by a polynomial.
A QR code is the three previous ideas fused into engineering. The large squares at three corners are finder patterns — the phone locates them first and thereby learns orientation and perspective, so tilted or upside-down scans still read. Data fills the grid along a zigzag path under a layer of Reed–Solomon parity; four correction levels exist, the highest (H) carrying about 30% redundancy — which is precisely why a logo stamped over the centre still scans: the covered region is, mathematically, a scratch.
One further step is easily overlooked and rather elegant: masking. The data may by chance produce broad black or white regions, or accidentally mimic a finder pattern. So the encoder XORs the data against each of 8 fixed patterns and keeps whichever balances black and white best — a reversible layer of pseudo-randomness to break up unlucky regularity.
Practical RS encoding uses this systematic form: shift the message polynomial $m(x)$ up by $2t$ and divide by the generator polynomial $g(x)$, appending the remainder as parity symbols. The codeword $c(x)$ is then divisible by $g(x)$ — equivalently, it vanishes at $\alpha^0,\dots,\alpha^{2t-1}$. To decode, evaluate the received polynomial at those points: a non-zero result means an error, and the system of equations woven from those non-zero values solves for where the errors are and by how much.
The beauty is the distance the abstraction travelled. Finite fields were dreamt up by Galois before he turned twenty, purely to answer why the quintic has no radical solution; two centuries later they run billions of times a day in front of your phone's camera — a tool built to understand impossibility, finally deployed against coffee stains.
There is structural beauty too: the three defences are orthogonal — finder patterns, RS, and masking each guard a distinct failure dimension without interfering. Good engineering is isomorphic to good mathematics: split a coupled problem into independent ones.
Mobile payments, boarding passes and supply-chain tracking all ride on this; industry's Data Matrix codes use the same RS core, laser-etched into metal parts and still readable after cutting fluid and heat. Masahiro Hara invented the format in 1994 to track car components, and Denso's decision to waive patent royalties is what made it universal.