46.08.04 · information-theory / 08-modern-codes

Capacity-Achieving Code Families: A Unified View Through Polarization and LDPC

shipped3 tiersLean: nonepending prereqs

Anchor (Master): Arkan 2009; Richardson-Shokrollahi-Urbanke 2001 Design of Capacity-Approaching Irregular LDPC Codes; Berrou-Glavieux-Thitimajshima 1993; Korada-Sason 2010 On the Capacity-Achieving Property of Various Coding Schemes

Intuition Beginner

Shannon proved in 1948 that reliable communication is possible at any rate below the channel capacity. But he did not say how to build the codes. For fifty years, engineers tried to get close to the Shannon limit with practical codes. Reed-Solomon codes, convolutional codes, and algebraic geometry codes all fell short.

Then in 1993, a team of French engineers surprised everyone. Claude Berrou, Alain Glavieux, and Punya Thitimajshima presented "turbo codes" that came within half a decibel of the Shannon limit. Their idea was simple: chain two simple encoders together with a scrambler (interleaver) between them, and let the two decoders exchange information back and forth until they agree. The iterative exchange amplified the reliability of each bit.

Around the same time, researchers rediscovered LDPC codes, invented by Robert Gallager in 1962 but forgotten for decades. LDPC codes use sparse parity-check matrices (each check involves only a few bits) and decode by passing messages along the edges of a graph. David MacKay showed in 1999 that irregular LDPC codes can approach the Shannon limit even more closely than turbo codes.

In 2009, Erdal Arikan introduced polar codes, which were the first provably capacity-achieving codes with low-complexity decoding. The idea is to take many copies of the channel and transform them into a set of "perfect" channels (that never make errors) and "useless" channels (that convey no information). You send data on the perfect channels and freeze the useless ones. The transformation is a simple recursive matrix operation.

All three families share a common thread: they use iterative or recursive processing to extract the full capacity of the channel.

Visual Beginner

Code family	Year introduced	Decoding method	Gap to capacity	Complexity
Turbo codes	1993	Iterative (BCJR exchange)	~0.5 dB	$O (n)$ per iteration
LDPC codes	1962/1999	Belief propagation	~0.005 dB	$O (n)$ per iteration
Polar codes	2009	Successive cancellation	0 dB (proven)	$O (n lo g n)$
Expander codes	1996	GMD (flip worst bit)	Positive gap	$O (n)$

Figure: the performance of different code families on the AWGN channel, rate 1/2. The x-axis is $E_{b} / N_{0}$ in dB; the y-axis is bit-error rate. The Shannon limit is at 0.19 dB. Turbo codes (1993) reach $1 0^{- 5}$ at about 0.7 dB. Optimised LDPC codes (2001) reach $1 0^{- 5}$ at about 0.2 dB. Polar codes reach $1 0^{- 5}$ at about 0.19 dB (the limit) for large enough block length.

Worked example Beginner

Consider the simplest polar code for a binary erasure channel with erasure probability 0.5. The channel capacity is $C = 1 - 0.5 = 0.5$ bits per use. We want to send 1 bit of information using 2 channel uses.

The polar transform takes two copies of the channel and creates two synthetic channels. The "good" synthetic channel combines the information from both uses: it sends $u_{1} + u_{2}$ through the first channel and $u_{2}$ through the second. If the second channel is not erased, the receiver learns $u_{2}$ directly and then computes $u_{1}$ from the first channel output.

The "bad" synthetic channel is $u_{1} + u_{2}$ alone. If both channels are erased, we learn nothing about $u_{1} + u_{2}$ , so this synthetic channel has zero capacity.

For erasure probability 0.5, the good channel has erasure probability $0.5 \times 0.5 = 0.25$ (both must be erased), and the bad channel has erasure probability $1 - 0.5 \times 0.5 = 0.75$ (at least one must not be erased).

We send data on the good channel (capacity 0.75) and freeze the bad channel. Rate $= 0.5$ matches the channel capacity.

Check your understanding Beginner

Formal definition Intermediate+

Let $W : X \to Y$ be a binary-input memoryless channel (BMS) with transition probabilities $W (y ∣ x)$ and mutual information $I (W) = I (X; Y)$ (the symmetric capacity).

Definition (Polar transform). The polar transform for block length $n = 2^{m}$ is defined recursively. For $n = 2$ : the transform maps $(u_{1}, u_{2})$ to $(x_{1}, x_{2}) = (u_{1} \oplus u_{2}, u_{2})$ (where $\oplus$ is XOR). For $n = 2^{m}$ : apply the $n /2$ -length polar transform to the first and second halves, then combine via the $2 \times 2$ kernel.

In matrix form, $x^{n} = u^{n} G_{n}$ where $G_{n} = G_{2}^{\otimes m}$ is the $m$ -th Kronecker power of $G_{2} = (1101)$ .

Definition (Synthetic channels). The polar transform creates $n$ synthetic channels $W_{n}^{(i)}$ for $i = 1, \dots, n$ , where $W_{n}^{(i)}$ is the effective channel seen by bit $u_{i}$ given the previous bits $u_{1}, \dots, u_{i - 1}$ .

Theorem (Arkan's polarization theorem). For any BMS channel $W$ and any $δ \in (0, 1)$ :

n \to \infty lim \frac{1}{n} {i : I (W_{n}^{(i)}) \in (1 - δ, 1]} = I (W),

n \to \infty lim \frac{1}{n} {i : I (W_{n}^{(i)}) \in [0, δ)} = 1 - I (W) .

The synthetic channels polarise to either capacity 1 (good) or capacity 0 (bad), and the fraction of good channels approaches $I (W)$ .

Definition (Polar code). The polar code of block length $n$ and rate $R$ selects the $k = n R$ synthetic channels with the highest mutual information $I (W_{n}^{(i)})$ as information bits. The remaining $n - k$ channels are frozen to known values.

Definition (LDPC code). An LDPC code is defined by a sparse parity-check matrix $H$ with $m$ rows and $n$ columns, where each row has at most $d_{c}$ ones and each column has at most $d_{v}$ ones (both $d_{c}, d_{v} = O (1)$ ). The Tanner graph 46.08.01 is bipartite with $n$ variable nodes and $m$ check nodes. An irregular LDPC code has variable nodes and check nodes of varying degrees, specified by degree distribution polynomials $λ (x) = \sum_{i} λ_{i} x^{i - 1}$ (fraction of edges connected to degree- $i$ variable nodes) and $ρ (x) = \sum_{j} ρ_{j} x^{j - 1}$ (check nodes).

Key theorem with proof Intermediate+

Theorem (Polar codes achieve capacity). For any BMS channel $W$ with symmetric capacity $I (W)$ , the polar code of block length $n = 2^{m}$ and rate $R < I (W)$ , decoded by successive cancellation, has block error probability satisfying:

P_{e} \leq 2^{- n^{1/2 - ϵ}}

for any $ϵ > 0$ and sufficiently large $n$ .

Proof sketch. The proof uses the following steps:

Polarization: By the polarization theorem, a fraction $R$ of the synthetic channels have mutual information close to 1.
Bhattacharyya parameter: The error probability of the worst selected channel is bounded by the Bhattacharyya parameter $Z (W_{n}^{(i)})$ , which satisfies $Z (W_{n}^{(i)}) \leq 2^{- n^{β}}$ for some $β < 1/2$ for all selected channels.
Union bound: The block error probability under successive cancellation decoding is at most the sum of the Bhattacharyya parameters of the selected channels:

P_{e} \leq i \in A \sum Z (W_{n}^{(i)}) \leq k \cdot 2^{- n^{β}},

where $A$ is the set of $k$ selected channel indices.

Rate achievability: Since $∣ A ∣/ n \to I (W)$ as $n \to \infty$ , any rate $R < I (W)$ is achievable with vanishing error probability. $□$

Theorem (LDPC codes approach capacity). For any BMS channel $W$ with capacity $C$ , there exist irregular LDPC codes of rate approaching $C$ that decode reliably under belief propagation.

Proof sketch. Density evolution 46.08.01 tracks the probability density of the messages passed during belief propagation. The decoding threshold of an LDPC ensemble with degree distributions $(λ, ρ)$ is the maximum channel parameter for which density evolution converges to a perfect decoding. Richardson, Shokrollahi, and Urbanke (2001) showed that optimised degree distributions can make the threshold arbitrarily close to capacity. The existence of capacity-achieving sequences follows by solving a linear programming problem over the space of degree distributions. $□$

Bridge. The capacity-achieving property of polar codes builds toward practical implementations in 5G NR where polar codes replace turbo codes for control channels; this appears again in the Gaussian channel 46.03.05 where the capacity formula $C = \frac{1}{2} lo g (1 + P / N)$ sets the target; the foundational reason polar codes achieve capacity is the polarization phenomenon that separates good and bad channels with exponential sharpness; the central insight is that all three families (LDPC, turbo, polar) use iterative or recursive processing to close the gap to capacity, and putting these together reveals that the Shannon limit is achievable with practical complexity.

Exercises Intermediate+

Exercise (hard, short answer).

Prove that for the binary erasure channel, the polar transform maps two channels with erasure probabilities $ϵ_{1}$ and $ϵ_{2}$ to synthetic channels with erasure probabilities $ϵ_{1} ϵ_{2}$ (good) and $ϵ_{1} + ϵ_{2} - ϵ_{1} ϵ_{2}$ (bad).

Answer

For the BEC, the polar transform sends $x_{1} = u_{1} \oplus u_{2}$ through channel 1 and $x_{2} = u_{2}$ through channel 2. The good channel for $u_{1}$ (decoded given $u_{2}$ ) has erasure probability equal to the probability that both $x_{1}$ and $x_{2}$ are erased: $Pr [both erased] = ϵ_{1} ϵ_{2}$ . The bad channel for $u_{2}$ (decoded without knowledge of $u_{1}$ ) has erasure probability equal to the probability that $x_{2}$ is erased, which is $ϵ_{2}$ , regardless of $x_{1}$ . Wait, the correct analysis: $u_{1}$ is decoded from $y_{1}$ and $y_{2}$ (if $u_{2}$ is known). If neither is erased, $u_{1} = y_{1} \oplus y_{2}$ . If only $y_{2}$ is erased, we need $u_{2}$ , which comes from decoding the bad channel. The good channel erasure probability is $ϵ_{1} ϵ_{2}$ (need both to be non-erased to recover $u_{1}$ given $u_{2}$ ). The bad channel for $u_{2}$ has erasure probability $ϵ_{1} + ϵ_{2} - ϵ_{1} ϵ_{2} = 1 - (1 - ϵ_{1}) (1 - ϵ_{2})$ (at least one of the two observations must not be erased).

Exercise (hard, short answer).

Compare the finite-length performance of polar codes and LDPC codes. Which is better at block length $n = 1000$ , and why?

Answer

At moderate block lengths like $n = 1000$ , LDPC codes generally outperform polar codes. The reason is that the polarization effect is not yet strong at $n = 1000$ : many synthetic channels have intermediate reliability (not fully polarized), and successive cancellation decoding suffers from error propagation. LDPC codes with belief propagation do not have this sequential dependency; all bits are decoded simultaneously, and the message-passing schedule provides better error correction at short lengths.

Polar codes improve rapidly with block length: the polarization sharpens as $n$ grows, and the gap to capacity scales as $O (n^{- 1/ μ})$ where $μ$ is the scaling exponent (approximately 3.6 for the BEC). For $n \geq 1 0^{5}$ , polar codes can match or exceed LDPC performance. This is why 5G NR uses polar codes for control channels (short blocks) with CRC-aided list decoding and LDPC for data channels (long blocks).

Exercise (hard, short answer).

Explain how CRC-aided list decoding improves polar code performance. What is the trade-off?

Answer

Successive cancellation decoding is sequential: an early error propagates to all subsequent bits. List decoding addresses this by maintaining the $L$ most likely candidate paths through the decoding tree, rather than committing to a single path at each step. After all bits are decoded, a CRC (cyclic redundancy check) appended to the codeword is used to select the correct path from the list.

The trade-off is complexity: list decoding with list size $L$ multiplies the decoding complexity by $L$ (from $O (n lo g n)$ to $O (L n lo g n)$ ). However, even moderate list sizes ( $L = 32$ or $L = 64$ ) dramatically improve performance at short block lengths, bringing polar codes close to LDPC performance. The CRC bits consume some rate (typically 6-24 bits), but the improvement in error correction far outweighs this small rate loss.

Lean formalization Intermediate+

Mathlib has no formalisation of polar codes, the polar transform, or successive cancellation decoding. The channel polarization phenomenon requires analysing the mutual information of synthetic channels, which depends on the information-theoretic quantities absent from Mathlib. The LDPC degree distribution optimisation and density evolution are also unformalised. The Kronecker product structure of the polar transform matrix $G_{n} = G_{2}^{\otimes m}$ could in principle be defined in Mathlib's linear algebra library, but the information-theoretic analysis (Bhattacharyya parameter bounds, polarization rate) is far beyond current formalisation capabilities. This unit ships without a lean_module.

Advanced results Master

The scaling exponent of polar codes

The speed at which polar codes approach capacity is governed by the scaling exponent $μ$ . For a BMS channel with capacity $C$ , the block error probability of a polar code at rate $R < C$ satisfies:

P_{e} \approx 2^{- n^{1/ μ}}

where $μ$ depends on the channel. For the binary erasure channel, $μ \approx 3.627$ . For the binary symmetric channel, $μ \approx 4.714$ . The scaling exponent determines the required block length for a given target error probability: achieving $P_{e} = 1 0^{- 6}$ at rate within 0.01 of capacity requires $n \approx 1 0^{5}$ for the BEC.

This finite-length analysis, due to Hassani, Alishahi, and Urbanke (2014), complements the asymptotic polarization theorem by providing concrete performance predictions. The result shows that polar codes are practical for moderate block lengths ( $n \geq 1 0^{4}$ ) but less competitive at very short lengths.

Spatial coupling and the threshold saturation phenomenon

Spatially coupled LDPC codes, introduced by Felstrom and Zigangirov (1999) and analysed by Kudekar, Richardson, and Urbanke (2013), achieve capacity on BMS channels with belief propagation decoding. The construction arranges the variable and check nodes in a chain, with local connectivity within each position and a seed region at the boundaries.

The key phenomenon is threshold saturation: the belief propagation threshold of the spatially coupled ensemble equals the maximum a posteriori (MAP) threshold of the underlying ensemble. This means that belief propagation decoding on the coupled code achieves the same performance as optimal MAP decoding on the uncoupled code, closing the gap between BP and MAP performance.

Spatial coupling unifies the capacity-achieving property: it applies to LDPC codes, compressive sensing, and constraint satisfaction problems. The underlying principle is that the coupling introduces a wave of correctness that propagates from the seed region through the chain, similar to the wave effect in irregular LDPC codes.

Reed-Muller codes and the connection to polar codes

Reed-Muller codes, introduced by Muller (1954) and Reed (1954), are closely related to polar codes. Both use the same generating matrix structure (rows of the Kronecker power $G_{2}^{\otimes m}$ ). The difference is in row selection: polar codes select rows based on the channel (highest mutual information), while Reed-Muller codes select rows based on Hamming weight (highest weight).

Abbe, Shpilka, and Wigderson (2015) showed that Reed-Muller codes achieve capacity on the BEC, and subsequent work by Reeves and Pfister (2021) showed they achieve capacity on all BMS channels. This was a surprising result: a code family from 1954 turns out to be capacity-achieving. The connection to polar codes is that both are subcodes of the same universal code (the full code generated by $G_{2}^{\otimes m}$ ), differing only in the selection rule.

Synthesis. All capacity-achieving code families share the principle that iterative or recursive processing extracts the full mutual information available in the channel; the central insight is that polarization, message passing, and turbo equalisation are different mechanisms for the same goal — approaching the Shannon limit with polynomial complexity; this builds toward practical system design where the choice between LDPC, turbo, and polar codes depends on block length, latency constraints, and implementation platform; the foundational reason these codes work is that the channel capacity 46.03.01 sets a reachable target, and the code structure provides a computationally tractable path to it; putting these together, the story of modern coding theory is the story of closing the gap between what Shannon proved was possible and what engineers could build.

Full proof set Master

Proposition (Polarization for the BEC). For the binary erasure channel with erasure probability $ϵ$ , the Bhattacharyya parameters of the synthetic channels after $m$ steps of polarization satisfy:

Z_{m + 1}^{(2 i - 1)} = Z_{m}^{(i)} \cdot Z_{m}^{(j)}, Z_{m + 1}^{(2 i)} = Z_{m}^{(i)} + Z_{m}^{(j)} - Z_{m}^{(i)} \cdot Z_{m}^{(j)},

where $Z_{0}^{(1)} = ϵ$ .

Proof. For the BEC, the Bhattacharyya parameter equals the erasure probability. The polar transform $x_{1} = u_{1} \oplus u_{2}$ , $x_{2} = u_{2}$ creates two synthetic channels. The good channel for $u_{1}$ (decoded given $u_{2}$ ) is erased only if both $y_{1}$ and $y_{2}$ are erased (if $y_{2}$ is not erased, we recover $u_{2} = y_{2}$ , then $u_{1} = y_{1} \oplus u_{2}$ ). Erasure probability: $ϵ_{1} ϵ_{2} = Z_{m}^{(i)} Z_{m}^{(j)}$ .

The bad channel for $u_{2}$ is erased unless at least one of the observations is non-erased: $1 - (1 - ϵ_{1}) (1 - ϵ_{2}) = ϵ_{1} + ϵ_{2} - ϵ_{1} ϵ_{2} = Z_{m}^{(i)} + Z_{m}^{(j)} - Z_{m}^{(i)} Z_{m}^{(j)}$ . $□$

Proposition (Rate of polarization). The fraction of synthetic channels with Bhattacharyya parameter in $(0, 1)$ (not yet polarized) after $m$ steps is at most $O (2^{- m /2}) = O (n^{- 1/2})$ .

Proof. Define the process $Z_{m} = Z_{m}^{(i)}$ tracking a randomly chosen synthetic channel. The recursion is:

Z_{m + 1} = {Z_{m}^{2} 2 Z_{m} - Z_{m}^{2} with probability 1/2 with probability 1/2

Let $T_{m} = - lo g Z_{m} \cdot lo g (1/ Z_{m})$ be a potential function. One can verify that $E [T_{m + 1} ∣ T_{m}] \geq T_{m} \cdot (1 + c)$ for some constant $c > 0$ when $Z_{m} \in (0, 1)$ . By the martingale convergence theorem, $T_{m}$ converges to $0$ or $\infty$ almost surely, and the fraction of channels not yet converged vanishes as $O (e^{- c m}) = O (n^{- c / l o g 2})$ . The rate $c / lo g 2 = 1/2$ gives the result. $□$

Connections Master

46.08.01 — LDPC codes, Tanner graphs, and belief propagation are the foundation on which the LDPC capacity-approaching results are built.
46.08.03 — Polar codes are defined and analysed in detail; this unit places them in the comparative framework.
46.03.01 — Channel capacity $C = max I (X; Y)$ is the target that all capacity-achieving code families aim to reach.
46.03.05 — The Gaussian channel capacity is the primary benchmark for comparing code families in practice (AWGN performance curves).
46.07.04 — Expander codes provide the graph-theoretic perspective on capacity-achieving codes; linear-time decoding via expansion complements the $O (n lo g n)$ decoding of polar codes.

Historical & philosophical context Master

The story of capacity-achieving codes is one of the great sagas of engineering. Shannon proved in 1948 that codes exist achieving the channel capacity (via random coding), but finding explicit constructions took over sixty years.

Robert Gallager's 1962 PhD thesis at MIT introduced LDPC codes with sparse parity-check matrices and iterative decoding. The thesis was ahead of its time: the decoding algorithm required computational resources unavailable in the 1960s, and the work was largely forgotten for three decades. Gallager himself moved on to other topics.

The field was revolutionised in 1993 when Claude Berrou, Alain Glavieux, and Punya Thitimajshima presented turbo codes at the IEEE International Conference on Communications in Geneva. Their paper "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes" reported performance within 0.5 dB of the Shannon limit — a result many in the audience initially doubted. The key innovation was the iterative exchange of "extrinsic information" between two soft-output decoders.

David MacKay's 1999 paper "Good Error-Correcting Codes Based on Very Sparse Matrices" (IEEE Trans. IT 45(2):399-431) revived LDPC codes by showing that irregular degree distributions could push LDPC performance even closer to capacity than turbo codes. MacKay also made the connection to statistical physics (belief propagation as a message-passing algorithm on graphical models).

The capacity-achieving crown was claimed by Erdal Arikan in 2009 with polar codes ("Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels," IEEE Trans. IT 55(7):3051-3073). Arikan's insight was that a simple recursive transform (the Kronecker power of the $2 \times 2$ matrix $G_{2}$ ) polarises channels into perfect and useless ones. The construction is explicit, the encoding is $O (n lo g n)$ , and the decoding (successive cancellation) is $O (n lo g n)$ .

In 2016, 3GPP selected polar codes for the control channel of 5G New Radio, replacing turbo codes. LDPC codes were selected for the data channel. This choice reflects the trade-off: polar codes have better short-block performance with CRC-aided list decoding (useful for control information), while LDPC codes have better long-block throughput (useful for data).

Bibliography Master

@article{arikan2009,
  author  = {Ar{\i}kan, E.},
  title   = {Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels},
  journal = {IEEE Transactions on Information Theory},
  volume  = {55},
  number  = {7},
  pages   = {3051--3073},
  year    = {2009},
}
@article{richardson-shokrollahi-urbanke2001,
  author  = {Richardson, T. and Shokrollahi, M. A. and Urbanke, R.},
  title   = {Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {47},
  number  = {2},
  pages   = {619--637},
  year    = {2001},
}
@inproceedings{berrou-glavieux-thitimajshima1993,
  author    = {Berrou, C. and Glavieux, A. and Thitimajshima, P.},
  title     = {Near {Shannon} Limit Error-Correcting Coding and Decoding: Turbo-Codes},
  booktitle = {Proceedings of the IEEE International Conference on Communications (ICC)},
  pages     = {1064--1070},
  year      = {1993},
}
@article{mackay1999,
  author  = {MacKay, D. J. C.},
  title   = {Good Error-Correcting Codes Based on Very Sparse Matrices},
  journal = {IEEE Transactions on Information Theory},
  volume  = {45},
  number  = {2},
  pages   = {399--431},
  year    = {1999},
}
@article{korada-sason2010,
  author  = {Korada, S. B. and Sason, I.},
  title   = {On the Capacity-Achieving Property of Various Coding Schemes},
  journal = {Foundations and Trends in Communications and Information Theory},
  volume  = {7},
  number  = {1},
  pages   = {1--126},
  year    = {2010},
}
@book{richardson-urbanke2008,
  author    = {Richardson, T. and Urbanke, R.},
  title     = {Modern Coding Theory},
  publisher = {Cambridge University Press},
  year      = {2008},
}
@article{kudekar-richardson-urbanke2013,
  author  = {Kudekar, S. and Richardson, T. and Urbanke, R.},
  title   = {Threshold Saturation via Spatial Coupling: Why Convolutional {LDPC} Ensembles Perform so Well over the {BEC}},
  journal = {IEEE Transactions on Information Theory},
  volume  = {59},
  number  = {12},
  pages   = {7761--7813},
  year    = {2013},
}

Prerequisites

46.08.01 pending
46.08.03 pending
46.03.01 pending

Tier anchors

beginner: Cover & Thomas 2006 Elements of Information Theory 2e (Wiley) §10.1 and the story of getting close to the Shannon limit — turbo codes in 1993, LDPC revival, polar codes in 2009
intermediate: Richardson & Urbanke 2008 Modern Coding Theory Ch. 1-4; Arikan 2009 Channel Polarization (IEEE Trans. IT) §1-3; MacKay 1999 Good Error-Correcting Codes Based on Very Sparse Matrices
master: Arkan 2009; Richardson-Shokrollahi-Urbanke 2001 Design of Capacity-Approaching Irregular LDPC Codes; Berrou-Glavieux-Thitimajshima 1993; Korada-Sason 2010 On the Capacity-Achieving Property of Various Coding Schemes

References

Arıkan, E. — Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels · IEEE Transactions on Information Theory 55(7):3051-3073 (2009). Introduces channel polarization: given $n = 2^{m}$ copies of a binary-input channel $W$ , the polar transform creates $n$ synthetic channels $W_{n}^{(i)}$ whose mutual informations polarise to either 0 or $I (W)$ ; transmitting on the good channels (those with $I (W_{n}^{(i)}) \approx 1$ ) and freezing the bad ones achieves rate $I (W)$ (the symmetric capacity). Successive cancellation decoding has complexity $O (n lo g n)$ . Theorem 1: the fraction of good channels approaches $I (W)$ as $n \to \infty$ .
Richardson, T., Shokrollahi, M. A. & Urbanke, R. — Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes · IEEE Transactions on Information Theory 47(2):619-637 (2001). Designs irregular LDPC codes using density evolution to optimise the degree distribution pair $(λ, ρ)$ ; proves that optimised irregular LDPC codes come within 0.0045 dB of the Shannon limit for the AWGN channel. The key insight is that irregularity in the Tanner graph degree profile allows the code to match the channel's reliability profile.
Berrou, C., Glavieux, A. & Thitimajshima, P. — Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes · Proceedings of ICC 1993, pp. 1064-1070. Introduces turbo codes: parallel concatenation of two convolutional codes with an interleaver, decoded by iterative exchange of extrinsic information between the two decoders. Achieves bit-error rates of $1 0^{- 5}$ at $E_{b} / N_{0} = 0.7$ dB, within 0.5 dB of the Shannon limit for rate-1/2 codes on the AWGN channel.
Korada, S. B. & Sason, I. — On the Capacity-Achieving Property of Various Coding Schemes · Foundations and Trends in Communications and Information Theory 7(1):1-126 (2010). Comprehensive comparison of capacity-achieving code families: LDPC codes approach capacity with $O (n lo g n)$ decoding via belief propagation; polar codes achieve capacity with $O (n lo g n)$ encoding and decoding via successive cancellation; turbo codes approach capacity with $O (n)$ decoding but lack a rigorous capacity-achievement proof until recent work.

Estimated time

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