Classical error correction
The Voyager probes, now beyond the edge of the solar system, send data home with a transmitter weaker than a fridge light. Your phone reads a QR code with a coffee stain on it. Both work because the data carry redundancy arranged so cleverly that errors can be found and fixed without knowing in advance where they will strike. Quantum error correction borrows every idea in this chapter, then has to overcome three obstacles classical codes never face.
On the plate: a noisy channel, and a code that repairs it.
Repetition
Send each bit three times and take the majority. If each copy flips independently with probability , the majority fails only when two or three flip:
At that is , more than thirty times better, for three times the cost. Longer repetition codes suppress errors further, but only when : below a threshold, adding redundancy helps; above it, it hurts. That word will matter enormously in Chapter 139. Established
Hamming’s code and syndromes
Richard Hamming, frustrated by weekend computer jobs failing at Bell Labs, found in 1950 a code that protects 4 data bits with only 3 extra bits. The generator matrix maps 4 data bits to a 7-bit codeword; the parity-check matrix satisfies , so every codeword has zero syndrome . A single flipped bit produces a syndrome equal to that bit’s column of , which names the culprit. The decoder never looks at the data, only at parities. Flip probability 0.050, then . The code is distance 3: any two codewords differ in at least 3 places, so it corrects one error per block. Its rate, 4/7, beats repetition’s 1/3. Established
Distance, rate, and LDPC codes
A code encodes bits into with distance , correcting errors. Codes trade rate against distance, and Claude Shannon’s theorem (Chapter 95) says the best codes approach channel capacity. Robert Gallager’s 1962 low-density parity-check (LDPC) codes approach it in practice: each check involves only a few bits and each bit only a few checks. Decoding uses belief propagation: bits and checks pass probability messages along the edges of the code’s Tanner graph until they agree. Rediscovered by David MacKay in the 1990s, LDPC codes now run in Wi-Fi, 5G and satellite TV. Their quantum versions, and belief-propagation decoders for them, are the subject of Chapter 141. Established
What you now have
Repetition codes and their failure probability, thresholds, generator and parity-check matrices, syndrome decoding, the Hamming code, the [n, k, d] trade-off, LDPC codes and belief propagation.
· · ·
Three questions to carry with you.
And one to work out. What is the 3-bit repetition code’s failure probability at ?
Sources: R. W. Hamming, Bell Syst. Tech. J. 29, 147 (1950). R. G. Gallager, Low-Density Parity-Check Codes (MIT Press, 1963). D. J. C. MacKay, Information Theory, Inference, and Learning Algorithms (CUP, 2003). T. Richardson and R. Urbanke, Modern Coding Theory (CUP, 2008). Checked by code: H·Gᵀ = 0 mod 2; Hamming block failure 0.0020 at p = 0.01 and 0.044 at p = 0.05.