136
Part Three · D · Error correction and fault tolerance

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 pp, the majority fails only when two or three flip:

pL=3p2(1−p)+p3=3p2−2p3p_L = 3p^2(1-p) + p^3 = 3p^2 - 2p^3

At p=1%p = 1\% that is 2.98×10−42.98\times10^{-4}, more than thirty times better, for three times the cost. Longer repetition codes suppress errors further, but only when p<1/2p < 1/2: 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 GG maps 4 data bits to a 7-bit codeword; the parity-check matrix HH satisfies HGT=0(mod2)HG^\mathsf T = 0 \pmod 2, so every codeword has zero syndrome HcH\mathbf c. A single flipped bit produces a syndrome equal to that bit’s column of HH, 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 [n,k,d][n, k, d] encodes kk bits into nn with distance dd, correcting ⌊(d−1)/2⌋\lfloor (d-1)/2\rfloor errors. Codes trade rate k/nk/n 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.

What does a syndrome reveal?tap
Which parity checks failed, which identifies the error, not the data.
How many errors does a distance-3 code correct?tap
One.
Why are LDPC codes efficient to decode?tap
Each check touches few bits, so belief propagation’s local messages are cheap.

And one to work out. What is the 3-bit repetition code’s failure probability at p=0.01p = 0.01?

p_L =

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.

Next · Chapter 137
Quantum codes: Shor, Steane, CSS

Measure errors without measuring the data. This was widely thought impossible until 1995.

Turn the page