LDPC Codes, Belief Propagation, and Tanner Graphs

Overview

Low-Density Parity-Check (LDPC) codes are a class of linear block codes defined by a sparse parity-check matrix H. Introduced by Gallager in 1963 and rediscovered by MacKay and Neal in 1996, they achieve near-Shannon-limit performance on a wide variety of channels. Decoding uses belief propagation (sum-product algorithm) on the Tanner graph — a bipartite factor graph with variable nodes (bits) and check nodes (parity constraints). LDPC codes are used in 5G NR data channels, Wi-Fi (802.11n/ac/ax), DVB-S2 satellite television, and 10 Gigabit Ethernet.

Intuition

An LDPC code is defined by a sparse parity-check matrix H where most entries are 0. Think of H as a set of parity constraints on the codeword bits. The Tanner graph makes these constraints visual: variable nodes (one per bit) on the left, check nodes (one per parity equation) on the right, connected by edges where H has a 1. Belief propagation decodes by passing probability messages along edges: variable nodes aggregate channel evidence and incoming check messages; check nodes aggregate parity constraint information from neighboring variable nodes. After many rounds, the messages converge to reliable bit estimates.

Formal Definition

Definition

A (N, K) LDPC code is defined by an M x N sparse parity-check matrix H over GF(2). The Tanner graph G = (V union C, E) has variable nodes V = {v_1,...,v_N}, check nodes C = {c_1,...,c_M}, and edge (v_i, c_j) iff H_{ji} = 1. The sum-product algorithm computes:

H \mathbf{x} = \mathbf{0} \pmod{2}

LDPC parity-check condition

L_{c \to v}^{(t)} = 2\,\mathrm{arctanh}\!\left(\prod_{v' \in \partial c \setminus v} \tanh\frac{L_{v' \to c}^{(t)}}{2}\right)

Check-to-variable LLR message (sum-product)

L_{v \to c}^{(t+1)} = L_v^{\mathrm{ch}} + \sum_{c' \in \partial v \setminus c} L_{c' \to v}^{(t)}

Variable-to-check LLR message

\hat{x}_v = \mathbb{1}\!\left[L_v^{\mathrm{ch}} + \sum_{c \in \partial v} L_{c \to v}^{(T)} < 0\right]

Hard decision after T iterations

Notation

Notation	Meaning
$H$	Sparse M x N parity-check matrix over GF(2)
$d_v,\; d_c$	Variable node degree and check node degree
$L_v^{\mathrm{ch}}$	Channel log-likelihood ratio for variable v
$\lambda(x),\; \rho(x)$	Variable/check node degree distribution polynomials

Theorems

Theorem 1: Density Evolution Convergence

For LDPC codes on a binary memoryless symmetric channel, in the limit of large block length and girth, the distribution of messages in belief propagation converges to a fixed point. The threshold capacity delta* is the largest channel noise parameter for which this fixed point is the zero-error state.

Theorem 2: Capacity-Approaching LDPC Codes

For any binary memoryless symmetric channel with capacity C and any epsilon > 0, there exist sequences of LDPC code ensembles with rate R > C -- epsilon whose bit error probability under belief propagation decoding tends to 0 as block length N -> infinity.

Theorem 3: Error Floor Phenomenon

At high SNR, LDPC decoding error probability levels off to an 'error floor' caused by small trapping sets -- subgraphs on which the belief propagation decoder fails to converge. The floor can be lowered by careful Tanner graph design.

Worked Examples

1
A check node c connected to variable nodes v1, v2, v3. We compute the message from c to v1.
$L_{c \to v_1}$
2
Gather incoming LLRs from the other variables: L_{v2->c} and L_{v3->c}.
$L_{v_2 \to c} = 2.1,\quad L_{v_3 \to c} = -0.8$
3
Apply the check-to-variable formula using the tanh product rule.
$L_{c \to v_1} = 2\,\mathrm{arctanh}\!\left(\tanh\frac{2.1}{2} \cdot \tanh\frac{-0.8}{2}\right)$
4
Compute: tanh(1.05) approx 0.781, tanh(-0.4) approx -0.380. Product = -0.297.
$L_{c \to v_1} = 2\,\mathrm{arctanh}(-0.297) \approx -0.608$

✓ Answer

The check-to-variable message is approximately -0.608, indicating the parity constraint pushes v1 slightly toward 1.

Practice Problems

Mediumfree response

What is a Tanner graph and how does it represent an LDPC code?

Hardapplication

Explain what an 'error floor' is in LDPC decoding and how it arises.

Common Mistakes

Common Mistake

LDPC codes were a recent invention from the 1990s.

LDPC codes were invented by Robert Gallager in his 1963 MIT doctoral thesis, predating turbo codes by 30 years. They were independently rediscovered by MacKay and Neal in 1996.

Common Mistake

Belief propagation on LDPC gives exact MAP decoding.

Belief propagation is exact only on cycle-free (tree) graphs. Real Tanner graphs have cycles, so BP is an approximation. However, for long codes with large girth, BP closely approximates MAP decoding.

Quiz

The 'low density' in LDPC codes refers to:

Low information rateSparsity of the parity-check matrix HFew iterations of belief propagationSmall block length

Belief propagation on the Tanner graph decodes LDPC codes by:

Computing the syndrome and looking up a correction tableIteratively exchanging log-likelihood ratios between variable and check nodesUsing a Viterbi algorithm on a trellisApplying Gaussian elimination to the received word

Historical Background

Robert Gallager introduced LDPC codes in his 1963 MIT doctoral thesis under Robert Fano. The computational demands of belief propagation decoding made them impractical on the hardware of the time, and they were largely forgotten. In 1996, David MacKay and Radford Neal independently rediscovered them and showed, using modern probabilistic inference techniques, that LDPC codes rival turbo codes in performance. Their rediscovery coincided with the turbo codes revolution, and the two families have since been the dominant practical near-capacity codes.

1963
Gallager introduces LDPC codes in his MIT doctoral thesis.
Robert Gallager
1996
MacKay and Neal rediscover LDPC codes and demonstrate near-capacity performance.
David MacKay, Radford Neal
2001
Richardson and Urbanke develop density evolution for rigorous LDPC code design.
Tom Richardson, Ruediger Urbanke
2003
DVB-S2 satellite standard adopts LDPC codes.
2009
IEEE 802.11n Wi-Fi standard adopts LDPC codes.
2017
3GPP selects LDPC for 5G NR data channels.

Summary

LDPC codes are linear block codes defined by a sparse parity-check matrix H, introduced by Gallager (1963) and rediscovered by MacKay and Neal (1996).
The Tanner graph is a bipartite factor graph with variable nodes (bits) and check nodes (parity constraints); edges correspond to 1s in H.
Belief propagation (sum-product algorithm) iteratively passes LLR messages between variable and check nodes, achieving near-Shannon-limit performance.
LDPC codes are used in 5G NR data channels, Wi-Fi, DVB-S2 satellite TV; they exhibit an error floor at high SNR due to trapping sets.

References

PaperGallager, R.G. (1963). Low-Density Parity-Check Codes. MIT Press (doctoral thesis).
PaperMacKay, D.J.C., Neal, R.M. (1996). Near Shannon Limit Performance of Low Density Parity Check Codes. Electronics Letters, 32(18), 1645-1646.
BookMacKay, D.J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press.
WebsiteWikipedia — Low-density parity-check code