Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity

Abstract

Let $W$ be a binary-input memoryless symmetric (BMS) channel with Shannon capacity $I(W)$ and fix any $\alpha >0$. We construct, for any sufficiently small $\delta >0$, binary linear codes of block length $O(1/{\delta }^{2+\alpha })$ and rate $I(W)-\delta$ that enable reliable communication on $W$ with quasi-linear time encoding and decoding. Shannon's noisy coding theorem established the \emph{existence} of such codes (without efficient constructions or decoding) with block length $O(1/{\delta }^2)$. This quadratic dependence on the gap $\delta$ to capacity is known to be best possible. Our result thus yields a constructive version of Shannon's theorem with near-optimal convergence to capacity as a function of the block length. This resolves a central theoretical challenge associated with the attainment of Shannon capacity. Previously such a result was only known for the erasure channel. Our codes are a variant of Arıkan's polar codes based on multiple carefully constructed local kernels, one for each intermediate channel that arises in the decoding. A crucial ingredient in the analysis is a strong converse of the noisy coding theorem when communicating using random linear codes on arbitrary BMS channels. Our converse theorem shows extreme unpredictability of even a single message bit for random coding at rates slightly above capacity.

References in corpus (2)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Polar-like Codes and Asymptotic Tradeoff among Block Length, Code Rate, and Error Probability

Cited by in corpus (1)

• Polar Codes' Simplicity, Random Codes' Durability