Error-Correcting Codes
Memory chips, storage drives, and satellite links all silently fix errors that go unnoticed. The mathematics behind this goes back to one frustrated Bell Labs researcher in 1950.
- ECC RAM in servers corrects single-bit errors and detects double-bit errors automatically
- CDs use Reed-Solomon codes so deep scratches don't corrupt music
- QR codes can be read even when 30% of the pattern is damaged
Richard Hamming's Weekend Frustration
In 1950, Richard Hamming worked at Bell Labs on relay computers that would crash over weekends when no one was present to restart them after an error. He invented systematic error-correcting codes out of pure frustration. His (7,4) code became the foundation of modern coding theory.
The Codes That Closed the Shannon Gap
For 45 years after Shannon's 1948 theorem, engineers couldn't get within 3 dB of capacity. In 1993, Berrou and Glavieux unveiled Turbo codes at ICC-a conference where most attendees dismissed the results as too good to be true. Within a year, simulations confirmed: they came within 0.5 dB of capacity. LDPC codes, originally invented by Gallager in 1962 and forgotten, were rediscovered in the 1990s and proved equally powerful.
Hamming Codes
A Hamming (7,4) code encodes 4 data bits into 7 bits by adding 3 parity bits. The key insight: parity bits are placed at positions that are powers of 2 (1, 2, 4), and each parity bit covers a specific subset of positions.
Rate of a code = k/n (data bits / total bits). Hamming(7,4) has rate 4/7 ≈ 0.571. Adding redundancy always costs rate, but buys reliability. The fundamental tradeoff of coding theory.
Hamming(7,4) can correct how many bit errors per codeword?
Reed-Solomon Codes
Reed-Solomon codes operate on symbols (bytes or larger) rather than bits, and are based on polynomial interpolation over finite fields. An RS(n,k) code encodes k symbols into n symbols and can correct up to (n-k)/2 symbol errors.
The burst error handling of RS codes is exceptional. Since they operate on bytes, a scratch on a CD that wipes out 100 consecutive bits only destroys about 12-13 bytes-well within the correction capability of RS(32,28) used in audio CDs.
An RS(7,3) code encodes 3 data symbols into 7. How many symbol errors can it correct?
LDPC and Turbo Codes
Low-Density Parity-Check (LDPC) codes are linear codes defined by a sparse parity-check matrix H. Decoding uses belief propagation on a bipartite Tanner graph, passing messages between variable nodes (codeword bits) and check nodes (parity equations).
5G NR (New Radio) uses LDPC for data channels and Polar codes (discovered by Arıkan in 2008) for control channels. Polar codes are the first provably capacity-achieving codes with polynomial complexity-the theoretical pinnacle of Shannon's existence proof.
Better codes keep improving forever-there's always a more powerful code
Shannon capacity is a hard ceiling. Once a system is within a fraction of a dB, further code improvements yield negligible gains. The engineering focus shifts to complexity, latency, and practical constraints.
The capacity theorem is a mathematical absolute, not an engineering approximation. Modern codes have essentially closed the gap.
Why are LDPC codes called 'low-density'?
Coding Bounds and Tradeoffs
Coding theory has fundamental limits beyond Shannon capacity. The Singleton bound, Plotkin bound, and Hamming bound constrain what any code can achieve in terms of the tradeoff between rate R, minimum distance d, and alphabet size q.
| Code | Rate | Error Correction | Use Case |
|---|---|---|---|
| Hamming(7,4) | 4/7 ≈ 0.57 | 1 bit error | ECC memory |
| RS(255,223) | 0.875 | 16 byte errors | Deep space, DVB |
| Turbo (3GPP) | 1/3 to 1 | Near Shannon | 4G LTE |
| LDPC (802.11n) | 1/2 to 5/6 | Near Shannon | Wi-Fi |
| Polar (5G NR) | varies | Capacity-achieving | 5G control channels |
A code needs to correct t errors. What minimum Hamming distance d is required?
Error-Correcting Codes: Key Takeaways
- Hamming codes correct 1 bit error; their structure is based on binary parity checks
- Reed-Solomon codes work on symbol bursts; used in CDs, QR codes, and space probes
- LDPC and Turbo codes approach Shannon capacity using iterative belief propagation
- The rate-distance tradeoff is fundamental: more protection costs more redundancy
- To correct t errors, minimum distance d ≥ 2t+1 is required
Codes in Practice
Modern systems stack multiple codes. A 5G phone uses Polar codes for control, LDPC for data, and CRC for error detection-all within a single frame. Understanding capacity bounds reveals exactly how much room remains for improvement.
Вопросы для размышления
- Why didn't LDPC codes get adopted immediately after Gallager invented them in 1962?
- QR codes with 30% redundancy can be read even when heavily damaged. How does this map to Reed-Solomon parameters?
- When designing a storage system where errors come in bursts (scratches), which code family is preferable: Hamming or Reed-Solomon? Why?