How Error-Correcting Codes Make Digital Communication Possible
Voyager 1 is more than 24 billion kilometers from Earth, transmitting with about 23 watts, roughly the power of a refrigerator light bulb. By the time its signal crosses that distance and reaches our largest dish antennas, it has spread out so much that it arrives as an astonishingly faint whisper, barely above the background noise.
Yet we still receive usable data. The trick isn't just bigger antennas. It's error-correcting codes: mathematics that detects and repairs corrupted bits automatically, so the message survives the trip.
Noise Doesn't Have to Mean Errors
Before 1948, engineers believed that the only way to reduce errors over a noisy channel was to send more slowly or with more power. Push the error rate toward zero and the data rate would have to drop toward zero too.
In 1948, Claude Shannon of Bell Labs proved that was wrong. His noisy-channel coding theorem showed that every channel has a capacity C. At any rate below C, there exist codes that make the error rate as small as you like. Noise sets a speed limit, not an accuracy limit.
For a channel with bandwidth B and signal-to-noise ratio S/N, the capacity is:
C = B × log₂(1 + S/N) bits per second
Step 1: Detecting Errors With Parity
The simplest code adds one parity bit so every group has an even number of 1s:
Data: 1011001
Parity: 0 (four 1s → already even)
Sent: 10110010
If one bit flips in transit, the count of 1s becomes odd and the receiver knows something went wrong.
Parity can detect any single-bit error but can't tell you which bit flipped, so it can't fix it. And if two bits flip, the errors cancel and go unnoticed.
Step 2: Correcting Errors With Hamming Codes
In the late 1940s, Richard Hamming was using a relay computer at Bell Labs. On weekends, when no operators were around, the machine would stop dead whenever it detected an error. After losing his work one weekend too many, he reportedly asked: if the machine can detect an error, why can't it locate and correct it?
His answer, published in 1950, was the Hamming code. The classic Hamming(7,4) code sends 4 data bits with 3 parity bits. Each parity bit checks a different overlapping group of positions:
| Parity bit | Checks positions |
|---|---|
| p₁ (position 1) | 1, 3, 5, 7 |
| p₂ (position 2) | 2, 3, 6, 7 |
| p₄ (position 4) | 4, 5, 6, 7 |
The groups follow the binary representation of each position. When a single bit flips, some parity checks fail. Write the failures as a binary number, the syndrome, and it spells out the position of the bad bit.
For example, if checks p₁ and p₄ fail but p₂ passes, the syndrome is 101₂ = 5. Flip bit 5 and the message is fixed. Practice reading those positions with the binary to decimal converter.
Step 3: Hamming Distance
The Hamming distance between two bit strings is the number of positions where they differ:
1011101
1001001
↑ ↑ → distance = 2
A code's power depends on its minimum distance d, the smallest distance between any two valid codewords:
- It can detect up to d − 1 errors
- It can correct up to ⌊(d − 1) / 2⌋ errors
Hamming(7,4) has d = 3, so it detects 2 errors and corrects 1. Designing a good code is really a geometry problem: spread codewords as far apart as possible in a space of bit strings.
Step 4: Burst Errors and Reed–Solomon
Real-world errors often come in bursts: a scratch on a disc or a lightning crackle wipes out many bits in a row. Reed–Solomon codes (1960) work on whole bytes instead of individual bits, treating data as coefficients of a polynomial over a finite field.
Audio CDs use a scheme called Cross-Interleaved Reed–Solomon Coding (CIRC). It can fully correct burst errors of about 3,500 bits, roughly 2.4 mm of track. That's why a lightly scratched CD still plays perfectly. The same family of codes protects QR codes, DVDs and deep-space missions.
Step 5: Modern Codes Near the Shannon Limit
For decades, practical codes fell well short of Shannon's capacity. Then two breakthroughs closed the gap:
- Turbo codes, introduced by Claude Berrou and colleagues in 1993, came within about 0.5 dB of the Shannon limit
- LDPC codes (Low-Density Parity-Check), invented by Robert Gallager in his 1960 doctoral thesis and rediscovered in the 1990s
Today LDPC codes are used in Wi-Fi, 5G data channels and digital TV. Gallager's idea was simply too computationally expensive for 1960s hardware.
Two Concepts Worth Knowing
Redundancy and Code Rate
The code rate is data bits divided by total bits sent. Hamming(7,4) has a rate of 4/7 ≈ 0.57. Lower rates add more protection but send data more slowly. Every system picks a trade-off.
Logarithms and Information
Shannon measured information in bits using base-2 logarithms. A channel with a signal-to-noise ratio of 1,000 has a capacity of log₂(1,001) ≈ 9.97 bits per second for every hertz of bandwidth. Try the numbers with the logarithm calculator.
Quick Answer: How Do Error-Correcting Codes Work?
Error-correcting codes add carefully calculated redundant bits to data. The receiver checks whether those bits are consistent. If not, the pattern of failed checks identifies which bits were corrupted so they can be fixed. Hamming codes fix single-bit errors, while Reed–Solomon and LDPC codes handle heavier noise.
Try Them Yourself
- Binary to Decimal Converter: decode a Hamming syndrome
- Base 2 to Base 10 Table: binary positions at a glance
- Base 2 Addition Table: XOR is addition without carrying
- Logarithm Calculator: compute channel capacity
- Number Theory Formulas: modular arithmetic behind parity
- The Mathematics Behind QR Codes: Reed–Solomon in your pocket
Write a 4-bit message, encode it with Hamming(7,4), flip one bit, and use the syndrome to find it. It's the same trick your phone performs millions of times a day.