Polar Codes and Channel Polarization — Mathematics Knowledge System

Overview

Polar codes, invented by Erdal Arikan in 2008, are the first family of error-correcting codes with a provably capacity-achieving construction for binary-input symmetric memoryless channels, with an explicit (not random) construction and efficient O(N log N) encoding and successive cancellation decoding. The key insight is channel polarization: by applying a recursive butterfly transform to N independent copies of a channel, the resulting N 'synthetic' bit-channels polarize — some become nearly perfect (capacity 1) and others become nearly useless (capacity 0). Information bits are sent on the good channels, and frozen bits on the bad ones. Polar codes are used in 5G NR control channels.

Intuition

Imagine combining two identical noisy channels using a butterfly operation: one combined channel becomes better than the original (more mutual information), and the other becomes worse. Applying this recursively for log_2(N) levels to N channels, the channels polarize: a fraction approaches capacity 1, and the complementary fraction approaches capacity 0. By sending information only on the good channels (and fixing known 'frozen' bits on the bad ones), successive cancellation decoding can reliably recover the message — achieving the Shannon limit as N grows.

Formal Definition

Definition

For a binary-input memoryless channel W: X -> Y with capacity I(W), the basic polarization transform combines two copies via the mapping (u1, u2) -> (u1 XOR u2, u2). Recursively applying this N = 2^n times yields N synthetic channels W_N^(i):

W^-: (u_1, u_2) \mapsto (y_1, y_2),\quad I(W^-) \leq I(W)

Worse synthetic channel (XOR combination)

W^+: (u_1, u_2) \mapsto (y_1, y_2, u_1),\quad I(W^+) \geq I(W)

Better synthetic channel (with side information)

I(W^-) + I(W^+) = 2\,I(W)

Polarization preserves total capacity

\lim_{n \to \infty} \frac{1}{N} \left|\{i : I(W_N^{(i)}) > 1 - \varepsilon\}\right| = I(W)

Channel polarization theorem: fraction of good channels equals I(W)

P_e \leq 2^{-N^\beta},\quad 0 < \beta < \tfrac{1}{2}

Error probability of successive cancellation decoding

Notation

Notation	Meaning
$W$	Binary-input memoryless channel
$I(W)$	Symmetric capacity of channel W
$W^+, W^-$	Good and bad synthetic channels after one polarization step
$W_N^{(i)}$	i-th synthetic channel after N-level recursive transform
$\mathcal{A}$	Information set: indices of good synthetic channels

Theorems

Theorem 1: Channel Polarization Theorem (Arikan)

For any binary-input memoryless symmetric channel W with capacity I(W) and any 0 < epsilon < 1, the fraction of synthetic channels W_N^(i) with I(W_N^(i)) > 1 -- epsilon converges to I(W) as N = 2^n -> infinity, and the fraction with I(W_N^(i)) < epsilon converges to 1 -- I(W).

Theorem 2: Capacity-Achieving Property of Polar Codes

Polar codes of rate R < I(W) with successive cancellation (SC) decoding achieve block error probability at most 2^{-N^beta} for any 0 < beta < 1/2, as block length N -> infinity.

Theorem 3: List Decoding Improvement

Successive cancellation list (SCL) decoding with list size L achieves near-ML performance for finite block lengths. With CRC concatenation, SCL decoding outperforms turbo and LDPC codes at short to moderate block lengths.

Worked Examples

1
Start with two independent BEC(epsilon) channels. Apply the transform: u1' = u1 XOR u2, u2' = u2.
$(x_1, x_2) = (u_1 \oplus u_2,\; u_2)$
2
Worse channel W^-: first bit u1 passes through both channels, effective erasure probability is 2*epsilon -- epsilon^2.
$P_{e}^- = 2\varepsilon - \varepsilon^2 = 1 - (1-\varepsilon)^2$
3
Better channel W^+: given u1, the second bit u2 is decoded using both received symbols, effective erasure probability is epsilon^2.
$P_{e}^+ = \varepsilon^2$
4
Total capacity is preserved: I(W^-) + I(W^+) = (1 - P_e^-) + (1 - P_e^+) = 2(1 - epsilon) = 2 I(W).
$I(W^-) + I(W^+) = 2\,I(W)$

✓ Answer

One polarization step on BEC(epsilon) produces a worse BEC(2*epsilon -- epsilon^2) and a better BEC(epsilon^2). Recursively, channels polarize toward 0 and 1.

Practice Problems

Mediumfree response

What are 'frozen bits' in polar codes, and why are they needed?

Hardapplication

Why do polar codes have better finite-length performance with list decoding and CRC?

Common Mistakes

Common Mistake

Polar codes have poor performance at finite block lengths.

Basic successive cancellation (SC) decoding does perform poorly at finite lengths, but CRC-aided successive cancellation list (CA-SCL) decoding gives excellent finite-length performance, matching or exceeding LDPC and turbo codes.

Common Mistake

Channel polarization means some channels get more noise added to them.

Polarization is a mathematical transformation of channel statistics via the butterfly operation. Channels do not become physically noisier; rather, the synthetic channels created by the transform have capacities that converge to 0 or 1.

Quiz

Polar codes were the first to provably achieve Shannon capacity with:

Exponential encoding complexityO(N log N) encoding and successive cancellation decodingRandom code constructionOnly for erasure channels

In 5G NR, polar codes are used for:

Data channelsControl channelsPilot signalsRandom access

Historical Background

Shannon's 1948 theorem guaranteed that capacity-achieving codes exist but did not construct them explicitly. Turbo codes and LDPC codes approach capacity but lack a proof of exact capacity achievement with polynomial complexity. Erdal Arikan's 2008 paper 'Channel Polarization: A Method for Constructing Capacity-Achieving Codes' was a landmark: it gave the first explicit, efficiently encodable and decodable capacity-achieving code family. Arikan received the Claude E. Shannon Award in 2018 for this work. Polar codes were adopted for 5G New Radio (NR) control channel coding in 2017.

2008
Arikan introduces polar codes and proves they achieve capacity for binary symmetric channels.
Erdal Arikan
2009
Arikan publishes the full paper in IEEE Transactions on Information Theory.
Erdal Arikan
2013
Tal and Vardy develop efficient construction algorithm for polar codes.
Ido Tal, Alexander Vardy
2015
List decoding (SCL) proposed by Tal and Vardy, significantly improving finite-length performance.
Ido Tal, Alexander Vardy
2017
3GPP selects polar codes for 5G NR control channels.
2018
Arikan receives the Claude E. Shannon Award.
Erdal Arikan

Summary

Polar codes, invented by Arikan (2008), are the first explicitly constructed capacity-achieving codes with O(N log N) complexity.
Channel polarization: recursive butterfly transforms cause N synthetic channels to polarize -- a fraction I(W) become perfect and the rest become useless.
Information bits go on good channels; frozen bits (known constants) on bad channels. Successive cancellation decoding achieves error probability 2^{-N^beta}.
CRC-aided list decoding (CA-SCL) dramatically improves finite-length performance; 5G NR uses polar codes for control channels.

References

PaperArikan, E. (2009). Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels. IEEE Transactions on Information Theory, 55(7), 3051-3073.
PaperTal, I., Vardy, A. (2015). List Decoding of Polar Codes. IEEE Transactions on Information Theory, 61(5), 2213-2226.
BookRichardson, T., Urbanke, R. (2008). Modern Coding Theory. Cambridge University Press.
WebsiteWikipedia — Polar code (coding theory)