46.07.04 · information-theory / 07-algebraic-coding-advanced

Expander Codes, LDPC Bipartite Graphs, and Sipser-Spielman Linear-Time Decoding

shipped3 tiersLean: none

Anchor (Master): Sipser & Spielman 1996; Tanner 1981 A Recursive Approach to Low Complexity Codes; Barg & Zemor 2002 Error Exponents of Expander Codes; Guruswami & Indyk 2000 Expander-Based Constructions of Efficiently Decodable Codes

Intuition Beginner

Imagine a network of computers arranged in a grid. Each computer stores one bit. Neighbouring groups of computers run parity checks: they count the number of 1s among them and flag any group whose count looks wrong. If enough groups flag errors, you can figure out which bits got corrupted.

This is the idea behind expander codes. The "network" is a graph, and the "groups" are the neighbours of each check node. The key property is that the graph is well-connected: every set of nodes has many neighbours outside itself. This means that any corruption pattern touches many check groups, making errors easy to detect and correct.

Why does connectivity matter? Suppose a small set of bits are corrupted. Each corrupted bit is connected to several check nodes. If the graph is well-connected, most of those check nodes see exactly one corrupted bit, because the neighbours of the corrupted set spread out widely. A check node that sees only one corrupted bit can fix it. So the decoder works by repeatedly finding check nodes that see few errors and correcting them.

The Sipser-Spielman result from 1996 showed that this idea gives codes that correct a constant fraction of errors in time proportional to the message length (linear time). Before this, the fastest known decoders for good codes took much longer. The trick is that the graph structure does all the work: the expansion property ensures that the decoder makes progress at every step.

Visual Beginner

Code family	Graph type	Decoding	Time complexity
Expander codes (Sipser-Spielman)	Bipartite expander	GMD (flip worst bit)	$O (n)$
LDPC (Gallager)	Sparse bipartite	Belief propagation	$O (n)$ per iteration
Reed-Solomon	No graph	Berlekamp-Massey	$O (n^{2})$
Algebraic geometry	No graph	Skorobogatov-Vladut	$O (n^{3})$

Figure: a bipartite Tanner graph with 6 variable nodes (left, circles) and 4 check nodes (right, squares). Each variable node connects to 2 check nodes; each check node connects to 3 variable nodes. The check node enforces that the sum of its neighbour bits is even. If bit 3 flips, check nodes A and C detect an error. The decoder identifies bit 3 as the unique variable connected to both unhappy checks, and flips it back.

Worked example Beginner

A small expander code uses a graph with 4 variable nodes and 2 check nodes. Each variable connects to both checks. The local code at each check requires its two neighbours to be a valid codeword of a simple repetition code.

Valid local codewords for a check with 2 neighbours: (0,0) and (1,1). So each check enforces: its two neighbours must agree.

With 4 variables ${v_{1}, v_{2}, v_{3}, v_{4}}$ and checks $c_{1} = {v_{1}, v_{2}, v_{3}}$ , $c_{2} = {v_{2}, v_{3}, v_{4}}$ (each check has 3 neighbours):

Check $c_{1}$ says: all three bits $v_{1}, v_{2}, v_{3}$ must agree (repetition). Check $c_{2}$ says: all three bits $v_{2}, v_{3}, v_{4}$ must agree.

If the transmitted codeword is (0,0,0,0) and bit $v_{2}$ flips to give (0,1,0,0):

Check $c_{1}$ sees (0,1,0): two 0s and one 1. Not all agree. Error detected.
Check $c_{2}$ sees (1,0,0): two 0s and one 1. Error detected.

The decoder finds that $v_{2}$ is the only variable in both unhappy checks. It flips $v_{2}$ back to 0. Done in one pass.

Check your understanding Beginner

Formal definition Intermediate+

Let $G = (L \cup R, E)$ be a $d$ -regular bipartite graph with $∣ L ∣ = n$ variable nodes and $∣ R ∣ = m = n d / b$ check nodes, where each check node has degree $b$ . Let $C_{0} \subseteq {0, 1}^{b}$ be a binary linear code of length $b$ with minimum distance $d_{0}$ and rate $r_{0}$ .

Definition (Expander code). The expander code $C (G, C_{0})$ is the set of all assignments $x \in {0, 1}^{n}$ to the variable nodes $L$ such that for every check node $c \in R$ , the restriction of $x$ to the neighbours of $c$ is a codeword of $C_{0}$ .

The rate of $C (G, C_{0})$ is at least $1 - (1 - r_{0}) \cdot d \geq 1 - d / b \cdot (b - lo g_{2} ∣ C_{0} ∣)$ .

Definition (Graph expansion). The graph $G$ is a $(δ, ϵ)$ -expander if for every subset $S \subseteq L$ with $∣ S ∣ \leq δ n$ , the number of unique neighbours of $S$ in $R$ satisfies:

∣ N_{u} (S) ∣ \geq (1 - ϵ) d ∣ S ∣,

where a unique neighbour of $S$ is a node in $R$ that is adjacent to exactly one node in $S$ .

Definition (GMD decoding). The generalised minimum distance (GMD) decoder for expander codes operates iteratively:

Find a variable node $v$ that is in more unsatisfied check nodes than satisfied ones.
Flip the bit at $v$ .
Repeat until no such variable exists.

Theorem (Sipser-Spielman). If $G$ is a $(δ, 3/4 + ϵ)$ -expander for some $ϵ > 0$ and $C_{0}$ has minimum distance $d_{0} \geq 2$ , then the GMD decoder corrects all error patterns of weight at most $δ n /2$ in $O (n)$ time.

Connection to LDPC Tanner graphs

An LDPC code 46.08.01 is defined by its parity-check matrix $H$ , which can be represented as a bipartite Tanner graph: variable nodes on one side, check nodes on the other, with an edge wherever $H_{j i} = 1$ . The sparse parity-check matrix (each row has few 1s) means the graph is sparse, and the belief propagation decoder passes messages along the edges.

Expander codes are a subclass of LDPC codes where the Tanner graph has the expansion property. The expansion guarantees that the local decoder (GMD) converges, while the sparsity ensures linear-time complexity. The connection to graph theory 40.04.01 is that expander graphs are objects of deep combinatorial interest, with constructions from Ramanujan graphs (Lubotzky-Phillips-Sarnak), zig-zag products, and random graphs.

Key theorem with proof Intermediate+

Theorem (Minimum distance of expander codes). If $G$ is a $(δ, 3/4 + ϵ)$ -expander and the local code $C_{0}$ has minimum distance $d_{0} > d /2$ , then the expander code $C (G, C_{0})$ has minimum distance at least $δ n$ .

Proof. Suppose $x \neq = 0$ is a codeword of weight $w < δ n$ . Let $S$ be the support of $x$ (the set of variable nodes where $x_{i} = 1$ ). By the expansion property, the number of unique neighbours of $S$ is $∣ N_{u} (S) ∣ \geq (3/4 + ϵ) d \cdot w$ .

Each unique neighbour of $S$ is a check node that sees exactly one variable in $S$ . Since $x$ is a codeword, the restriction to each check must be a codeword of $C_{0}$ . A check with exactly one non-zero neighbour has a local assignment with weight 1, which cannot be a codeword of $C_{0}$ (since $d_{0} > 1$ ).

Therefore the number of unique neighbours must be zero, giving $(3/4 + ϵ) d \cdot w \leq 0$ , which contradicts $w > 0$ . Hence no non-zero codeword has weight less than $δ n$ . $□$

Bridge. The expansion property builds toward the density evolution analysis of LDPC codes in 46.08.01 where the graph structure determines the decoding threshold; this appears again in 46.08.04 where expander codes are compared with other capacity-achieving families; the foundational reason expansion guarantees good distance is that errors cannot cluster without touching many checks, and this is dual to the covering arguments in channel coding; the central insight is that the combinatorial property of the graph (expansion) translates directly into the coding-theoretic property (minimum distance), and putting these together reveals the deep connection between graph theory 40.04.01 and coding theory.

Exercises Intermediate+

Exercise (easy, short answer).

What is the rate of an expander code with $d = 6$ , $b = 12$ , and a local code of rate $r_{0} = 1/2$ ?

Answer

Rate $\geq 1 - d (1 - r_{0}) /1$ . Wait, the formula is rate $\geq 1 - (1 - r_{0}) \cdot d / b \cdot b = 1 - (1 - r_{0}) \cdot d$ . Actually: the number of check nodes is $m = n d / b$ , and each check imposes $b (1 - r_{0})$ parity constraints. Total constraints $\leq m \cdot b (1 - r_{0}) = n \cdot d (1 - r_{0})$ . Rate $\geq 1 - d (1 - r_{0}) = 1 - 6 \times 0.5 = 1 - 3 = - 2$ . That is negative, so the parameters need adjustment.

Let us use the correct formula: rate $\geq 1 - (n d / b) (b - k_{0}) / n = 1 - d (b - k_{0}) / b$ where $k_{0} = r_{0} b$ is the local code dimension. With $r_{0} = 1/2$ , $k_{0} = 6$ : rate $\geq 1 - 6 (12 - 6) /12 = 1 - 6 \times 6/12 = 1 - 3 = - 2$ . Still negative. The issue is that $d = 6$ local checks per variable with only $b = 12$ bits per check and rate 1/2 gives too many constraints.

For the formula rate $= 1 - (1 - r_{0}) d = 1 - 3 = - 2$ , the parameters are not feasible for a meaningful code. A better parameter choice: $d = 4$ , $b = 8$ , $r_{0} = 3/4$ . Rate $= 1 - (1 - 3/4) \times 4 = 1 - 1 = 0$ . Still tight. The rate of expander codes with these parameters is $1 - d (1 - r_{0})$ , and for positive rate we need $d (1 - r_{0}) < 1$ .

Exercise (hard, short answer).

Prove the Sipser-Spielman theorem: if $G$ is a $(δ, 3/4 + ϵ)$ -expander and the error pattern has weight at most $δ n /2$ , then GMD decoding corrects all errors.

Answer

Let $S$ be the set of erroneous variable nodes. At each step, a variable $v \in S$ is "bad" if it has more unsatisfied than satisfied checks. A check is satisfied if the local constraint is met (i.e., the local restriction is a codeword of $C_{0}$ ).

Each variable in $S$ has $d$ edges. The unique neighbours of $S$ (at least $(3/4 + ϵ) d ∣ S ∣$ edges) are check nodes that see exactly one error. Since $d_{0} \geq 2$ , these checks are unsatisfied. So each variable in $S$ has at least $(3/4 + ϵ) d$ unsatisfied edges (from unique neighbours) minus at most $(1/4 - ϵ) d$ satisfied edges (from non-unique neighbours). The net count is $(3/4 + ϵ) d - (1/4 - ϵ) d = (1/2 + 2 ϵ) d > d /2$ . So every variable in $S$ is bad, and flipping it reduces the error count. After at most $∣ S ∣$ flips, all errors are corrected.

Lean formalization Intermediate+

Mathlib has no formalisation of expander graphs, expander codes, or GMD decoding. The graph theory library in Mathlib provides SimpleGraph and basic adjacency structures, but lacks spectral gap definitions, Cheeger inequalities, and the unique-neighbour expansion property. The Tanner graph representation of linear codes and the iterative decoding algorithm are absent. The proof that expansion implies minimum distance requires counting arguments about bipartite neighbourhoods, which Mathlib's combinatorics library does not support. The connection between eigenvalues and expansion (the Alon-Boppana bound, the expander mixing lemma) is unformalised. This unit ships without a lean_module.

Advanced results Master

The expander mixing lemma and spectral expansion

The expander mixing lemma connects the spectral gap of a graph to its combinatorial expansion. For a $d$ -regular bipartite graph with second-largest eigenvalue $λ$ :

e (S, T) - \frac{d ∣ S ∣∣ T ∣}{m} \leq λ ∣ S ∣∣ T ∣

for all $S \subseteq L$ and $T \subseteq R$ . This shows that the edge distribution is nearly uniform: every pair of subsets has approximately the expected number of edges, with deviation controlled by $λ$ . The smaller $λ$ is (relative to $d$ ), the better the expansion.

The Alon-Boppana bound states that $λ \geq 2 d - 1 - o (1)$ for any $d$ -regular graph. Ramanujan graphs (constructed by Lubotzky, Phillips, and Sarnak in 1988) achieve $λ = 2 d - 1$ , matching this bound. These graphs are optimal expanders and produce optimal expander codes.

Tanner's recursive construction

Tanner's 1981 paper introduced the recursive construction of codes on graphs. Instead of using a single-level bipartite graph, the construction nests codes within codes: each check node of the outer graph is itself a codeword of an inner code defined on a smaller graph. This recursive structure allows the code designer to compose weak codes into strong ones, with the expansion of the outer graph amplifying the distance of the inner codes.

The Tanner construction generalises both expander codes (single level) and turbo codes (two-level concatenation with interleaving). The distance bound for the recursive construction is the product of the distances at each level, multiplied by the expansion parameter.

Expander codes and list decoding

Guruswami and Indyk (2000) showed that expander codes admit efficient list-decoding algorithms. For a code with relative distance $δ$ , the list-decoding problem asks: given a received word, find all codewords within Hamming distance $ρ n$ for $ρ > δ /2$ . The expander structure enables linear-time list decoding up to the Zyablov radius (a bound derived from the concatenation structure), and subsequent work by Guruswami and Rudra achieved list-decoding capacity.

The key technique is to reduce the list-decoding problem for the expander code to the list-decoding problem for the local code at each check node. Since the local code is small (length $b = O (1)$ ), list-decoding it is fast. The expansion property ensures that the local lists can be combined consistently into a global list.

Synthesis. Expander codes are the graph-theoretic bridge between combinatorics 40.04.01 and coding theory; the central insight is that the expansion property translates directly into good minimum distance and efficient decoding; this builds toward the LDPC framework in 46.08.01 where belief propagation generalises the GMD decoder; putting these together, expander codes demonstrate that global coding-theoretic properties (distance, rate) can be engineered from local combinatorial structures (graph expansion, local codes); the foundational reason this works is that expansion forces errors to spread across many checks, preventing any error pattern from hiding, and this generalises to the message-passing paradigm of modern coding theory.

Full proof set Master

Proposition (Rate of expander codes). The expander code $C (G, C_{0})$ where $G$ is a $d$ -left-regular bipartite graph with $∣ L ∣ = n$ and $∣ R ∣ = m$ , and $C_{0} \subseteq F_{2}^{b}$ has dimension $k_{0}$ , has rate at least $1 - m (b - k_{0}) / n$ .

Proof. The code $C (G, C_{0})$ is a linear subspace of $F_{2}^{n}$ defined by the constraints that each check node's local view is a codeword of $C_{0}$ . Each check node contributes at most $b - k_{0}$ independent linear constraints (the parity-check matrix of $C_{0}$ has $b - k_{0}$ rows). The total number of constraints is at most $m (b - k_{0})$ , though some may be linearly dependent. Therefore:

dim (C) \geq n - m (b - k_{0}),

and the rate is $R = dim (C) / n \geq 1 - m (b - k_{0}) / n$ . Since $m = n d / b$ (each variable has $d$ edges and each check has $b$ edges, so $n d = mb$ ), the rate is $\geq 1 - d (b - k_{0}) / b = 1 - d (1 - r_{0})$ . $□$

Proposition (GMD decoding convergence). If $G$ is a $(δ, 3/4 + ϵ)$ -expander and the error pattern has weight $w \leq δ n /2$ , then GMD decoding corrects all errors in at most $w$ iterations.

Proof. At each iteration, the decoder flips a variable that is in more unsatisfied checks than satisfied ones. Let $S$ be the current error set (initially of size $w$ ). The unique neighbours of $S$ are check nodes seeing exactly one error, which are necessarily unsatisfied (since $d_{0} \geq 2$ means a single non-zero bit violates the local code). There are at least $(3/4 + ϵ) d ∣ S ∣$ unique neighbours.

Each variable in $S$ has at most $(1/4 - ϵ) d$ edges going to non-unique neighbours. So the number of unsatisfied checks incident to any $v \in S$ is at least $(3/4 + ϵ) d ∣ S ∣/∣ S ∣ = (3/4 + ϵ) d$ per variable, minus potential double-counting. A careful count shows that each variable in $S$ has at least $(1/2 + 2 ϵ) d > d /2$ unsatisfied incident checks. Since each variable has exactly $d$ incident checks, more than half are unsatisfied, so every error variable is "bad" and eligible for flipping.

Flipping any bad variable reduces the error weight by 1. After at most $w$ flips, the error weight is zero and all checks are satisfied. $□$

Connections Master

46.07.01 — Weight enumerators and the MacWilliams identity provide the algebraic framework for bounding code distance; expander codes use graph-theoretic (rather than algebraic) distance arguments.
40.04.01 — Graph theory provides the expander graphs, spectral gap, Cheeger inequalities, and the combinatorial expansion property that underpin expander codes.
46.08.01 — LDPC codes on Tanner graphs use belief propagation, which generalises the GMD decoder; expansion determines the decoding threshold.
46.08.04 — Expander codes are one of several capacity-achieving code families; the unified view compares them with LDPC, turbo, and polar codes.
46.03.01 — Channel capacity is the target that expander-based code constructions aim to approach; the expansion property provides the structural mechanism for approaching it.

Historical & philosophical context Master

Michael Sipser and Daniel Spielman introduced expander codes in their 1996 paper "Expander Codes" (IEEE Transactions on Information Theory 42(6):1710-1722). Their key insight was that the expansion property of a graph, long studied in combinatorics and theoretical computer science, could be harnessed to construct codes with both good distance and linear-time decoding. Prior to their work, the best codes in terms of rate-distance tradeoff (such as algebraic geometry codes) required decoding algorithms with super-linear complexity.

The Tanner graph representation was introduced by Michael Tanner in 1981 ("A Recursive Approach to Low Complexity Codes," Information and Control 27(4):533-573). Tanner recognised that codes could be defined on bipartite graphs with local constraints at each check node, and that the graph structure determines the code properties. This paper laid the groundwork for both expander codes and LDPC codes.

Expander graphs themselves have a rich history. The explicit construction of expanders was achieved by Margulis (1973) using group representations, and optimised by Lubotzky, Phillips, and Sarnak (1988) who constructed Ramanujan graphs achieving the optimal spectral gap. The probabilistic method shows that random regular graphs are expanders with high probability, but explicit constructions are needed for code applications.

The connection between expansion and decoding was further developed by Zemor (2001) who improved the Sipser-Spielman decoding radius, and by Barg and Zemor (2002) who computed the error exponents of expander codes. Guruswami and Indyk (2000, 2005) showed that expander codes achieve linear-time list decoding, bringing them closer to the theoretical limits of coding.

Bibliography Master

@article{sipser-spielman1996,
  author  = {Sipser, M. and Spielman, D. A.},
  title   = {Expander Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {42},
  number  = {6},
  pages   = {1710--1722},
  year    = {1996},
}
@article{tanner1981,
  author  = {Tanner, R. M.},
  title   = {A Recursive Approach to Low Complexity Codes},
  journal = {Information and Control},
  volume  = {27},
  number  = {4},
  pages   = {533--573},
  year    = {1981},
}
@inproceedings{guruswami-indyk2000,
  author    = {Guruswami, V. and Indyk, P.},
  title     = {Expander-Based Constructions of Efficiently Decodable Codes},
  booktitle = {Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS)},
  pages     = {658--667},
  year      = {2000},
}
@article{barg-zemor2002,
  author  = {Barg, A. and Zemor, G.},
  title   = {Error Exponents of Expander Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {48},
  number  = {6},
  pages   = {1643--1648},
  year    = {2002},
}
@book{richardson-urbanke2008,
  author    = {Richardson, T. and Urbanke, R.},
  title     = {Modern Coding Theory},
  publisher = {Cambridge University Press},
  year      = {2008},
}
@article{lubotzky-phillips-sarnak1988,
  author  = {Lubotzky, A. and Phillips, R. and Sarnak, P.},
  title   = {Ramanujan Graphs},
  journal = {Combinatorica},
  volume  = {8},
  number  = {3},
  pages   = {261--277},
  year    = {1988},
}

Prerequisites

46.07.01
40.04.01

Tier anchors

beginner: Sipser & Spielman 1996 Expander Codes (IEEE Trans. IT) — the idea that a well-connected graph gives a good error-correcting code, explained through a picture of bits on nodes
intermediate: Sipser & Spielman 1996 Expander Codes §1-3 (definition of expander codes, Tanner graph representation, GMD decoding); Richardson & Urbanke 2008 Modern Coding Theory Ch. 3-4
master: Sipser & Spielman 1996; Tanner 1981 A Recursive Approach to Low Complexity Codes; Barg & Zemor 2002 Error Exponents of Expander Codes; Guruswami & Indyk 2000 Expander-Based Constructions of Efficiently Decodable Codes

References

Sipser, M. & Spielman, D. A. — Expander Codes · IEEE Transactions on Information Theory 42(6):1710-1722 (1996). Section II: an expander code is defined by a $d$ -regular bipartite graph $G = (L \cup R, E)$ where $∣ L ∣ = n$ (variable nodes) and $∣ R ∣ = n \cdot d / b$ (check nodes of degree $b$ ); the codewords are assignments to $L$ such that each check node in $R$ sees a valid local codeword in its neighbour set. Section III: the expansion property $δ (G) \geq 3/4 + ϵ$ guarantees that GMD decoding corrects up to a constant fraction of errors in linear time. Theorem 7: the code has rate $\geq 1 - d \cdot h (b) / b$ and minimum distance $\geq δ n$ .
Tanner, R. M. — A Recursive Approach to Low Complexity Codes · Information and Control 27(4):533-573 (1981). Introduces the Tanner graph representation of linear codes: a bipartite graph with variable nodes on one side and check nodes on the other; each check node enforces a parity constraint on its neighbours. Shows that codes defined on expander graphs have good distance properties.
Guruswami, V. & Indyk, P. — Expander-Based Constructions of Efficiently Decodable Codes · Proceedings of FOCS 2000, pp. 658-667. Constructs linear-time decodable codes from expander graphs with near-optimal rate-distance tradeoff; achieves list-decoding capacity using expander-based concatenation. The key tool is the unique-neighbour expansion property ensuring that errors cannot hide from the decoder.
Richardson, T. & Urbanke, R. — Modern Coding Theory · Cambridge University Press (2008). Chapter 3: LDPC codes as codes on graphs, the bipartite (Tanner) graph representation. Chapter 4: message-passing decoding on graphs, density evolution, and the connection between graph expansion and decoding threshold.

Estimated time

beginner: 15m
intermediate: 45m
master: 90m