Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity

DOI10.1145/3357713.3384323MaRDI QIDQ5144941zbMATH OpenOpenAlexFDO

Authors Andrii Riazanov, Min Ye, Venkatesan Guruswami

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.03858

zbMATH Keywords

capacity-achieving codesinformation theorypolar codes

Mathematics Subject Classification ID

Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24) Channel models (including quantum) in information and communication theory (94A40) Linear codes (general theory) (94B05)

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/delt{a}^{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/delt{a}^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{i}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.

Recommendations

• Arıkan Meets Shannon: Polar Codes With Near-Optimal Convergence to Channel Capacity
• Capacity-Achieving Rate-Compatible Polar Codes
• Capacity-Achieving Polar Codes for Arbitrarily Permuted Parallel Channels
• Polar Codes for the m-User Multiple Access Channel
• Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels
• Polar Codes: Speed of Polarization and Polynomial Gap to Capacity
• Polar Coding for Non-Stationary Channels
• Polar Codes for $q$-Ary Channels, $q=2^{r}$
• Performance Bounds of Concatenated Polar Coding Schemes

Cited in

(6)

• Polar codes with higher-order memory
• The polarization of hybrid multi-kernel polar codes
• An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets
• Polar codes with exponentially small error at finite block length
• Polar codes
• Reed-Muller Codes

This page was built for publication: Arikan meets Shannon: polar codes with near-optimal convergence to channel capacity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144941)