LDPC and Turbo Codes — The Error Correction Behind 5G and Deep Space

Shannon proved in 1948 that these codes exist, and nobody could build one for 45 years. Starting from zero background, this article unpacks the three ideas — soft decisions, log-likelihood ratios, and belief propagation — that finally reached the theoretical limit, and shows what actually runs in 5G NR and deep-space links.

A promise left hanging for 45 years

In 1948 Claude Shannon proved that every channel has a capacity, and that as long as you send slower than that, codes exist which push the error rate as close to zero as you like.

$$C = B\log_2\!\left(1 + \frac{S}{N}\right)$$

$C$ is the bits per second you can carry, $B$ is the bandwidth, and $S/N$ is the ratio of signal power to noise power. In plain terms: fix the bandwidth and the signal strength, and the ceiling on information flow is fixed too. The derivation lives in Information Theory for AI.

The trouble was how he proved it. Shannon showed that the average member of a family of random codes is good — he never said how to build one. Worse, decoding a random code means comparing the received signal against all $2^k$ candidates, where $k$ is the number of information bits. So engineers attacked from the opposite side: impose algebraic structure, the way the Hamming and Reed–Solomon codes in Error Correction from Scratch do, and decoding becomes cheap. Those codes could be decoded, but they sat several dB short of capacity, and that gap refused to close for 45 years.

Then in 1993 Berrou, Glavieux and Thitimajshima announced "turbo codes": rate 1/2, bit error rate below $10^{-5}$ at $E_b/N_0 = 0.7$ dB. The claim was hard to believe, and it replicated. In 1996 MacKay and Neal showed an equally strong family that was not even new — Robert Gallager's LDPC codes (low-density parity-check codes) from 1962, forgotten because no machine of that era could run the decoder.

Hard decisions throw away information

What arrives at the antenna is not a 0 or a 1 — it is a voltage. Put the threshold at 0.5 V, and 0.51 V becomes "1". At that moment the fact that it was barely a 1 is discarded. To the next stage, 0.51 V and 0.99 V are the same symbol, yet the first one was a hair's breadth from flipping.

Replacing hard decisions with soft ones — passing along how 0-ish the sample was instead of rounding it — is where both turbo and LDPC decoding begin. Soft decisions are generally worth roughly 2 dB over hard decisions. A good share of that 45-year stall was sitting in the information everyone was throwing away.

Turning confidence into a single number

There are only two things to read here: the sign says which way it leans, the magnitude says how sure we are. A large positive value means "almost certainly 0", a small negative value means "probably 1, but don't bet on it", and zero means a coin flip. $y_i$ is the received sample for bit $i$ and $x_i$ is the bit that was actually transmitted. This quantity is the log-likelihood ratio, or LLR.

On an additive white Gaussian noise channel with BPSK (sending 0 and 1 as $+1$ and $-1$), equation (1) collapses to something startlingly simple:

$$L_i = \frac{2 y_i}{\sigma^2}$$

$\sigma^2$ is the noise variance. You divide the received voltage by how noisy the channel is — a formal way of saying that in a noisy room, the same volume of speech should convince you less.

The reason we take the log of a ratio rather than a probability is worth pausing on. Independent pieces of evidence combine by multiplication, and taking a logarithm turns multiplication into addition. So with LLRs, evidence arriving from different places can be merged by adding it up. It is the same move as the posterior update in Bayes for AI.

Why "just try everything" is not an option

If you picked whichever valid codeword best matched the LLRs, you would be optimal — that is maximum-likelihood decoding. But there are $2^k$ candidates. The 5G NR LDPC code carries up to 8448 information bits (base graph 1 in 3GPP TS 38.212), so $2^{8448}$ options: a machine testing a trillion per second, running for the age of the universe, would not scratch it.

What we need is a way to get each bit's "0-ness" without enumerating any candidates at all. Turbo and LDPC codes look nothing alike, and both do exactly that.

LDPC — make the parity checks sparse

The name is the blueprint. Build a parity-check matrix $H$ and require every transmitted word $\mathbf{c}$ to satisfy:

$$H\mathbf{c}^\top = \mathbf{0} \pmod 2$$

Each row of $H$ is one parity equation, and the XOR of the bits it touches must be zero. So far this is any linear code. What makes LDPC special is one thing only: $H$ is mostly empty. A row may span thousands of bits while containing somewhere between a handful and twenty ones.

You can redraw $H$ as a picture. Put a variable node for each bit, a check node for each parity equation, and draw an edge when the bit participates in the equation. That is a Tanner graph. Sparsity matters for two reasons: decoding cost is proportional to the number of edges, and fewer edges make short cycles — short loops that return to the same node — rarer. Cycles are what fool the algorithm.