Information Theory
Polar Codes: Arikan's Construction
Цели урока
- Explain channel polarization through the recursive G_N transform
- Describe SC and SCL decoding and their comparative characteristics
- Compare polar codes to LDPC on key performance metrics
- Know polar code applications in 5G NR and their limitations
Предварительные знания
- Channel Capacity
- Error-Correcting Codes
How does recursive XOR in a finite number of steps create channels that are part perfect and part useless? Why is this the first explicit construction achieving C?
- 5G NR PDCCH: polar codes with SCL-8 and CRC-11 - in every 5G smartphone since 2019
- SCL decoding with L=32 outperforms LTE turbo codes by 0.5-1 dB at short blocks
- FlexPolar (Huawei, 2020): hardware accelerator, 1 Gbps on 7nm
- Neural decoders for polar codes: new class of methods at the intersection of IT and DL
60 Years of Search: from Shannon to Arikan
Shannon (1948) proved good codes exist but gave no construction. Turbo codes (Berrou 1993) practically approached C by randomness. LDPC (Gallager 1960, MacKay-Neal 1995): close but no theoretical guarantee for finite N. Erdal Arikan (Bilkent University, 2008): 'Channel Polarization'. Key insight: recursive transform polarizes N identical channels into N/2 better and N/2 worse. At n recursions: N=2^n channels with polarization approaching perfection. 2016: 3GPP selects polar codes for 5G. Arikan receives IEEE Hamming Medal in 2018.
Channel Polarization: Arikan's Key Idea
2008. Erdal Arikan publishes 'Channel Polarization: A Method for Constructing Capacity-Achieving Codes'. For 60 years after Shannon no one had found an explicit construction that provably achieves C. Arikan found one. In 2016, 3GPP adopted polar codes for 5G NR control channels. A simple recursive idea - and it waited 60 years.
BEC polarization is particularly clear: good channels get Z_i -> 0 (perfect), bad ones -> 1 (fully erased). For AWGN polarization works analogously but asymptotically slower.
What happens to the virtual channels under polar transform as N grows to infinity?
Arikan's polarization theorem: as N grows, virtual channels polarize - the fraction with I(W_N^(i)) > 1-delta approaches I(W). Intermediate channels disappear. This allows exactly k = NR information positions to be chosen and capacity to be achieved.
SC and SCL Decoding
Successive Cancellation (SC) decoding is simple and elegant: bits are decoded sequentially, each using all previous decisions. Complexity O(N log N) - better than many codes. But at finite N the performance is worse than LDPC. SCL (Successive Cancellation List) with CRC fixed this and brought polar codes into 5G.
Polar Codes in 5G NR
3GPP Release 15 (2018): polar codes for PDCCH (physical downlink control channel) and PUCCH. Parameters: blocks 32-512 bits, SCL with L=8, CRC length 11. Comparison with LTE turbo codes: at 100-bit block and BLER=1%, polar codes win by 0.5-1 dB in SNR. At larger blocks the advantage decreases - hence LDPC was kept for data channels.
| Property | Polar Codes | LDPC Codes |
|---|---|---|
| Achieving C | Theoretically at N->inf | Theoretically with optimal degree dist. |
| Block length | Short (32-1K) | Long (1K-64K) |
| Decoding | SC: sequential | BP: parallel |
| 5G NR use | Control (PDCCH/PUCCH) | Data (PDSCH/PUSCH) |
| Latency | Higher (serial) | Lower (parallel) |
Why does SCL decoding with CRC outperform SC?
SC makes hard decisions at each step and cannot correct them. SCL keeps L best paths - when one path is wrong the correct one stays in the list. CRC selects at the end. At L=32 performance is close to maximum likelihood decoding.
Polar vs. LDPC: the 5G Engineering Choice
5G NR uses two code families: polar for control channels (short blocks), LDPC for data (long blocks). This reflects theoretical and practical tradeoffs of each class.
Neural decoders for polar codes (2017-2024): unrolling ISTA-like iterations into a neural network - LISTA applied to decoding. At block length 64: a neural decoder achieves 0.3 dB from ML at complexity O(N^2) instead of O(2^k) for ML. TurboAE (2019): a neural codec competitive with LDPC at short blocks.
Why does 5G NR use polar codes for control channels and LDPC for data?
Control channels: 32-512 bit blocks, latency-critical -> SCL-polar. Data: 1K-64K bit blocks, throughput-critical -> LDPC with parallel BP. The polar scaling exponent (~3.63) is worse than LDPC (~2) at large N, but at small N the difference is small.
Connection to Other Topics
Polar codes use: the polarization theorem (C achieved as N grows), SCL decoding (beam search with L=2^k hypotheses), and CRC (additional code for path selection among L candidates). Connection to LDPC: both in 5G, for different block lengths. Connection to deep learning: neural decoders apply seq2seq models to decoding. The scaling exponent of polar codes (~3.63) is worse than turbo codes (~2) - an active area of improvement.
- Channel Capacity — Polar codes are the first deterministic construction proven to achieve symmetric capacity
- LDPC Codes: Gallager's Construction — Complementary capacity-approaching family used for long block lengths in 5G
- Error-Correcting Codes — Polar codes inherit and extend the classical algebraic coding framework
Итоги
- Polar transform G_N recursively creates N=2^n virtual channels from N identical ones
- Polarization theorem: fraction of good channels -> I(W), bad -> 1-I(W) as N grows
- SC: O(N log N) decoding; SCL with L paths and CRC - close to ML decoding
- 5G NR: polar for control (short), LDPC for data (long)
Вопросы для размышления
- Why did polar codes take more than 60 years to discover despite the simplicity of the construction?
- How does SCL decoding balance computational complexity against approaching ML?
- What limits polar codes at practical block lengths compared to LDPC?