LDPC, turbo and polar codes

The Shannon limit page ended with a puzzle. Shannon proved that good codes exist: even codes with codewords picked by tossing coins come as close to the limit as you like, given long enough blocks. But decoding a random code means comparing what arrived with every codeword, and with 1,000-bit blocks at rate ½ there are $2^{500}$ of them. For 45 years, the codes that could be decoded quickly sat several decibels from the limit.

The codes that closed the gap all answer the puzzle the same way. Instead of one giant decision (“which of $2^{500}$ codewords was it?”), they make thousands of small, local ones, and let them talk. Each small part of the decoder works out what it can from the little it sees, tells its neighbours, listens to what they say back, and tries again. After a few dozen rounds of this message passing, the whole decoder agrees on an answer, and it’s almost always the right one.

This page builds that idea up from the Hamming code on the error-correcting codes page, then runs three modern codes that use it: LDPC codes (in Wi-Fi, 5G and digital television), turbo codes (in 3G and 4G phones), and polar codes (in 5G). It ends by putting an LDPC code into the acoustic modem.

As on the earlier pages:

$E_b/N_0$ is the energy per data bit against the noise’s power per hertz, the fair way to compare codes (defined here).
Every code here has a rate of ½: one data bit for every two bits sent. At that rate, Shannon’s limit is $E_b/N_0$ = 0 dB, or 0.19 dB if each bit sent is +1 or −1, as with BPSK (section 8 of the Shannon page).

1 · Parity checks as a picture

The Hamming (7,4) code has 4 data bits (d1 to d4) and 3 parity bits (p1 to p3). Each parity bit makes one check come out even: check A says d1, d2, d4 and p1 must contain an even number of 1s; check B says the same of d1, d3, d4 and p2; check C of d2, d3, d4 and p3. On the error-correcting codes page these were three overlapping circles.

Here they’re drawn another way: bits along the bottom, checks along the top, and a line wherever a check covers a bit. That’s a Tanner graph, after Michael Tanner, who introduced it in 1981. Everything on this page happens on graphs like this one.

The Hamming (7,4) code’s graph. Choose the data bits, and the parity bits are filled in so every check is even. Then click any bit to flip it, as noise would, and watch which checks notice. A filled circle is a 1.

Flip one bit, and the checks covering it turn odd. Every bit is covered by a different set of checks, which is why one flip can always be found. Flip d1, for example, and checks A and B turn odd while C stays even: only d1 is covered by A and B but not C.

2 · The naive decoder: bit flipping

The graph suggests a decoder. A check that comes out odd knows that one of its bits is wrong, but not which, so it blames all of them. A bit that’s blamed by most of its checks is probably the culprit: flip it, and look again. Repeat until every check is even.

That’s bit flipping, and Robert Gallager described it in 1962, in the same thesis that introduced LDPC codes. The figure runs it on the Hamming code, and below, on a much bigger code: 2,000 bits and 1,000 checks, each bit covered by 3 checks, which section 7 comes back to.

Top: bit flipping on Hamming (7,4), round by round. Under each bit, its blame: how many of its checks are odd. Each round flips the bits with the most blame. Orange rings mark the bits that are really wrong, which the decoder can’t see. Bottom: the big code with bit flipping, through a channel that flips each bit with the chance shown, 40 blocks at each chance. The red line is Shannon’s limit for rate ½.

With one error in d2, checks A and C are odd, and d2 and d4 both get the most blame (2), so both flip. Now d4 is wrong instead, and in the next round it takes the blame alone and flips back: two rounds, and the word is right. With two errors, in d1 and d3, the decoder flips its way to a word that passes every check, but it’s a different codeword: the data comes out wrong, and nothing in the checks can say so.

The big code fares better. It corrects every block when up to 2% of bits are flipped, 85% of blocks at 3%, 47% at 4%, and only 17% at 5%. But Shannon says a rate-½ code can cope with 11%.

Bit flipping throws away almost everything: a bit is either right or wrong in its eyes, and a check is either odd or even. A bit that arrived very clearly and a bit that arrived as a coin toss look the same. The soft decisions on the ECC page were worth about 2 dB to the Viterbi decoder, and a decoder on a graph can use them too. It first needs a way to say how sure it is about a bit.

3 · Soft information in one number

After BPSK and noise, a bit sent as 0 arrives as about +1, and a 1 as about −1, give or take the noise. A value that arrives at +0.9 was almost certainly a 0; one at +0.1 could easily have been either.

The log-likelihood ratio (LLR) puts that in one number. It compares how likely the received value is if a 0 was sent with how likely it is if a 1 was sent, and takes the natural logarithm:

\text{LLR} = \ln \frac{\text{chance of this value, if 0 was sent}}{\text{chance of this value, if 1 was sent}}.

Its sign says which way the bit leans (positive for 0, negative for 1), and its size says how sure: 0 means no idea, and every extra 1 multiplies the odds by $e$ ≈ 2.7. With Gaussian noise of standard deviation σ, the two chances are bell curves centred on +1 and −1, and their ratio works out to something simple:

\text{LLR} = \frac{2y}{\sigma^2},

where $y$ is the received value. The noisier the channel, the less any reading counts.

LLRs have one property that makes everything else on this page work: independent evidence adds. If the same bit is read twice, with independent noise, the LLR of both readings together is just the sum of their LLRs. That’s because chances multiply, and logarithms turn multiplying into adding.

Top: how likely each received value is, if 0 was sent (blue) or 1 (orange), at the chosen noise. The black line is the received value; the dots are the two heights. Bottom: the LLR, the logarithm of the ratio of those heights, against the received value: a straight line. Tick a second reading to add another, independent reading of the same bit.

With noise σ = 0.80, a reading of +0.30 has an LLR of +0.9: the bit is 0 with a chance of 71.9%. A second reading of +0.60 has an LLR of +1.9. Together, the LLR is their sum, +2.8, and the chance is 94.3%.

To turn an LLR back into a chance: the bit is 0 with probability $1 / (1 + e^{-\text{LLR}})$ .

4 · What one check can tell a bit

A check can’t see any bits directly. All it knows is that its bits add up to an even number. But that’s enough to tell each bit something, given what the others look like. What a check tells one of its bits is called a message. It’s an LLR, like the bits’ own, worked out only from the check’s other bits, and it’s the basic step of everything in the next two sections.

Take a check covering three bits, X, Y and Z, and work out its message to Z. If X and Y are both surely 0, then Z must be 0 too, to keep the check even. If X is surely 0 and Y surely 1, then Z must be 1. So the message to Z is the “sum” of X and Y: the same as both if they agree, the opposite if they don’t. If X is doubtful, though, the check can’t say much about Z, however sure Y is: the message can be no surer than the least sure of the others.

In LLRs, that’s two rules:

The sign of the message is the product of the others’ signs (an even number of 1s among them says 0).
Its size is limited by the least sure of the others.

The exact rule (from the probabilities) is

\tanh\frac{\text{message}}{2} = \tanh\frac{\text{LLR}_X}{2} \times \tanh\frac{\text{LLR}_Y}{2},

and with more bits on the check, every other bit’s $\tanh$ joins the product. ( $\tanh$ squashes any number into the range −1 to +1, and turns an LLR into the bit’s chance of being 0 minus its chance of being 1.)

For example, with X at +4.0 and Y at −2.0: $\tanh(4.0 \div 2)$ = 0.964 and $\tanh(-2.0 \div 2)$ = −0.762. Their product is −0.734, so the message is $2 \times \operatorname{atanh}(-0.734)$ = −1.9, where atanh undoes tanh. The sign is negative because one of X and Y leans towards 1, and the size, 1.9, is a little less than Y’s 2.0: the message is never surer than its least sure input.

Real decoders often use a simpler approximation, min-sum: the sign as above, and the size of the least sure. It’s slightly overconfident, so it’s usually scaled down a little; the decoders below use 0.8.

Top: a check covering bits X, Y and Z, with X’s and Y’s LLRs set by the sliders, and the message the check sends to Z. Bottom: that message against Y’s LLR, with X’s held where it is: the exact rule (solid), and min-sum without scaling (dashed).

With X at +4.0 (surely 0) and Y at −2.0 (probably 1), the check tells Z −1.9: probably 1, a chance of 13.3% of being 0. Min-sum says −2.0. However sure Y gets, the message levels off at X’s size: Z can never be surer than the less sure of X and Y.

5 · Belief propagation

Now put sections 3 and 4 together. Each bit starts with its LLR from the channel. Then, round after round:

Every bit tells each of its checks what it believes.
Every check works out, for each of its bits, what the other bits imply, and sends it back as a message (section 4).
Every bit adds up its channel LLR and all its checks’ messages (section 3: independent evidence adds).

There’s one rule that keeps this honest: a bit never tells a check what that check itself just said. What it sends each check is its total minus that check’s own message. Otherwise a check would hear its own opinion come straight back, louder, as if someone else agreed.

The decoder stops as soon as the bits’ best guesses make every check even. This is belief propagation, or the sum-product algorithm; Judea Pearl developed it in the 1980s for reasoning with uncertainty in general, and it turned out to be exactly what Gallager’s codes needed.

Belief propagation on Hamming (7,4), with the codeword for data 1011 sent through noise of σ = 0.80. Show the working for picks one line (thick in the graph), and the panel below works out its message for the round shown, with the rule from section 4, then adds up the bit’s total. Under each bit, its total LLR; its colour leans green (0) or blue (1), and grows stronger as it gets surer. The numbers on the lines are each check’s message to that bit, in that round. Orange rings mark wrong bits. Each check is green if the bits, decided as they stand, make it even, and red if odd: the decoder stops as soon as all three are green.

With two bits wrong, d3 (arriving at +0.8, doubtfully the wrong way) and p2 (+1.1), hard decisions followed by Hamming decoding get the data wrong: Hamming (7,4) can only fix one error. Belief propagation fixes both in 3 rounds. The checks’ messages overrule d3’s weak reading in the first round, and p2 follows in the third, once d3 is put right. With three bits wrong, the received word happens to be another codeword exactly: after one round every check is even, and the decoder stops, wrong.

6 · Why low density matters

Section 5 rests on one assumption: that the messages arriving at a bit are independent pieces of evidence, so that adding them is right. On a graph with short loops, they aren’t.

Hamming (7,4)‘s graph is full of them. Bits d1 and d4 are both covered by checks A and B, so there’s a loop of four lines: d1, A, d4, B, and back to d1. Whatever d1 says to A reaches d4, comes back to B, and arrives at d1 again two rounds later, disguised as news. The evidence starts counting itself twice.

Top: one of Hamming (7,4)‘s loops of four lines. Bottom: the share of data bits wrong, against $E_b/N_0$ , for Hamming (7,4) decoded three ways, measured on 6,000 blocks per point: the best possible (compare what arrived with all 16 codewords, and pick the nearest), belief propagation, and hard decisions followed by Hamming decoding.

Belief propagation gets close to the best possible, but not all the way: at 4 dB it gets 0.70% of data bits wrong, against 0.53%. Hard decisions get 1.65% wrong.

On a small graph, that’s a small loss. But a code that’s close to Shannon’s limit needs long blocks, and comparing with every codeword stops being possible long before then. Belief propagation’s effort only grows in step with the number of lines in the graph. The trick is to make the loops long.

That’s Gallager’s insight, and the reason for the name low-density parity-check code: a code with thousands of bits, each covered by only a few checks (3, here), and each check covering only a few bits (about 6). With so few lines, they can be placed so that every loop is long. The big code on this page was built line by line, each placed as far as possible from the bit’s other lines (the progressive edge growth method), and its shortest loop has 10 lines. Evidence then takes at least five rounds to come back round, by which time the decoder has usually finished.

Gallager’s codes were mostly forgotten for 30 years: the computers of the 1960s couldn’t decode blocks thousands of bits long. David MacKay and Radford Neal rediscovered them in 1996, by which time computers could.

7 · A real LDPC code

Here’s that big code in action: 2,000 bits per block, 1,000 of them data, so rate ½, with 1,000 checks. Its encoder was worked out from the checks by solving them for the parity bits, the same way the Hamming code’s parity bits are found, on a bigger scale.

Top: one block’s 1,000 data bits as they arrive (hard decisions from the channel) and after decoding; red bits are wrong. Middle: the data bits still wrong after each round. Bottom: the share of data bits wrong against $E_b/N_0$ , measured as the figure loads (60 blocks, 60,000 data bits, per point), with no code, the K = 7 convolutional code from the ECC page, and Shannon’s limit. New block sends different data with different noise.

At 1.5 dB, this block arrives with 110 of its 1,000 data bits wrong, and belief propagation corrects them all in 10 rounds: 81 wrong after the first, 45 after the third, 9 after the seventh. Over 60 blocks at 1.5 dB, 1.30% of data bits stay wrong (1.64% with min-sum). From 1.75 dB up, none of the 60,000 do.

That sudden drop is the waterfall: below some $E_b/N_0$ , belief propagation can’t get started and the code does little; just above it, the errors vanish within a fraction of a decibel. The figure can’t measure far down the waterfall in the time it takes to load, but longer runs can. Measured on 20,000 blocks per point, this code reaches one data bit wrong in 100,000 at 2.21 dB. The ECC page’s K = 7 code needs 4.21 dB for the same, so this simple LDPC code is 2.0 dB better. It’s 2.2 dB from Shannon’s limit for rate ½, or 2.0 dB from the limit when every bit sent is +1 or −1 (0.19 dB).

It’s also the simplest kind of LDPC code: every bit in exactly 3 checks. The codes in Wi-Fi and 5G are irregular, with some bits in many checks and some in few, in proportions found by careful optimisation, and with much longer blocks. In 2001, Sae-Young Chung, David Forney, Thomas Richardson and Rüdiger Urbanke showed an irregular code with 10-million-bit blocks within 0.04 dB of the limit.

8 · Turbo codes: two simple codes that talk

Turbo codes reached the same idea from a different direction, and got there first. In 1993, Claude Berrou, Alain Glavieux and Punya Thitimajshima showed a code within 0.7 dB of the limit, using 65,536-bit blocks. The results seemed too good to be true, and many experts didn’t believe them until they’d reproduced them.

A turbo encoder uses two small convolutional encoders, like the ECC page’s, with two twists:

They’re recursive: the encoder feeds its own output back into its register, so a single 1 at the input makes parity bits that go on and on, rather than dying out after a few steps.
The second encoder sees the data in a scrambled order, rearranged by an interleaver. Data bits that sit next to each other for one encoder are far apart for the other.

A turbo encoder. The data is sent as it is, along with parity bits from two recursive convolutional encoders, the second working on the data in a scrambled order. Here, to make rate ½, the two encoders’ parity bits take turns: encoder 1’s on even positions, encoder 2’s on odd ones.

The decoder has two halves, one for each encoder. Each uses the BCJR algorithm (after Lalit Bahl, John Cocke, Frederick Jelinek and Josef Raviv, 1974), a cousin of Viterbi’s. Viterbi’s algorithm finds the single most likely path through the trellis; BCJR runs through the trellis forwards and backwards, and works out the LLR of every data bit from all the paths together. That’s slower, but it says how sure it is about each bit, which is exactly what the other half needs.

Then the two halves take turns. Decoder 1 works out its LLRs and passes them to decoder 2, which uses them as a head start. Decoder 2 passes its own back, and so on. Each passes on only its extrinsic information: what it worked out from its own parity bits, with what it was given taken away, so that neither hears its own opinion back (the same rule as in belief propagation). The feedback between the two, like a turbocharged engine’s, gave the codes their name.

Top: the turbo code’s data bits wrong after each of its 8 rounds, over 20 blocks at the chosen $E_b/N_0$ . Bottom: the share of data bits wrong against $E_b/N_0$ , measured as the figure loads (40 blocks per point), with the LDPC code from section 7. This turbo code uses 1,000-bit blocks (the same amount of data per block as the LDPC code) and the 8-state component code of 4G phones.

At 1.25 dB, 5.93% of data bits are wrong after the first round, 2.11% after the second, 0.70% after the third, and 0.44% after eight. At 1 dB, 0.55% of the turbo code’s data bits are wrong, against 5.9% for the LDPC code.

Measured on 5,000 blocks per point, this turbo code reaches one data bit wrong in 100,000 at 1.74 dB, about half a decibel better than the LDPC code. The 1993 code did better still, 0.7 dB, with blocks 65 times as long.

9 · Polar codes

Polar codes, invented by Erdal Arıkan in 2009, work differently from the others. They were the first codes proved to reach Shannon’s limit with a decoder that’s fast enough to use, and they carry the control messages in 5G.

The idea starts with two uses of a channel. Instead of sending two bits $u_1$ and $u_2$ as they are, send $x_1 = u_1 \oplus u_2$ and $x_2 = u_2$ ( $\oplus$ is the exclusive or: 1 if the two differ). If both arrive intact, the receiver can undo the mixing: $u_2 = x_2$ , and $u_1 = x_1 \oplus x_2$ .

A polar decoder works through the bits in order: first $u_1$ , then $u_2$ , using what it decided about $u_1$ . So it helps to think of each bit as having its own channel. Not a wire, but the whole path from that bit at the sender to the receiver’s decision about it: the mixing, both transmissions, and the order of decoding. Those two paths turn out to be very different.

The easiest way to see it is on the erasure channel, where each bit either arrives intact or is lost (and the receiver knows which). Say each of $x_1$ and $x_2$ is lost half the time, so four cases are equally likely:

What arrives	Can the receiver find $u_1$ ?	And $u_2$ , once $u_1$ is known?
both	yes: $x_1 \oplus x_2$	yes
only $x_2$	no: it needs $x_1$ too	yes: $x_2$
only $x_1$	no: $x_1$ alone mixes both	yes: $x_1 \oplus u_1$
neither	no	no

$u_1$ is lost 3 times in 4. A bit sent on its own would be lost only 2 times in 4, so $u_1$ ‘s channel is worse.
Once $u_1$ is known, $u_2$ arrives in two independent copies, $x_2$ and $x_1 \oplus u_1$ , and is lost only when both are: 1 time in 4. Its channel is better.

On average, they still lose 2 bits in 4: mixing has created nothing and destroyed nothing. It has only moved reliability from one bit to the other.

That leaves the obvious question: if $u_1$ ‘s channel is the bad one, how can the receiver know $u_1$ , so as to use $u_2$ ‘s two copies? The answer is to put nothing on it. Make $u_1$ a frozen bit: always 0, agreed in advance, so the receiver knows it before anything arrives. Then $x_1 = 0 \oplus u_2 = u_2$ , and $x_2 = u_2$ : the pair is simply $u_2$ sent twice, a repetition code. The data goes on the better channel, and the worse channel’s transmission becomes its backup copy.

Two bits combined, through an erasure channel. Choose what’s sent, whether $u_1$ is frozen, and which of $x_1$ and $x_2$ arrive. The receiver decides $u_1$ first, then $u_2$ , using its decision about $u_1$ . The readouts count, over the four equally likely cases, how often each bit is lost.

With $u_1$ frozen, $u_2$ survives whenever either copy arrives, and is lost 1 time in 4. With $u_1$ not frozen, $u_1$ is lost 3 times in 4, and $u_2$ is lost 2 times in 4, no better than a bit sent on its own: when $x_2$ is lost, the receiver can’t work out $u_1$ , so it can’t use $x_1$ either. The better channel only helps if the bits before it are known.

On a channel that flips bits rather than losing them, freezing $u_1$ still gives $u_2$ two copies. If they’re hard 0s and 1s and they disagree, the receiver can only tell that something went wrong, as with repeating a bit twice. With LLRs, though, the two copies simply add (section 3), so a confident copy outweighs a doubtful one. That’s the decoder’s rule for the better channel. Its rule for the worse one is the check rule of section 4: $u_1 = x_1 \oplus x_2$ is exactly a parity check.

Now do the same again with pairs of pairs, and again, and again. Each round makes the better channels better still, and the worse ones worse. After many rounds, the combined channels polarise: almost all of them end up either almost perfect or almost useless, with very few in between. Freeze the useless ones, and send data on the rest. Each data bit’s decision then leans on everything decided before it: frozen bits, which the receiver knows for certain, and earlier data bits, which on good channels it almost always decides correctly.

On the erasure channel this can all be worked out exactly. If each original use loses its bit with chance $z$ , the worse channel loses it with chance $2z - z^2$ (if either copy is lost), and the better one with chance $z^2$ (only if both are). With $z = ½$ , that’s the 3 in 4 and 1 in 4 above.

Top: the capacity of each combined channel (1 minus its chance of losing the bit), for an erasure channel that loses bits with the chosen chance, after combining the chosen number of channels. Bottom: the same capacities, sorted from worst to best. The dashed line is the original channel’s capacity.

With 64 channels each losing half their bits, 15 become nearly perfect (losing under 1%), 15 nearly useless, and 34 are still in between. With 1,024, it’s 382 nearly perfect, 382 nearly useless, and 260 in between. Their average capacity is always exactly the original channel’s, 0.5 here: polarising moves capacity around, but never creates or destroys it.

The decoder, successive cancellation, decodes the bits in order, each using the decisions before it, just as the two-bit example did. Its calculations are the same two rules as before: combining two values that must add up to a known parity (the check rule of section 4), and adding two independent pieces of evidence (section 3). For blocks of $N$ bits, it takes about $N \log_2 N$ steps.

Successive cancellation has a weakness: a wrong decision early on can’t be taken back, and it leads the decisions after it astray. List decoding (Ido Tal and Alexander Vardy, 2011) fixes that by keeping several candidates. At every data bit, each candidate splits into two (one guessing 0, one guessing 1), and only the most likely ones survive. At the end, a CRC (a checksum, like the modem’s) picks the most likely candidate that passes it. 5G’s polar codes come with a CRC for exactly this, and receivers typically keep a list of 8.

The share of data bits wrong against $E_b/N_0$ , measured as the figure loads (40 blocks per point), for a polar code with 2,048 bits per block: 1,008 data bits and a 16-bit CRC on the 1,024 most reliable channels, and the rest frozen. It’s decoded by successive cancellation, and by list decoding with a list of 8 and the CRC. The LDPC code from section 7 is shown for comparison.

At 1.5 dB, successive cancellation gets 7.43% of data bits wrong. List decoding gets none of 40,320 wrong, and the LDPC code 1.03%.

Measured on 20,000 blocks per point, successive cancellation reaches one data bit wrong in 100,000 at 3.26 dB. List decoding gets far fewer blocks wrong than the LDPC code at the same $E_b/N_0$ (at 2 dB, 10 of 30,000, against the LDPC code’s 33 of 20,000), but when it does fail, it fails badly: about 100 of the block’s 1,008 data bits wrong, against about 48 for the LDPC code. So its error rate per bit falls a little more slowly than its block failures suggest. It reaches one data bit wrong in 100,000 at about 2.0 to 2.1 dB (at 2.1 dB, just one block in 30,000 failed), a little better than the LDPC code.

10 · Back to the modem

The acoustic modem can use an LDPC code too. Its OFDM with an LDPC code option uses the same carriers and the same rate (½) as the coded OFDM of the ECC page, with an LDPC code of 1,152 bits in place of the K = 7 convolutional code, decoded by belief propagation. Its chirp falls and then rises.

Belief propagation needs proper LLRs, not just soft values. Viterbi’s algorithm only compares paths, so it doesn’t mind if every soft value is scaled up or down; belief propagation adds evidence from the channel to evidence from the checks, so the channel’s must be on the right scale. The receiver estimates the noise from the two training symbols (both are known, so whatever differs between them is noise), and scales each carrier’s values by how strongly that carrier arrived.

The same message, sent with the K = 7 code and with the LDPC code, 24 times at each noise level, through either the direct sound alone (no echoes) or the made-up echoey room. The bars count messages whose checksum matched. Measured as the figure loads.

With the direct sound alone, both codes deliver every message down to −5 dB. At −6 dB, the K = 7 code delivers 22 of the 24, and the LDPC code all 24; at −7 dB, 6 against 11. In the echoey room, at −4 dB, 21 against 23, and at −5 dB, 8 against 11; at −6 dB, both deliver just 1.

The LDPC code holds on about half a decibel longer, much less than the 2 dB it gains in section 7. Two things probably narrow the gap. These blocks are 1,152 bits, half as long as section 7’s, and short blocks are where convolutional codes are at their best. And at these noise levels, the receiver’s measurements of the room, from two training symbols, are themselves noisy, which costs both codes alike.

You can try it through your own loudspeaker on the digital modulation page: it’s the last option in the modem’s menu.

11 · Where they’re used, and the error floor

These codes are everywhere now:

LDPC codes: Wi-Fi (from 802.11n), 5G’s data channels, digital satellite television (DVB-S2), 10-gigabit Ethernet over copper, and the error correction inside SSDs.
Turbo codes: 3G and 4G phones, and deep-space missions.
Polar codes: 5G’s control channels.

Each has its strengths. Turbo codes shine at moderate block lengths. LDPC decoders are naturally parallel, since every check and every bit can work at once, which suits very high data rates. Polar codes have the neatest theory, and with list decoding they’re excellent for the short messages of a control channel.

All iterative decoders share one weakness, the error floor. Below the waterfall, the errors usually keep falling as $E_b/N_0$ rises. But some codes have a few small, unlucky structures (a handful of codewords that are unusually close together, or a small knot in the graph that belief propagation can’t untangle), and these cause rare failures that hardly improve with more signal.

The turbo code here shows one. Its blocks with errors fell from 0.84% at 1.5 dB to 0.14% at 1.75 dB, the waterfall. But at 2 dB, 3 of 5,000 blocks still failed, and at 2.25 dB, 4 of 5,000: the error rate flattened out at about one data bit in a million. The LDPC code, with its long loops, showed no floor down to the lowest error rates measured here: at 2.3 and 2.4 dB, none of its 20,000 blocks failed. Real systems handle floors by designing codes carefully, and often by adding a small outer code, as DVB-S2 does, to clean up the rare failures.

Summary

A code’s parity checks can be drawn as a Tanner graph: bits on one side, checks on the other.
Bit flipping decodes on the graph with hard decisions: each odd check blames its bits, and the most blamed flip. It works, but far from the limit.
The log-likelihood ratio puts how sure a bit is into one number, and independent evidence simply adds.
A check tells each bit what its other bits imply: the sign of their product, no surer than the least sure of them.
Belief propagation passes these messages back and forth, never letting a bit’s own opinion come straight back to it.
Short loops make the evidence count itself twice; low-density graphs with long loops avoid that, and let belief propagation work on blocks thousands of bits long.
A simple LDPC code with 2,000-bit blocks comes within 2.0 dB of Shannon’s limit; the K = 7 code is 4 dB away.
Turbo codes get there with two recursive convolutional codes, an interleaver, and two BCJR decoders passing extrinsic information.
Polar codes split channels into nearly perfect and nearly useless ones, send data on the good ones, and decode them one by one; list decoding with a CRC makes them competitive.
In the acoustic modem, an LDPC code holds on about half a decibel longer than the K = 7 code.