Turbo Codes and LDPC Codes — Mathematics Knowledge System

Overview

Turbo codes (1993) and Low-Density Parity-Check (LDPC) codes (1963, rediscovered 1996) are two families of modern error-correcting codes that achieve performance very close to the Shannon limit — the theoretical maximum rate of reliable communication over a noisy channel. Both use iterative decoding: rather than making a single hard decision, decoders exchange 'soft' probabilistic beliefs between component codes or variable/check nodes repeatedly until convergence. Turbo codes are used in 3G/4G cellular networks; LDPC codes are used in 5G, Wi-Fi (802.11n/ac/ax), DVB-S2 satellite television, and 10-Gigabit Ethernet.

Intuition

Imagine two people working a jigsaw puzzle together, each seeing different clues. They take turns sharing 'hints' (soft probabilities) based on what they've learned, updating their beliefs each round. After many rounds, they reliably complete the puzzle. This is the intuition behind iterative decoding: two (or many) component decoders exchange probability information about each bit, each becoming more confident in each iteration. The 'turbo' name (from turbocharger) reflects how the component decoders boost each other's performance. LDPC codes are decoded by 'belief propagation' on a bipartite factor graph.

Formal Definition

Definition

A turbo code concatenates two convolutional codes C₁, C₂ via an interleaver π. LDPC codes are defined by a sparse parity-check matrix H with low density of 1s. Belief propagation on the Tanner graph iterates between variable nodes and check nodes:

\text{Turbo encoder: } \mathbf{c} = (\mathbf{m},\ \mathbf{p}_1,\ \mathbf{p}_2) \text{ where } \mathbf{p}_i = C_i(\pi_i(\mathbf{m}))

Turbo code structure (systematic + 2 parity streams)

\mu_{v \to c}^{(t)}(x) \propto p(y_v|x) \prod_{c' \neq c} \mu_{c' \to v}^{(t-1)}(x)

Belief propagation: variable-to-check message

\mu_{c \to v}^{(t)}(x) \propto \sum_{\mathbf{x}_{\partial c \setminus v}: \text{constraint}} \prod_{v' \in \partial c \setminus v} \mu_{v' \to c}^{(t)}(x_{v'})

Belief propagation: check-to-variable message

\lim_{n\to\infty} R^* = C = \max_{p(x)} I(X;Y) \text{ (LDPC/Turbo codes approach this as } n \to \infty)

Near-capacity performance

Notation

Notation	Meaning
$H$	Parity-check matrix (sparse for LDPC)
$\pi$	Interleaver permutation (turbo codes)
$\mathrm{LLR}$	Log-likelihood ratio: the soft reliability measure
$\mu_{v \to c}$	Message from variable node v to check node c in belief propagation

Theorems

Theorem 1: Capacity-Approaching Performance of LDPC Codes

For a binary-input memoryless symmetric channel, there exist sequences of LDPC codes with rate R approaching the channel capacity C = I(X;Y) such that the block error probability under belief propagation decoding tends to 0 as the block length n \to \infty.

Theorem 2: Density Evolution (DE) for LDPC Codes

For cycle-free Tanner graphs (tree assumption), the distribution of messages in belief propagation can be tracked exactly via density evolution. A code is asymptotically good iff the density evolution fixed point is the zero-error state.

Theorem 3: Turbo Code Interleaver Gain

For turbo codes with block length N and a random interleaver, the minimum distance d_{\min} grows as \Omega(\sqrt{N}), enabling decreasing error rates at any R < C as N \to \infty.

Worked Examples

1
Initialize: each variable node v sends to each check node c the channel LLR: L_v = log(P(y_v|x_v=0)/P(y_v|x_v=1)).
$L_v^{(0)} = \log\frac{1-p}{p} \cdot (1 - 2y_v)$
2
Check-to-variable update: for each check node c connected to variables V_c, the message to variable v is the 'parity check soft information' from all other variables.
$L_{c\to v}^{(t)} = 2\,\mathrm{arctanh}\!\left(\prod_{v' \in V_c \setminus v} \tanh\frac{L_{v'\to c}^{(t)}}{2}\right)$
3
Variable-to-check update: each variable v aggregates channel LLR plus all incoming check messages except from c.
$L_{v \to c}^{(t+1)} = L_v^{(0)} + \sum_{c' \in C_v \setminus c} L_{c' \to v}^{(t)}$
4
Posterior: variable v's posterior LLR after T iterations: bit decoded to 0 if positive, 1 if negative.
$L_v^{\text{post}} = L_v^{(0)} + \sum_{c \in C_v} L_{c \to v}^{(T)}$

✓ Answer

Belief propagation iteratively refines soft-bit estimates. On graphs with long cycles (long codes), it approximates optimal maximum a posteriori decoding.

Practice Problems

Mediumfree response

What is the key difference between hard-decision decoding and soft-decision (belief propagation) decoding?

Hardapplication

Why do turbo and LDPC codes work best for long block lengths, and what is the 'error floor' phenomenon?

Common Mistakes

Common Mistake

Thinking turbo/LDPC codes achieve zero error at rates up to capacity.

They achieve very low (but not zero) error probability for finite block lengths. The Shannon limit says error → 0 as n → ∞. At finite n, there is always a nonzero gap.

Common Mistake

Confusing the Tanner graph (for LDPC) with the trellis diagram (for convolutional codes).

The Tanner graph is a bipartite graph with variable nodes (bits) and check nodes (parity checks) connected by edges. The trellis represents the state transitions of a convolutional encoder. Belief propagation runs on the Tanner graph; Viterbi/BCJR algorithms run on the trellis.

Quiz

Historical Background

Robert Gallager introduced LDPC codes in his 1963 MIT doctoral thesis, but limited computing power meant they were ignored for 30 years. In 1993, Claude Berrou, Alain Glavieux, and Punya Thitimajshima presented turbo codes at the ICC conference, demonstrating performance within 0.5 dB of the Shannon limit for a rate-1/2 code — a result that stunned the coding community. This reignited interest in LDPC codes, which were rediscovered and analyzed by MacKay and Neal (1996) using modern belief propagation. Both code families rely on the insight that iterative decoding over a graphical model can approach capacity.

1963
Gallager introduces LDPC codes in his doctoral thesis at MIT.
Robert Gallager
1993
Berrou, Glavieux, and Thitimajshima present turbo codes, operating within 0.5 dB of Shannon limit.
Claude Berrou, Alain Glavieux, Punya Thitimajshima
1996
MacKay and Neal rediscover LDPC codes, showing they also approach capacity.
David MacKay, Radford Neal
2001
Turbo codes adopted in 3G (UMTS/CDMA2000) mobile communications standards.
2017
LDPC codes selected for 5G NR (New Radio) data channels; polar codes for control channels.

Summary

Turbo codes (1993) and LDPC codes (1963/1996) are capacity-approaching codes using iterative soft decoding, operating within fractions of a dB from Shannon's limit.
Both use graphical structure: turbo codes use an interleaver between two convolutional codes; LDPC codes use sparse parity-check matrices defining a Tanner graph.
Belief propagation (sum-product algorithm) iteratively passes log-likelihood ratios between variable nodes and check nodes until convergence.
LDPC codes are used in 5G, Wi-Fi, and satellite TV (DVB-S2); turbo codes powered 3G/4G cellular networks.

References

PaperBerrou, C., Glavieux, A., Thitimajshima, P. (1993). Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-codes. ICC 1993.
PaperMacKay, D.J.C. and Neal, R.M. (1996). Near Shannon Limit Performance of Low Density Parity Check Codes. Electronics Letters, 32(18).
BookMacKay, D.J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. Ch. 47-50.
WebsiteWikipedia — Turbo code