Polar Code

Polar Code
Name	Polar Code
Inventor	Erdal Arıkan
Year	2008
Field	Information theory
Related	Channel coding, Error correction, Shannon's channel capacity

Polar Code

Polar Code is a class of error-correcting codes introduced in 2008 that provably achieve the symmetric capacity of binary-input discrete memoryless channels. Developed by Erdal Arıkan within the context of information theory, Polar Code exploited a channel transformation and recursive construction to produce channels that become either virtually noiseless or completely noisy, a phenomenon called channel polarization. Subsequent work connected Polar Code to practical communication systems adopted by standards bodies and research in coding theory, leading to widespread study across IEEE, 3GPP, and academic conferences such as International Symposium on Information Theory.

Introduction

Polar Code was proposed by Erdal Arıkan as a constructive method to achieve the symmetric capacity predicted by Claude Shannon for binary-input channels. The concept builds on tools from probability theory, martingale theory, and Fourier analysis on groups and links to earlier developments in Reed–Solomon, Bose–Chaudhuri–Hocquenghem, and Low-density parity-check code research. Early demonstrations spurred interest at institutions such as Bell Labs, MIT, Stanford University, and companies like Huawei and Qualcomm, which investigated Polar Code for standards including 5G NR and satellite links. The invention earned attention comparable to milestones such as the introduction of Turbo codes and LDPC codes.

Construction and Polarization Principle

Polar Code construction uses a recursive channel combining and splitting transform based on a kernel matrix; the canonical kernel is the 2×2 matrix used in Arıkan's original construction. The method uses the Kronecker power of the kernel to map N independent uses of a binary-input discrete memoryless channel to N synthesized channels with polarized reliabilities. This process invokes concepts from binary expansion and the Walsh–Hadamard transform and relates to algebraic structures studied in Galois fields and finite group theory. Proofs of polarization rely on inequalities and concentration results from martingale convergence theorems and measure concentration results akin to those used in the analysis of random matrices and branching processes. Design choices for frozen sets and reliability ordering connect with evaluation methods developed in teams at University of Cambridge, École Polytechnique Fédérale de Lausanne, and University of Illinois Urbana–Champaign.

Encoding and Decoding Algorithms

Encoding in Polar Code is linear and implemented as multiplication by the generator matrix formed from the kernel's Kronecker powers, enabling implementation with butterfly networks similar to those used in Fast Fourier Transform hardware. Decoding algorithms include successive cancellation decoding introduced by Erdal Arıkan, successive cancellation list decoding developed by researchers at Huawei and Ecole Polytechnique, and belief propagation inspired by techniques from Gallager and Richardson and Urbanke. Successive cancellation list (SCL) decoding often uses cyclic redundancy check (CRC) concatenation as introduced by practitioners at Huawei to improve performance and selection of codewords, while successive cancellation stack and sphere decoding variants borrow algorithmic ideas from Dijkstra-style search and Viterbi algorithm optimization. Hardware implementations leverage designs from ARM Holdings, Xilinx, and Intel for accelerators in base stations and mobile devices.

Performance and Capacity-Achieving Properties

Polar Code achieves the symmetric capacity of binary-input discrete memoryless channels as proved by Arıkan, connecting to the landmark result of Claude Shannon. Finite-length behavior is characterized by scaling laws and error exponents analyzed using techniques from large deviation theory and finite-blocklength information theory advanced by researchers at Princeton University, ETH Zurich, and University of California, Berkeley. Practical performance under SCL decoding with CRC approaches those of concatenated systems and Turbo codes for moderate block lengths; however, at short block lengths, Reed–Muller codes and specialized LDPC constructions sometimes outperform Polar Code without list decoding. Trade-offs between complexity and error-floor behavior have been explored in collaborations involving Nokia Bell Labs and Samsung Research.

Variants and Extensions

Researchers have proposed many extensions: non-binary kernels generalize the original binary construction using ideas from Reed–Solomon and Algebraic geometry codes, multi-kernel constructions mix different kernel sizes, and spatially coupled polar-like constructions draw from work on spatial coupling used in LDPC theory by teams at EPFL and University of Cambridge. Universal and rate-compatible polar constructions target standards work in 3GPP and satellite communications studied at European Space Agency and NASA laboratories. List decoding improvements, CRC-aided schemes, and concatenations with convolutional and cyclic codes integrate classical results from Peterson and Weldon and modern list-decoding theory developed at Microsoft Research and Google labs.

Applications and Implementation Issues

Polar Code has been adopted in industries and standards bodies, most notably selected for control-channel coding in 3GPP 5G NR specifications, prompting implementation studies by Qualcomm, Ericsson, and Huawei. Other application areas include deep-space communications under programs at NASA, satellite systems investigated by European Space Agency, and storage systems explored by teams at Western Digital and Seagate Technology. Implementation challenges involve decoding latency, memory footprint, and throughput constraints addressed by ASIC and FPGA implementations from Xilinx, Altera (Intel), and custom silicon groups at Samsung and Apple. Research in quantum error correction and polar-inspired codes links to efforts at Perimeter Institute and IBM Research exploring fault-tolerant computation.

Category:Error-correcting codes