Make your paper interactiveCreate

Text from the interactive explanation

Polar Codes and Their Quantum-Domain Counterparts

Zunaira Babar, Zeynep B. Kaykac Egilmez, Luping Xiang, Daryus Chandra, Robert G. Maunder, Soon Xin Ng, Lajos Hanzo

Original paper

An interactive reading of a survey on polar codes · IEEE Communications Surveys & Tutorials, 2019

Can a channel that loses half of everything you send be split into some lanes that lose nothing and others that lose everything — without cheating the laws of information?

Claude Shannon proved in 1948 that near-perfect communication is possible, but gave no recipe. Erdal Arıkan’s recipe is a single XOR gate, repeated. Within a decade it was protecting 5G control signals, and the same circuit, rebuilt from quantum gates, can protect qubits.

Exact calculation for an erasure channel (paper Section II, Eqs. 10–16). Every bit picks the worse or better branch with equal odds. Start the journey ↓

A channel that forgets

Picture a stream of bits — 0s and 1s — crossing a channel that sometimes simply drops one. The receiver can tell a bit went missing (it sees a ?) but not what it was. This is a binary erasure channel , and the fraction it loses is called ε (epsilon).

How much information can it carry? On average, each use delivers at most 1 − ε bits. That number is the channel’s capacity . Shannon proved something astonishing: by adding carefully designed redundancy, you can send at any rate below capacity with virtually no errors. He just didn’t say how.

For seven decades researchers chased that recipe along two roads. The algebraic road — Hamming, Reed–Muller, BCH and Reed–Solomon codes — made codewords as different from each other as possible. The probabilistic road, inspired by Shannon’s random codes, led to convolutional, turbo and LDPC codes that crept extremely close to the limit.

Polar codes, introduced by Arıkan in 2009, were the first codes proven to reach capacity, as codes grow longer, with low-complexity encoding and decoding, built not from randomness but from one tiny repeated structure. Here it is.

One XOR gate

Take two message bits, u₁ and u₂ . Instead of sending them directly, send x₁ = u₁ ⊕ u₂ (XOR: 1 when the two bits differ) and x₂ = u₂ . Both travel through the same forgetful channel and arrive as y₁ and y₂ . The receiver decodes in order: first u₁, then u₂, and by then it already knows u₁.

Predict: with this one gate, which bit is now safer than before?

Click a received bit to erase or restore it. Click u₁ or u₂ to change the message.

u₁ can only be rebuilt if both y₁ and y₂ arrive (û₁ = y₁ ⊕ y₂). u₂ survives if either arrives: directly from y₂, or as y₁ ⊕ u₁. One lane got worse — call it W⁻ — and one got better, W⁺ . With ε = 0.5 they succeed 25% and 75% of the time. Add them: exactly the 0.5 + 0.5 of the two original channels. Nothing was created or destroyed; capacity was moved.

Do it again: the Matthew effect

Now pair two of the worse lanes with another XOR, and two of the better lanes with another. The bad get worse and the good get better — the paper calls this the Matthew effect , after “to everyone who has, more will be given.” Repeat n times and you have N = 2ⁿ lanes.

Two things hold at every layer. The average capacity never changes — it stays 1 − ε. And the lanes keep drifting toward the two extremes. Arıkan proved that as N grows without limit, the share of almost-perfect lanes approaches exactly 1 − ε: Shannon’s capacity.

But notice how slowly. With ε = 0.5 and 1,024 lanes, 37% are above 0.99 and 37% below 0.01 — a quarter are still in between. The engine at the top is exactly this calculation drawn as a tree. That unfinished polarization at practical lengths is why decoders will need extra help later.

For an erasure channel the capacities follow a simple recursion (paper Eq. 16): a lane with capacity I splits into I² (worse) and 2I − I² (better). Their sum is always 2I. For other channels no exact recursion exists, so engineers estimate the lanes — see chapter 7.

Freeze the useless lanes

Here is the whole idea of a polar code: put your message on the best lanes, and on the worst lanes send bits the receiver already knows — usually zeros. These are called frozen bits .

Your turn. There are 8 lanes (ε = 0.5) and a 4-bit message. Pick which lanes carry it.

The encoder is the same butterfly of XOR gates every time, written x = u·GN. In the paper’s example the message 1 0 0 1 rides on lanes 4, 6, 7 and 8, lanes 1, 2, 3 and 5 are frozen, and the codeword that goes on air is 0 0 0 0 1 1 1 1 . Building it takes about N log₂ N XORs — cheap even for thousands of lanes.

Reed–Muller codes use the very same GN but keep the rows with the most 1s, which maximizes the distance between codewords. Polar codes keep the rows of the most reliable lanes, which is what lets them approach capacity. For 8 lanes the two choices coincide — this example is the (8, 4) Reed–Muller code — but they part ways as N grows.

Change the rate by turning a dial

Want to send more? Freeze fewer lanes. The encoder and decoder stay the same, and the lanes picked at a high rate always include those picked at a lower one. Below, 1,024 lanes are ranked by reliability and lit in order.

Undoing it, one bit at a time

Real receivers don’t get clean bits. For each one they get a confidence score called a log-likelihood ratio (LLR) : its sign is the best guess (+ means 0, − means 1) and its size says how sure.

Successive cancellation (SC) decoding runs the encoder’s circuit backwards with two simple rules. f combines two scores into a score for their XOR — as unsure as the less certain one. g uses a bit that’s already been decided to merge two scores into a stronger one. Decided bits then flow back to the right to help the next lanes.

Watch the paper’s own worked example: the codeword 0 0 0 0 1 1 1 1 arrives as eight noisy scores.

f scores flowing left g scores using a decided bit bits flowing right F frozen lane

SC needs only about N log₂ N simple operations, and the paper notes it provably reaches capacity as N grows. Its weakness is order: lane 8 can’t start until lanes 1 to 7 are done. That strict sequence makes SC slow to run in hardware — a major thread of research the survey maps out.

View the decoder as a tree. Branches whose lanes are all frozen (“rate-0”) need no computing at all, and branches whose lanes all carry data (“rate-1”) can be decided in one go. This simplified SC decoder gives identical results; the work cited in the survey reports 20–50% fewer of the costly score combinations and 75–95% lower latency.

When one guess goes wrong

SC never takes back a decision. If an early data lane is decided wrongly, every later lane inherits the mistake. Successive cancellation list (SCL) decoding hedges its bets: at every data lane it keeps both possibilities, scores each path (a penalty of |LLR| whenever a choice disagrees with its score) and keeps only the L best.

Investigate: change the noise on the eight received scores. Can you find noise that fools SC but not the list?

Gold: winning path · green: kept · red ×: pruned. Numbers are path penalties.

Even when a list decoder picks wrongly, the right answer is often sitting in its list with a slightly worse score. So engineers attach a short checksum — a cyclic redundancy check (CRC) — to the message, and the decoder chooses the best path that passes it. This CRC-aided list decoder brought polar codes level with the reigning turbo and LDPC codes, at the price of a few message bits spent on the checksum.

Cousins in the survey: the SC-flip decoder re-runs SC, flipping one shaky decision at a time until the CRC passes; the stack decoder explores the most promising path first, keeping candidates of different lengths in a sorted stack.

The decoder race

Time for a real experiment. Below, your browser builds a 256-lane, rate-½ polar code, chooses its frozen lanes with the Gaussian-approximation method from the survey’s design chapter, then sends thousands of random messages through simulated radio noise and decodes them with each decoder. The block error rate is the share of messages that come out with any mistake. Eb/N0 is signal strength per message bit relative to noise, in decibels: further right means a cleaner channel.

Live simulation of a smaller code than the paper’s. Faint points have few errors so far; they firm up as blocks accumulate.

What the paper’s simulations found

For a 1,024-lane, rate-½ code using the 5G frozen-lane sequence, with QPSK over a noisy (AWGN) channel:

Longer lists help, with diminishing returns: little gain beyond L = 8 , and L = 32 comes close to the best possible (maximum-likelihood) decoding.

SC performs worst; the CRC-aided list decoder (L = 8, 11-bit CRC) performs best; belief propagation, soft cancellation, list and stack decoders fall in between.

A stack decoder holding 128 candidates matched the list decoder with L = 8.

For choosing frozen lanes, Monte Carlo and Gaussian-approximation designs did equally well and approached the 3GPP 5G sequence when designed at 2 dB; the simpler erasure-channel approximation was worse.

Better decoding is never free. The survey sums up the trade-offs:

Two kinds of noise

A quantum bit, or qubit , can hold a blend (a superposition) of 0 and 1. Noise can disturb it in two ways: a bit-flip swaps 0 and 1, and a phase-flip flips the sign between the two parts of the blend; a third error does both. In the standard “depolarizing” noise model, each happens with probability p/3.

The quantum version of XOR is the CNOT gate. Look at the same gate through “phase glasses” (the Hadamard basis) and its control and target swap places. So one circuit polarizes bit-flips one way and phase-flips the opposite way.

Now polarize in two directions at once. Each dot below is one qubit lane, placed by how reliable it is against bit-flips (→) and phase-flips (↑). Watch them split layer by layer and stream toward the corners.

top-right · good for both carries quantum data

right edge · good against bit-flips only frozen as |+⟩ or |−⟩

top edge · good against phase-flips only frozen as |0⟩ or |1⟩

elsewhere · bad for both filled with ebits

Estimate using the paper’s simplification: depolarizing noise treated as two independent bit-flip channels of probability 2p/3, with lane reliabilities from the erasure-channel (Bhattacharyya) approximation. “Good” = estimated reliability ≥ 0.9.

The four kinds of lanes get four jobs. Lanes good for both carry the precious quantum data. Lanes good against only one kind of error are frozen in a known state of the other kind. Lanes bad for both are filled with one half of an entangled pair (an “ebit”) whose partner was delivered to the receiver in advance — so quantum polar codes belong to the family of entanglement-assisted codes.

Decoding never looks at the data directly, which would destroy it. Measuring only the frozen qubits reveals a syndrome : which errors struck, not what the message was. Two ordinary classical polar decoders — one using GN, one using its transpose — estimate the bit-flip and phase-flip parts, and together they name the correction:

After the paper’s Table XI. The survey notes this syndrome-based approach is the most direct reuse of classical polar decoders, though it may not reach capacity for every quantum channel.

What it changes

Back to the opening question. Can a noisy channel be split into perfect lanes and useless ones? Yes — not by magic but by bookkeeping. The total capacity never changes; one XOR gate keeps moving it around until the message can ride where almost nothing is lost. Push the engine further:

Shannon’s promise finally had a recipe — and a structured one, overturning the belief that capacity needed randomness. Within a decade of their invention, polar codes were written into the 5G New Radio standard for control channels of enhanced mobile broadband and ultra-reliable low-latency services, and for the broadcast channel. The survey closes with the questions still open:

Faster decoders

SC-style decoding is serial; turbo and LDPC decoders run fully in parallel. Only belief propagation parallelizes fully, at a cost. The paper names decoding latency as a major reason polar codes are not used for 5G data channels.

Universal codes

The best frozen lanes depend on the channel. Universal polar codes that work well everywhere exist, but need longer codes.

Bigger building blocks

Kernels larger than 2×2, or over non-binary alphabets, polarize faster in theory but are harder to encode and decode.

Stochastic decoders

Decoders built from random bit-streams have helped LDPC and turbo codes tolerate timing faults and cut latency; for polar codes they are barely explored.

Quantum polar codes

The same encoder, built from CNOT gates, polarizes both kinds of quantum error — a direct bridge from classical coding to protecting fragile qubits.

Source

Zunaira Babar, Zeynep B. Kaykac Egilmez, Luping Xiang, Daryus Chandra, Robert G. Maunder, Soon Xin Ng and Lajos Hanzo. “Polar Codes and Their Quantum-Domain Counterparts.” IEEE Communications Surveys & Tutorials, 2019. DOI: 10.1109/COMST.2019.2937923.

This experience follows the accepted manuscript hosted by the University of Southampton (PDF). Paper © 2019 IEEE.

All visuals here are original and computed live from the equations in the paper; no figures are reproduced. The polarization engine, lane bars, lane-choice score and rate grid are exact calculations for an erasure channel. The 8-lane decoding walkthrough uses the paper’s worked example (Figs. 13, 15 and 18). The decoder race is a live simulation of a smaller code than the one in the paper’s figures. The quantum map is an estimate based on the paper’s two-independent-channel simplification.

Topics in this iPaper

Engineering
Polar codes have already found their way into the 5G New Radio (NR) for the control channels

Section I (Introduction), page 3

Computer science
an SCL decoder considers a list of alternative values for the information bits

Section IV-C (Successive Cancellation List Decoders), page 14

Mathematics
Shannon quantified the capacity limit and proved the existence of ‘capacity-achieving’ codes

Section I (Introduction), page 2

Physics
Environmental decoherence is a major source of noise in quantum systems.

Section VI (Quantum-to-Classical Isomorphism), page 25

polar codes
Arikan’s polar codes are capable of approaching Shannon’s capacity at a low encoding and decoding complexity

Abstract, page 1

channel polarization
Polar codes rely on the phenomenon of channel polarization, which is the key contributor towards approaching Shannon’s capacity.

Section II (The Philosophy of Channel Polarization), page 3

channel coding
Keywords—channel coding, channel polarization, capacity, polar codes, quantum error correction.

Keywords, page 1

successive cancellation list decoding
Tal and Vardy proposed an LR-based SCL decoder

Section IV-C (Successive Cancellation List Decoders), page 14

quantum error correction
make it challenging to design Quantum Error Correction Codes (QECCs)

Section VI (Quantum-to-Classical Isomorphism), page 25

Polar Codes and Their Quantum-Domain Counterparts — Interactive explanation | iPaper.ai