Polar Codes: Arikan's Channel Polarization Phenomenon and Successive Cancellation

Intuition Beginner

Take a noisy channel and make two copies of it. Combine them with a simple operation: add the first input to the second. You get two new channels. One is better than the original (its output reveals more about the input) and one is worse (its output is noisier).

This is the basic polarisation step. Repeat it ${\log }_{2}n$ times for $n$ channel uses. The result is dramatic: most of the $n$ synthesized channels become either nearly perfect (capacity close to 1) or nearly useless (capacity close to 0). The fraction of perfect channels equals the original channel capacity.

Send information only on the perfect channels and freeze the useless ones to known values. This is the polar code. It achieves the channel capacity with a simple, deterministic construction.

Decoding uses successive cancellation: decode the bits one at a time, using all previous decisions to inform the current one. If the current bit is frozen, skip it. If it is information, use the channel output and all previously decoded bits to make the best guess. The complexity is $O(n\log n)$ — fast enough for practical use.

The key quantity is the Bhattacharyya parameter $Z(W)$, which measures how noisy a channel is. At each polarisation step, $Z$ evolves: it either roughly squares (the channel gets much better) or roughly doubles (the channel gets much worse). After ${\log }_{2}n$ steps, most $Z$ values are extremely close to 0 or 1, which is the polarisation phenomenon.

Polar codes have a distinctive advantage over LDPC and turbo codes: their construction is deterministic and provably optimal, rather than relying on random ensemble arguments. For the BEC, the Bhattacharyya recursion can be computed exactly, giving a precise ranking of bit channels by reliability. For the BSC, the recursion involves more complex calculations, but the qualitative picture is the same. In both cases, the code designer selects the $k$ most reliable channels for information and freezes the rest, where $k=nR$ is determined by the target rate.

Visual Beginner

Figure: a tree diagram showing one level of channel polarisation. Channel $W$ splits into $W^{-}$ (worse, $Z^{-}=2Z-Z^2$) and $W^{+}$ (better, $Z^{+}=Z^2$). After 3 levels, 8 channels emerge: most have $Z\approx 0$ (good) or $Z\approx 1$ (bad), with the fraction of good channels equal to $C=1-Z_0$.

Polarisation level	Channels	Good ($Z\approx 0$)	Bad ($Z\approx 1$)	Mixed ($Z$ neither)
0 (original)	1	0	0	1
1	2	~$C$ fraction	~$(1-C)$ fraction	some
5	32	~$32C$	~$32(1-C)$	few
10	1024	~$1024C$	~$1024(1-C)$	very few
20	$10^6$	~$10^{6}C$	~$10^6(1-C)$	negligible

The mixed channels vanish as the block length grows, leaving only perfect and useless channels.

Worked example Beginner

Consider the BEC with erasure probability $\alpha =0.5$, so $C=0.5$. The initial Bhattacharyya parameter is $Z_0=\alpha =0.5$.

Level 1: Two channels.

• $W^{-}$: $Z^{-}=2Z_0-Z_0^2=2(0.5)-0.25=0.75$
• $W^{+}$: $Z^{+}=Z_0^2=0.25$

Level 2: Four channels (apply the split again to each).

• From $W^{-}$: $Z^{--}=2(0.75)-0.5625=0.9375$, $Z^{-+}=0.5625$
• From $W^{+}$: $Z^{+-}=2(0.25)-0.0625=0.4375$, $Z^{++}=0.0625$

Level 3: Eight channels.

• $Z^{---}=2(0.9375)-0.879=0.996$, $Z^{--+}=0.879$
• $Z^{-+-}=2(0.5625)-0.316=0.809$, $Z^{-++}=0.316$
• $Z^{+--}=2(0.4375)-0.191=0.684$, $Z^{+-+}=0.191$
• $Z^{++-}=2(0.0625)-0.0039=0.121$, $Z^{+++}=0.0039$

After 3 levels: channels with $Z<0.5$ are $Z^{+-+}=0.191$, $Z^{++-}=0.121$, $Z^{+++}=0.0039$, $Z^{-++}=0.316$ — four out of eight. The capacity is $C=0.5$, so we expect 4 good channels. The polarisation is already evident: the extremes ($Z^{+++}=0.004$ and $Z^{---}=0.996$) are far from the original $Z=0.5$.

Check your understanding Beginner

Formal definition Intermediate+

Let $W:\mathcal{X}\to \mathcal{Y}$ be a binary-input memoryless symmetric channel (BMS) with transition probabilities $W(y|x)$.

Definition (Bhattacharyya parameter). The Bhattacharyya parameter of $W$ is

$$Z(W)=\sum _y\sqrt{W(y|0)W(y|1)}.$$

$Z(W)\in [0,1]$ with $Z(W)=0$ iff $W$ is noiseless and $Z(W)=1$ iff $W$ is completely noisy. For the BEC with erasure probability $\alpha$: $Z(W)=\alpha$. For the BSC with crossover probability $p$: $Z(W)=2\sqrt{p(1-p)}$.

Definition (Arikan transform). The Arikan kernel is the matrix $G_2=\left(\begin{array}{cc}1& 0\\ 1& 1\end{array}\right)$. The $n\times n$ polarisation transform is $G_n=G_2^{\otimes m}$ where $n=2^m$.

The input vector $\mathbf{u}=(u_1,\dots ,u_n)$ is encoded as $\mathbf{x}=\mathbf{u}{G}_n$. The $n$ channel uses transmit $\mathbf{x}$ through $n$ copies of $W$.

Definition (Synthesized channels). The $i$-th synthesized channel $W_n^{(i)}$ is the effective channel seen by bit $u_i$, given that bits $u_1,\dots ,u_{i-1}$ are known and bits $u_{i+1},\dots ,u_n$ are unknown:

$$W_n^{(i)}(y^n,u^{i-1}|u_i)=\frac{1}{2^{n-1}}\sum _{u_{i+1}^n\in \{0,1{\}}^{n-i}}{W}^n(y^n|u^n{G}_n).$$

Key theorem with proof Intermediate+

Theorem (Channel polarization). For any BMS channel $W$, as $n=2^m\to \infty$, the synthesized channels polarise:

$$\underset{n\to \infty }{\lim }\frac{1}{n}|\{i:Z(W_n^{(i)})\in (\delta ,1-\delta )\}|=0\text{for all }\delta >0,$$

and the fraction of capacity-1 channels converges to $C(W)$:

$$\underset{n\to \infty }{\lim }\frac{1}{n}|\{i:Z(W_n^{(i)})<\delta \}|=C(W)\text{for all }\delta >0.$$

Proof sketch. The proof uses the recursive structure of the Bhattacharyya parameter.

Step 1: Evolution. At each polarisation step, the two child channels satisfy:

$$Z(W^{-})=2Z(W)-Z(W{)}^2,Z(W^{+})=Z(W{)}^2.$$

For the BEC, this is exact. For general BMS channels, the recursion involves a more complex averaging, but the qualitative behaviour is the same.

Step 2: Martingale argument. Define the random process $Z_m$ by choosing at each level whether to go to $W^{-}$ or $W^{+}$ with equal probability. Then $Z_m$ is a bounded martingale (it converges by the martingale convergence theorem). The limit $Z_{\infty }$ must satisfy the fixed-point equation of the recursion. The only fixed points of $Z\mapsto Z^2$ (for $W^{+}$) are $0$ and $1$, and the only fixed points of $Z\mapsto 2Z-Z^2$ are $0$ and $1$.

Step 3: Conservation of capacity. $C(W^{-})+C(W^{+})=2C(W)$, so the expected capacity is preserved. Since $Z_{\infty }\in \{0,1\}$ almost surely and $C(W)=1-\mathbb{E}[Z_{\infty }]$ (for the BEC; the relationship is $I(W)=1-H_b^{-1}$... more precisely $I(W)\approx 1-Z(W)$ for small $Z$), the fraction of channels with $Z_{\infty }=0$ is $I(W)$.

Step 4: Rate of convergence. Arikan and Telatar (2009) showed that the fraction of unpolarised channels decreases as $O(2^{-\beta \sqrt{n}})$ for some $\beta >0$, which gives block error probability $P_e\le 2^{-n^{\beta }}$ for rate $R<C$. $\square$

Bridge. Channel polarization builds toward the explicit construction of capacity-achieving codes in 46.08.01 where LDPC codes achieve capacity via iterative decoding, and the foundational reason polar codes work is that the Arikan transform recursively amplifies the difference between reliable and unreliable bit channels. This is exactly the phenomenon that converts a moderately noisy channel into a bimodal mixture of near-perfect and near-useless channels. The central insight is that the Bhattacharyya parameter evolves multiplicatively ($Z^{+}=Z^2$) for the good channel and additively ($Z^{-}=2Z-Z^2$) for the bad channel, generalises to non-binary alphabets via the same transform structure, and appears again in 46.03.04 as the quality measure for the BSC and BEC whose capacities polar codes achieve. The bridge is the Kronecker product structure of the encoding matrix, and putting these together polar codes provide the first explicit, deterministic, low-complexity construction that provably achieves Shannon capacity.

Exercises Intermediate+

Lean formalization Intermediate+

Mathlib has matrix Kronecker products but lacks the channel model, Bhattacharyya parameter, synthesized channels, and the polarization theorem. A Codex.InformationTheory.PolarCodes module would need to define BMS channels, the Bhattacharyya parameter, the Arikan transform, and the recursive channel splitting. The polarization theorem is a deep result requiring martingale theory and analysis. This unit ships without formal verification.

Advanced results Master

Rate of polarization

The block error probability of a polar code of length $n=2^m$ at rate $R=I(W)-ϵ$ satisfies:

$$P_e\le 2^{-n^{\beta }}\text{for some }\beta <1/2.$$

Arikan and Telatar (2009) proved $\beta =1/2-o(1)$ for the BEC, and Korada, Sasoglu, and Urbanke (2010) characterised the polarization exponent for general channels. The exponent determines how quickly $P_e$ vanishes and hence the block length required for a target error probability.

For practical block lengths ($n\sim 10^3$ to $10^4$), the vanilla SC decoder is suboptimal compared to LDPC and turbo codes. The CRC-aided successive cancellation list (SCL) decoder (Tal and Vardy 2015) closes this gap by maintaining a list of candidate paths through the decoding tree and using a CRC to select the correct one, achieving near-ML performance.

Non-binary polar codes

The polarization phenomenon extends to non-binary alphabets via invertible linear transforms over ${\mathbb{F}}_q$. The kernel becomes a $q\times q$ matrix over ${\mathbb{F}}_q$, and the synthesized channels polarise according to the same martingale argument. Sahebi and Pradhan (2011) showed that non-binary polar codes can be constructed over any prime field with the same capacity-achieving property.

Polar codes for the wiretap channel

Polar codes have a natural secrecy property: the channels that are "bad" for the legitimate receiver are also "bad" for the eavesdropper (assuming the eavesdropper's channel is degraded with respect to the main channel). By placing the information bits on channels that are good for the receiver but bad for the eavesdropper, polar codes achieve the secrecy capacity of the wiretap channel (Mahdavifar and Vardy 2010).

Synthesis. Polar codes exploit the channel polarization phenomenon to construct explicit capacity-achieving codes with $O(n\log n)$ encoding and decoding complexity. The central insight is that the Arikan transform recursively splits channels into better and worse versions, and the Bhattacharyya parameter evolves multiplicatively for the good channel ($Z^{+}=Z^2$), ensuring exponential convergence to 0. The foundational reason polarization works is the conservation law $C(W^{-})+C(W^{+})=2C(W)$, which ensures that the total capacity is preserved even as individual channels polarise. This builds toward 46.08.01 where LDPC codes achieve capacity via iterative probabilistic decoding, and the bridge is that both families exploit the structure of the channel to concentrate reliability into information-bearing bits. The polarisation phenomenon generalises to non-binary alphabets, multi-user settings, and the wiretap channel, and appears again in 46.03.04 as the explicit realisation of the BSC and BEC capacity formulas, and putting these together polar codes represent the deterministic, algebraic complement to the probabilistic approach of modern iterative codes.

Full proof set Master

Proposition (Bhattacharyya recursion for the BEC). For the BEC with erasure probability $\alpha$, the Bhattacharyya parameter of the synthesized channels after one polarisation step satisfies $Z(W^{-})=2\alpha -{\alpha }^2$ and $Z(W^{+})={\alpha }^2$.

Proof. For the BEC, $Z(W)=\alpha$. The bad channel $W^{-}$ corresponds to decoding $U_1$ from $(Y_1,Y_2)$ where $X_1=U_1\oplus U_2$ and $X_2=U_2$, with $U_2$ unknown. The output reveals nothing about $U_1$ if either $Y_1$ or $Y_2$ is erased (since $U_1=X_1\oplus U_2=X_1\oplus X_2$ and both $X_1$ and $X_2$ are needed). The erasure probability of $W^{-}$ is $\mathrm{Pr}[Y_1=?\text{ or }{Y}_2=?]=1-(1-\alpha {)}^2=2\alpha -{\alpha }^2$.

The good channel $W^{+}$ corresponds to decoding $U_2$ from $(Y_1,Y_2,U_1)$. With $U_1$ known, the output reveals $U_2$ if both $Y_1$ and $Y_2$ are received (since $U_2=X_2=Y_2$ if $Y_2$ is not erased; if $Y_2$ is erased but $Y_1$ is not, $U_2=X_1\oplus U_1=Y_1\oplus U_1$). So $U_2$ is unknown only if both $Y_1$ and $Y_2$ are erased: ${\alpha }^2$. Hence $Z(W^{+})={\alpha }^2$. $\square$

Proposition (Encoding complexity). The polar encoding $\mathbf{x}=\mathbf{u}{G}_n$ for $n=2^m$ can be computed in $O(n\log n)$ operations.

Proof. Write $G_n=G_2^{\otimes m}$. Split $\mathbf{u}=({\mathbf{u}}_1,{\mathbf{u}}_2)$ with ${\mathbf{u}}_1,{\mathbf{u}}_2\in \{0,1{\}}^{n/2}$. Then:

$$\mathbf{x}=({\mathbf{u}}_1,{\mathbf{u}}_2)\left(\begin{array}{cc}{G}_{n/2}& 0\\ G_{n/2}& G_{n/2}\end{array}\right)=({\mathbf{u}}_1{G}_{n/2}+{\mathbf{u}}_2{G}_{n/2},{\mathbf{u}}_2{G}_{n/2}).$$

Let $\mathbf{a}={\mathbf{u}}_1{G}_{n/2}$ and $\mathbf{b}={\mathbf{u}}_2{G}_{n/2}$. Then $\mathbf{x}=(\mathbf{a}\oplus \mathbf{b},\mathbf{b})$.

By induction: $T(n)=2T(n/2)+n$, giving $T(n)=n{\log }_{2}n$. $\square$

Connections Master

• 46.03.01 — Discrete memoryless channels and mutual information; the capacity of BMS channels is the quantity that polar codes achieve.
• 46.03.04 — BSC and BEC capacity formulas; polar codes achieve these capacities with explicit constructions, particularly clean for the BEC.
• 46.08.01 — LDPC codes achieve capacity via iterative decoding; polar codes achieve it via deterministic construction, the two main approaches.
• 46.08.02 — Turbo codes achieve near-capacity via iterative decoding; polar codes achieve exact capacity with deterministic SC decoding.
• 46.03.03 — Fano's inequality provides the converse that polar codes' rates cannot exceed capacity.

Historical & philosophical context Master

Erdal Arikan introduced polar codes in his 2009 paper "Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels" (IEEE Trans. Info. Theory 55(7), pp. 3051-3073). Arikan was a student of Robert Gallager at MIT and had been thinking about the problem of explicit capacity-achieving codes since the 1980s. His insight was that the recursive application of a simple $2\times 2$ matrix could create a polarisation effect that separates reliable from unreliable bit channels.

Polar codes were the first explicit code family proven to achieve Shannon capacity on general BMS channels with low encoding and decoding complexity ($O(n\log n)$). Prior to Arikan's work, only random codes (which are not explicit) and LDPC codes (which were proven capacity-achieving only for the BEC by various authors in the 2000s) had this property.

In 2016, 3GPP adopted polar codes as the control channel coding scheme for 5G NR (New Radio), replacing turbo codes for the control channel. The choice was motivated by polar codes' superior block error rate performance at short block lengths (up to a few hundred bits), which is the regime relevant for control channels. The data channel continues to use LDPC codes, which perform better at longer block lengths.

The name "polar codes" reflects the polarisation phenomenon: the channel qualities polarise to the extremes (perfect or useless), just as physical systems polarise to extreme states under suitable conditions.

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},
}
@inproceedings{arikan-telatar2009,
  author    = {Ar{\i}kan, E. and Telatar, E.},
  title     = {On the Rate of Channel Polarization},
  booktitle = {Proceedings of the IEEE International Symposium on Information Theory},
  pages     = {1493--1495},
  year      = {2009},
}
@inproceedings{korada-sasoglu-urbanke2010,
  author    = {Korada, S. B. and Sasoglu, E. and Urbanke, R.},
  title     = {Polar Codes: Characterization of Exponent, Bounds, and Constructions},
  booktitle = {Proceedings of the IEEE International Symposium on Information Theory},
  pages     = {1484--1488},
  year      = {2010},
}
@article{tal-vardy2015,
  author  = {Tal, I. and Vardy, A.},
  title   = {List Decoding of Polar Codes},
  journal = {IEEE Transactions on Information Theory},
  volume  = {61},
  number  = {5},
  pages   = {2213--2226},
  year    = {2015},
}
@book{cover-thomas2006,
  author    = {Cover, T. M. and Thomas, J. A.},
  title     = {Elements of Information Theory},
  edition   = {2nd},
  publisher = {Wiley},
  year      = {2006},
}