Polar Codes: Reaching Shannon Capacity

The problem Shannon left open

Claude Shannon's 1948 noisy-channel coding theorem proved that every communication channel has a maximum reliable rate, its capacity, and that codes exist that approach it arbitrarily closely with vanishing error probability. What Shannon's proof did not provide was a practical way to build such codes — it was an existence proof via random coding, not a construction. For over sixty years, engineers used codes (convolutional, turbo, LDPC) that got very close to capacity in practice but came with no proof of actually reaching it, and no simple explicit construction.

Arikan's kernel and channel polarization

Erdal Arikan's 2009 paper changed that with a deceptively simple idea: combine two independent copies of the same channel using a small 2x2 transform, then recursively combine 2 into 4, 4 into 8, and so on. The building block is:

F = [ 1  0 ]        G_N = F^(kron n),   N = 2^n
    [ 1  1 ]

n=1: combine 2 uses of the channel  -> 2 synthetic channels
n=2: combine 4 uses of the channel  -> 4 synthetic channels
...
As N grows, the synthetic channel capacities spread apart:
a fraction ~C of them approach capacity 1 (perfectly reliable)
the rest approach capacity 0 (useless) — very few stay in between

This spreading-apart is channel polarization, and it is the whole trick: as N grows large, the fraction of synthetic channels that become almost noise-free approaches exactly the original channel's Shannon capacity C. Nothing about the underlying physical channel changed — the polarization is purely a property of how the recursive combining interacts with the channel's statistics.

Freezing the bad channels

The construction step of a polar code is: rank the N synthetic channels by reliability, put actual information bits on the roughly N·C most reliable ones, and freeze the rest — fix them to a known value, typically zero, agreed in advance by transmitter and receiver. Because the frozen positions carry no information but are still known to the decoder, they act as built-in redundancy exactly where the channel is weakest, and information is sent only where it can survive. Computing exactly which channels are the reliable ones (density evolution, or the simpler Gaussian approximation and Bhattacharyya-parameter bounds used in practice) is itself a well-studied and efficient offline computation.

Successive cancellation decoding

The matching decoder, successive cancellation (SC), exploits the same recursive structure: it decodes bits one at a time in a fixed order, and each decision conditions on all previously decoded bits, mirroring exactly how the encoder combined the channels. SC decoding has O(N log N) complexity, matching the O(N log N) encoding cost of the recursive kernel — but by itself SC decoding converges to capacity only as N grows very large, and at practical block lengths its raw error performance trails established codes. The fix widely used in deployment is SC-List decoding: track several candidate decoding paths in parallel instead of one, and use an appended CRC to pick the surviving path that passes the check. This combination is what made polar codes competitive in practice, not just in the asymptotic proof.

From theorem to standard

In 2016, 3GPP selected polar codes for the control channels of 5G New Radio, making them the first capacity-achieving code with an explicit construction and a formal proof to see deployment in a global communications standard — a remarkably fast trip from a theory paper to billions of phones, and a direct payoff of the constructive, recursive design that made both the encoder and the SC-List decoder efficient enough to implement in silicon.

Frequently asked questions

Try it live

Everything above runs in your browser — open Polar Codes and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.