ISEGORIA / MATH ENCYCLOPEDIA
Coding theory: correcting errors
Every stored or transmitted bit can be flipped by noise, so a message is sent with redundancy arranged so that a few flips can be found and undone. The arrangement is geometry: codewords are points in the space of all bit strings, far apart in Hamming distance, the number of positions in which two strings differ. A received word is decoded to the nearest codeword, and a code with minimum distance d corrects any ⌊(d − 1)/2⌋ errors. Hamming built the first such code from three parity checks whose failures spell out the position of the error in binary. Counting how many balls fit in the space limits how good any code can be, and Reed and Solomon replaced bits by values of a polynomial over a finite field, which reaches the best possible distance and protects every CD, QR code and deep-space probe.
Before you begin: Binary numbers, vectors and matrices, polynomials, modular arithmetic
Predict, manipulate, then test yourself: every experiment ends with practice questions that are generated fresh at three levels. Graphs illustrate the mathematics; they do not replace a proof.
1. Hamming(7,4): the syndrome points at the error
Number the seven bits of a word 1 to 7 and put parity bits at positions 1, 2 and 4. Parity bit 1 makes the bits whose position has a 1 in its last binary digit (1, 3, 5, 7) add to an even number; bit 2 does the same for 2, 3, 6, 7, and bit 4 for 4, 5, 6, 7. Positions 3, 5, 6 and 7 carry the four message bits. If one bit flips, exactly the checks containing its position fail, and reading the failed checks as a binary number gives the position. In the Venn diagram each check is a circle and each position a region. Flip bits and watch the odd circles; then compare the chance that a 4-bit message arrives wrong with and without the code.
Worked example. The message 1011 goes to positions 3, 5, 6, 7. Check 1 covers positions 3, 5, 7, holding 1, 0, 1, so bit 1 is 0; check 2 covers 3, 6, 7, holding 1, 1, 1, so bit 2 is 1; check 4 covers 5, 6, 7, holding 0, 1, 1, so bit 4 is 0. The codeword is 0110011. If bit 6 flips, the received word is 0110001: check 1 (positions 1, 3, 5, 7: 0, 1, 0, 1) passes, check 2 (positions 2, 3, 6, 7: 1, 1, 0, 1) fails, check 4 (positions 4, 5, 6, 7: 0, 0, 0, 1) fails. The syndrome 110 in binary is 6. With bits flipping independently at \(p=0.01\), a raw 4-bit message is wrong with probability \(1-0.99^4=0.039\), the coded one only when two or more of seven bits flip: \(0.0020\).
Watch out. The code spends three extra bits for every four, so the comparison is per message, not per use of the channel; at the same energy per message bit the advantage is smaller. Two flips are always miscorrected into a third wrong bit, and three can turn one codeword into another and pass unnoticed. Real channels have bursts, which is why practical systems interleave or use the larger codes of the next two experiments.
Why does the syndrome depend only on the error, not on the message?
Because every codeword satisfies all three checks, \(H\mathbf c^{\mathsf T}=\mathbf 0\), and the checks are linear. The received word is \(\mathbf r=\mathbf c+\mathbf e\) (addition mod 2), so \(H\mathbf r^{\mathsf T}=H\mathbf c^{\mathsf T}+H\mathbf e^{\mathsf T}=H\mathbf e^{\mathsf T}\). For a single error in position \(i\) this is column \(i\) of \(H\), and Hamming chose the columns to be the numbers 1 to 7 in binary.
2. Balls in Hamming space
All bit strings of length \(n\) form the corners of an \(n\)-dimensional cube, with an edge between strings that differ in one bit, so the Hamming distance is the length of the shortest path along edges. A code is a set of corners. If its codewords are at least \(d\) apart, the balls of radius \(t=\lfloor(d-1)/2\rfloor\) around them do not overlap, and a received word inside a ball decodes to its centre. The balls cannot hold more corners than the cube has: \(M\,V(n,t)\le 2^n\), the Hamming bound. A code that meets it exactly is perfect. Choose a code, move the received word around the cube, and compare the code with the asymptotic limits on the right.
Worked example. The repetition code {000, 111} has \(d=3\), so \(t=1\). Each ball holds a codeword and its three neighbours, \(V(3,1)=1+3=4\), and two balls hold \(2\times4=8=2^3\) corners: the whole cube, a perfect code. Received 001 decodes to 000. For \(n=4\), {0000, 1111} has \(d=4\) and still \(t=1\); the two balls hold \(2\times5=10\) of the 16 corners, and the six words of weight 2 are tied. Hamming(7,4) has \(16\times V(7,1)=16\times8=128=2^7\) and is perfect; so is the Golay code, \(2^{12}\times V(23,3)=2^{12}\times2048=2^{23}\).
Watch out. The 4-cube is drawn as a cube inside a cube; distances along its edges are exact, but straight-line distances in the picture are not Hamming distances. The curves on the right are the limits as \(n\to\infty\) with \(d/n\) fixed. Perfect binary codes are rare: apart from trivial ones, every perfect binary code has the parameters of a Hamming code or of the binary Golay code. Whether the Gilbert–Varshamov bound is the true limit for binary codes is still an open question.
Why can a code with d = 4 still correct only one error?
Two errors can land on a word at distance 2 from two codewords at once, halfway between them, and nothing tells the decoder which way to go. Correcting \(t\) errors needs the balls of radius \(t\) to be disjoint, which needs \(d\ge 2t+1\). The extra distance is not wasted: a \(d=4\) code corrects one error and at the same time detects any two.
3. Reed–Solomon: a polynomial survives damage
Work in the field of integers mod 13, where every nonzero number has an inverse. Write the \(k\) message symbols as the coefficients of a polynomial \(P\) of degree below \(k\) and send its values at \(n\) points. Any \(k\) correct values determine \(P\), just as two points fix a line, so two codewords agree in at most \(k-1\) places and the minimum distance is \(n-k+1\), the most the Singleton bound allows. Berlekamp and Welch decode by looking for an error locator \(E\), a polynomial vanishing at the bad positions, together with \(Q=PE\): the conditions \(Q(x_i)=y_iE(x_i)\) are linear, and one division gives \(P\). Corrupt or erase symbols and watch the decoder until the budget runs out.
Worked example. Over GF(13) take \(P(x)=5+2x^2\) (\(k=3\)) and send its values at \(x=1,\dots,9\): 7, 0, 10, 11, 3, 12, 12, 3, 11, so \(d=7\). Change the symbols at \(x=2\) and \(x=5\) to 4 and 7, and erase the one at \(x=7\). Eight values survive, so the decoder can afford \(\lfloor(8-3)/2\rfloor=2\) errors. Solving the linear system gives \(E(x)=x^2+6x+10\), which is \((x-2)(x-5)\) because \(-7\equiv6\) mod 13, and dividing \(Q\) by \(E\) returns \(5+2x^2\). One more error would make \(2e+s=7>6\), and the decoder can no longer guarantee anything.
Watch out. Real Reed–Solomon codes use the field with 256 elements, so that a symbol is a byte, and lengths up to 255; GF(13) keeps the picture small. Past the budget the decoder either reports failure or, less often, lands on a different codeword, as the experiment shows. The grey line joining the decoded values is only a guide for the eye: over a finite field a polynomial is a set of points, not a curve.
Why is an erasure only half as expensive as an error?
An erasure tells the decoder where the damage is, so it costs one unknown value; an error hides its position as well as its value, so it costs two. Deleting the \(s\) erased points leaves a Reed–Solomon code of length \(n-s\) and distance \(n-s-k+1\), which corrects \(\lfloor(n-s-k)/2\rfloor\) errors. That is the condition \(2e+s\le n-k\).