Error-correcting codes

Every channel makes mistakes. On the digital modulation page, noise pushed symbols into the wrong part of the constellation, echoes smeared them together, and the best a receiver could do was keep the mistakes rare. Its checksum could say a message had arrived corrupted, but not fix it.

An error-correcting code adds carefully chosen extra bits, so that the receiver can work out what was sent even when some bits arrive wrong. It’s why a scratched CD still plays, why a QR code with a coffee stain still scans, why phones and Wi-Fi work at the edge of their range, and why Voyager’s pictures still arrive from beyond the planets.

This page starts with the obvious idea, sending everything more than once, and finds out what it really costs. Then it builds up to the codes that real systems use, and ends by putting one into the acoustic modem.

A few terms first:

The data bits are the ones we want to send. The code turns each group of them into a longer codeword, which is what’s actually sent.
The rate of a code is the data bits divided by the bits sent. Sending everything twice has a rate of ½.
Most of this page uses the simplest channel there is: each bit, independently, arrives flipped (a 0 as a 1, or a 1 as a 0) with some probability.

The figures send a small picture made of bits, the words “CODES FIX ERRORS”, so you can see the errors: each wrong pixel is drawn in red.

1 · Repeat everything

The obvious code: send every bit three times, and let the receiver take a majority vote. 000 or 001 means 0; 110 or 111 means 1. One flip in three can’t change the vote. Two flips can, but that’s much less likely.

Top: the picture sent once through the channel. Bottom: each bit sent several times, decoded by a majority vote. The readouts count errors over 120,000 data bits.

With 5% of bits flipped, sending each bit 3 times leaves 0.74% of the data wrong (0.73% in theory: two or three of the three copies must flip). 5 times leaves 0.11%, and 7 times 0.013%. Every extra copy helps, but the cost is steep: 7 times as many bits sent, for the same message.

2 · Detecting errors: parity and checksums

A cheaper idea only detects errors. Add one parity bit to every block of 8 data bits, chosen so that the block always has an even number of 1s. If one bit flips, the count becomes odd, and the receiver knows the block is wrong, though not which bit. It can ask for the block again, or throw it away.

Parity’s weakness is obvious: two flips cancel out. A checksum like the modem’s CRC-16 is a much stronger version of the same idea: 16 check bits, calculated from the whole message so that almost any corruption changes them.

16 blocks as they arrive: 8 data bits, then the parity bit. Flipped bits have red boxes; a block whose parity check fails is shaded orange (“caught”); a corrupted block that passes is shaded red (“missed”).

The readouts count over 40,000 blocks and 3,000 messages of 64 bytes. With 2% of bits flipped, 6,704 blocks arrive with errors. Parity catches 92.5% of them, and misses the 503 with an even number of flips. At 5%, it misses 2,637 of 14,912. The CRC-16 catches every one of the 3,000 corrupted messages.

3 · Hamming codes: finding which bit

In 1950, Richard Hamming was tired of coming back on Monday morning to find that his weekend’s calculations on the Bell Labs computer had stopped at the first error. The machine could detect errors, but not fix them. So he found a way to work out which bit was wrong.

Use several parity bits, each checking a different group of data bits. In the Hamming (7,4) code, 3 parity bits protect 4 data bits. Draw each parity bit’s group as a circle, overlapping like a Venn diagram:

p1 makes the circle with d1, d2 and d4 even
p2 makes the circle with d1, d3 and d4 even
p3 makes the circle with d2, d3 and d4 even.

Now if any one bit flips, a particular set of circles fails its check, and each bit sits in a different set. d4 is in all three circles, d1 in p1’s and p2’s, p1 in only its own. So the failing circles point at exactly one bit, and the decoder flips it back.

The 7 bits of one codeword, each in the circles that check it. Choose the 4 data bits, and choose a bit for the channel to flip. Circles whose check fails turn red.

Flip any single bit, and the failing circles name it: the decoder fixes it, and the data comes out right. Now flip a second bit as well. The circles still name a single bit, but the wrong one, and “fixing” it makes three errors. The code corrects one error per codeword. Any more, and it makes things worse.

The pattern of failing checks is called the syndrome. Write each bit’s set of circles as a column of three 0s and 1s, and the seven columns are the seven different non-zero 3-bit numbers:

	d1	d2	d3	d4	p1	p2	p3
p1’s check	1	1	0	1	1	0	0
p2’s check	1	0	1	1	0	1	0
p3’s check	0	1	1	1	0	0	1

That table is the code’s parity-check matrix. The syndrome is the column of whichever bit flipped. With more parity bits there are more columns to go round: 4 parity bits make a (15,11) code, 5 make (31,26), and the rate keeps rising.

4 · Distance, and a fair comparison

Why does one code correct more than another? Count the bits in which two codewords differ: their Hamming distance. The smallest distance between any two codewords is the code’s minimum distance, d:

Repeating 3 times: the codewords are 000 and 111, so d = 3.
Parity on 8 bits: any two valid blocks differ in at least 2 bits, so d = 2.
Hamming (7,4): any two of its 16 codewords differ in at least 3 bits, so d = 3.

Picture each codeword with a “bubble” of everything within one flip of it. If d = 3, the bubbles never overlap, so a received word with one error lies in exactly one bubble, and the decoder can tell which codeword was sent. In general a code corrects up to (d − 1)/2 errors, and detects up to d − 1.

So repetition and Hamming (7,4) both correct one error. But repeating 3 times has a rate of ⅓, and Hamming (7,4) a rate of 4/7. To compare codes fairly, there’s one more thing to account for. A transmitter has a fixed amount of energy to spend on each data bit. A code that sends 3 bits for every data bit must give each one a third of the energy, and weaker bits flip more often. The fair measure is the energy per data bit, $E_b/N_0$ .

Top: data bits wrong after decoding, against how often each sent bit flips. Bottom: the same codes sending BPSK through noise, against $E_b/N_0$ : each code’s bits share the energy of the data bits. The curves are exact: for repetition, by counting how many copies must flip; for Hamming (7,4), by adding up all 128 possible error patterns.

Against flips per sent bit, every code helps, and repetition looks best. But at the same $E_b/N_0$ = 8 dB, with no code 1.9 × 10⁻⁴ of the data is wrong. Repeating 3 times makes it worse, 1.2 × 10⁻³: each copy has a third of the energy, so flips far more often than the vote can make up for. Hamming (7,4) does better, but only a little: 1.2 × 10⁻⁴.

That’s the real challenge: a code has to correct more errors than it causes by spending energy on extra bits. Repetition never manages it. The rest of this page is about codes that do, by a much bigger margin.

5 · Bursts and interleaving

Real channels don’t flip bits independently. A scratch, a fade, or a burst of interference ruins many bits in a row, and then a Hamming codeword with one error correctable gets three or four, and is lost.

The fix is to interleave. Write the codewords into a table row by row, send it column by column, and undo that at the receiver. Bits that were neighbours in the channel now belong to different codewords, so a burst is spread out into single errors, one per codeword, which the code can fix. The table needs more rows than the longest burst.

Hamming (7,4) through a channel that is usually perfect, but 3% of the time is in a “bad” spell, flipping half the bits. Top: the picture sent with no code. Bottom: with the Hamming code, with or without interleaving.

With bursts 10 bits long on average, 1.4% of bits flip. Hamming alone barely helps: 1.4% of the data is still wrong, because each burst lands several errors in the same codeword. Interleaved 32 deep, only 0.21% is. Longer bursts need a deeper table.

6 · Reed–Solomon codes: whole bytes at a time

Hamming codes think in bits. Reed–Solomon codes (Irving Reed and Gustave Solomon, 1960) think in symbols, usually whole bytes. To a Reed–Solomon code, a byte with one bit wrong and a byte with all eight wrong are the same: one wrong symbol. That makes them naturally good at bursts.

The idea behind them is polynomials. Through any 2 points you can draw exactly one straight line, and through any k points exactly one polynomial of degree k − 1. Treat the k message bytes as the polynomial’s coefficients, and send its values at n points, more than k of them. Any k correct values are enough to rebuild the polynomial, so the extra n − k values let the receiver work out which values are wrong, and fix up to (n − k)/2 of them.

To make the arithmetic work with bytes, the code uses a finite field: a number system with just 256 values, where adding is a bitwise XOR and multiplying is defined so that every non-zero value can be divided by. Nothing ever overflows a byte, and all the usual algebra still works.

The most widely used version is RS(255, 223): 223 message bytes, 32 check bytes, correcting any 16 wrong bytes per codeword. It has flown on deep-space missions since Voyager, and is in many satellite links. CDs use two smaller Reed–Solomon codes, cross-interleaved with each other.

The synthetic voice from the voice coding page, as 16-bit samples, one byte at a time, like a CD’s data. Three scratches each destroy a run of bytes. Top: sent with no code. Bottom: coded with RS(255, 223), optionally interleaving several codewords byte by byte. Red marks samples that are still wrong.

With scratches of 400 bytes and no interleaving, each scratch lands 400 wrong bytes in one or two codewords, far more than the 16 each can fix: 6 codewords are beyond repair. Interleaving 16 codewords deep spreads each scratch over 16 codewords, still 25 bytes each: 48 beyond repair. 64 deep brings it to about 6 per codeword, and all 1,194 destroyed bytes are corrected. Interleaved 64 deep, even 1,000-byte scratches are fixed; 2,000 are too many.

A real CD player goes further. Its cross-interleaved code can correct about 3,500 bits in a row, roughly 2.4 mm of track. When even that fails, it doesn’t play garbage: it fills the gap by interpolating between the good samples either side. QR codes, DVDs, Blu-ray, DSL and digital TV all use Reed–Solomon codes too.

7 · Convolutional codes and the Viterbi algorithm

The codes so far chop the data into blocks and protect each block separately. A convolutional code works on a continuous stream of bits, and spreads each bit’s influence over the next few things it sends.

It’s built from a shift register: a row of boxes, each holding one bit. Here’s the small one used in the next two figures, three boxes long:

new  prev1  prev2

Each time a data bit arrives, it goes into the new box, and everything slides one place to the right. The bit that was in prev2 falls off the end. Then the encoder sends two coded bits, each made by XORing a fixed selection of the three boxes:

A = new ⊕ prev1 ⊕ prev2 (all three boxes)
B = new ⊕ prev2 (the first and last, skipping the middle)

These two recipes are the code’s generators. They’re usually written as the boxes they use, in binary, then in octal: A’s boxes are 111, which is 7, and B’s are 101, which is 5.

So each step takes in one data bit and sends out exactly two. But each data bit stays in the register for three steps: it arrives as new, then it’s prev1, then prev2, and only then does it fall out. During all three, it takes part in A and B. So every data bit helps make three pairs in a row, six coded bits in all, and a flipped coded bit still leaves five others carrying its influence. That’s what the decoder will use.

The number of boxes, 3 here, is the code’s constraint length K: how many data bits each coded bit depends on.

The K = 3 encoder sending 8 data bits, then 2 zeros to empty the register. Step through it: the data waiting to go in (top), the register, the wiring from the boxes to the two XORs, and every pair sent so far. Choose a data bit to follow, and it’s outlined in orange as it slides through the register, with the three pairs it helps make shaded.

Data bit 1 (a 1) arrives at step 1. The register holds 1 0 0, so A = 1 ⊕ 0 ⊕ 0 = 1, B = 1 ⊕ 0 = 1, and the encoder sends 11. At step 2 a 0 arrives and the 1 moves to prev1: the register holds 0 1 0, and it sends 10. At step 3 it’s in prev2, and the encoder sends 00. Then it falls out. Those three pairs are the ones shaded.

The two older boxes, prev1 and prev2, are all the encoder remembers: that’s its state. Two bits make 4 possible states (00, 01, 10 and 11), and each new bit moves the encoder from one state to another, sending a particular pair on the way. Drawn against time, the states and the possible moves between them make a trellis, and every possible message is a path through it.

The decoder’s job is to find the path whose coded bits are closest to what arrived. Trying every path is hopeless: there are 2 to the power of the message length. Andrew Viterbi’s algorithm (1967) does it a step at a time, keeping one number for each state.

Moves. When bit b goes in at state (prev1, prev2), the encoder moves to (b, prev1): the new bit becomes prev1, and the old prev1 becomes prev2. So two moves leave every state, one for a 0 and one for a 1, and two moves arrive at every state, from the two states that differ only in the bit that has just fallen out. Each move has an expected pair: what the encoder would send, making it.

Scores. Each node (a state, at a step) gets a score: the fewest received bits that disagree with the expected pairs, along any path from the start to that node. The encoder starts empty, at state 00, with a score of 0.

Choosing. At each step, every state looks at its two incoming moves. Each one’s total is the score it comes from, plus its cost: how many of the two received bits disagree with its expected pair (0, 1 or 2). The state keeps the smaller total, and discards the other move for good. The kept move is the state’s survivor. This is safe because two paths that reach the same state at the same step have the same future: whatever comes next adds the same cost to both, so the one that’s behind can never catch up.

Pruning. Every state keeps exactly one parent at every step, so no node is ever thrown away. What dies out are paths: when both moves out of a node lose at the next step, nothing descends from it, and its whole history drops out of contention.

Reading out. The two closing zeros bring the encoder back to state 00. So at the end, the decoder starts at 00 and follows the survivors backwards, and that’s the best path. It doesn’t need to push bits back through the register: the first digit of each state on the path is the bit that had just gone in, because the newest bit always lands in prev1.

The K = 3 code sending the same 8 data bits, through a channel that flips the bits you choose. Above the trellis: the data, and the pairs received (red: flipped). Each node shows its score. Blue lines are survivors (solid: a 0 went in; dashed: a 1). Step to the end, and the best path is drawn in orange, with the bits read off it underneath (“decoded”).

Choose a node to look at, and its two incoming moves are drawn in bold, each labelled with the pair it expects and the total it would give: the kept one in blue, the discarded one in red. With one error, at step 3 state 00 (where 01 arrived), the move from 01 expects 11, costs 1 and totals 0 + 1 = 1; the move from 00 expects 00, also costs 1, but totals 3 + 1 = 4. So 00 keeps the move from 01.

The flipped bit costs the true path 1 at step 3, and a wrong path costs the same there. But the true data bit shapes the next two pairs as well, and the wrong paths disagree with them, so their scores keep growing. At the end the true path’s score is 1, the single flipped bit, and it decodes 10110010, right.

Two errors anywhere are always corrected too: this code’s codewords differ in at least 5 bits (its free distance). Three errors spread out are usually fine. Three close together can fool it: try them.

This is the same idea as the pitch tracker’s search for the best path through candidate pitches over time: it’s dynamic programming, and the Viterbi algorithm is one of its most famous uses. Phones, Wi-Fi, satellite TV and deep-space probes have all decoded convolutional codes with it.

8 · Soft decisions

So far, the receiver decided each bit (0 or 1) and then handed the bits to the decoder. That throws information away. A received value of +0.9 is a confident 0; +0.1 is a 0 only just. Deciding first makes them look the same.

With soft decisions, the decoder gets the received values themselves, and scores each path by how far its expected signal is from what arrived. A doubtful bit then counts for little, and a confident one for a lot. Viterbi’s algorithm doesn’t care which score it uses, so this costs almost nothing.

The picture through BPSK and noise at the chosen $E_b/N_0$ : with no code, with a K = 7 convolutional code (64 states) decoded from hard decisions, and decoded from soft ones. Below: data bits wrong against $E_b/N_0$ : no code (in theory), Hamming (7,4) (exact), and the K = 7 code both ways, measured on 40,000 bits per point as the figure loads.

At $E_b/N_0$ = 3 dB, with no code 2.3% of bits are wrong. Both codes decoded from hard decisions do worse: 3.2% for Hamming (7,4), and 3.4% for the K = 7 code. From soft decisions, the K = 7 code gets only 0.03% wrong. On the curves, soft decisions are worth about 2 dB.

This K = 7 code (generators 171 and 133, in octal) is the one NASA flew on Voyager, and the one in Wi-Fi’s original 802.11a and g standards. Deep-space missions wrap a Reed–Solomon code around it: when the Viterbi decoder does make a mistake, it makes a short burst of them, which is exactly what Reed–Solomon codes are good at. That’s a concatenated code.

How much better could any code do? Claude Shannon worked out the answer in 1948, before any of these codes existed. That’s the subject of a later page, on the Shannon limit.

9 · Back to the modem

The acoustic modem’s OFDM sends every symbol twice, on two carriers far apart, and combines the copies. That’s a repetition code, with a rate of ½. The modem now has a third option: coded OFDM. Every data carrier carries different bits, coded with the K = 7 convolutional code (also rate ½, so the same air time), interleaved so neighbouring coded bits travel on carriers far apart, and decoded with soft decisions. Each carrier’s soft values are weighted by how strongly it arrived, so a carrier in a notch counts for little.

The same message, sent both ways through the made-up echoey room as the noise grows, 12 times at each level. The bars count messages whose checksum matched.

With plenty of signal, both get every message through. As the noise grows, the coded modem holds on for longer: at 4 dB it delivers 10 of the 12 messages, against 6 for sending everything twice, and at 2 dB, 8 against 4. Both fail eventually. When the coded one fails, it fails with a burst of wrong bits, which is why deep-space links add a Reed–Solomon code on top.

You can try coded OFDM with your own loudspeaker on the digital modulation page: it’s the third option in its modem’s menu, with its own chirp, which rises and then falls. Its measured SNR comes out lower than the other OFDM option’s, even when the message arrives intact: it’s measured on each carrier before decoding, where the other is measured after the two copies have been combined. Working from worse symbols is exactly what the code is for.

Summary

Repetition fixes errors, but at the same energy per data bit it makes things worse.
Parity and checksums detect errors without fixing them. A CRC catches almost any corruption.
Hamming codes use overlapping parity checks, so the failing checks (the syndrome) name the wrong bit.
A code’s minimum distance d decides what it can do: correct (d − 1)/2 errors, or detect d − 1. The fair comparison is at equal energy per data bit.
Interleaving turns bursts into scattered errors. Reed–Solomon codes work on whole bytes, and fix bursts naturally: CDs, QR codes and deep-space links use them.
Convolutional codes are decoded by the Viterbi algorithm: keep only the best path into each state. Soft decisions let it use how sure each bit was, worth about 2 dB.