Polar Codes' Simplicity, Random Codes' Durability

Abstract

Over any discrete memoryless channel, we build codes such that: for one, their block error probabilities and code rates scale like random codes'; and for two, their encoding and decoding complexities scale like polar codes'. Quantitatively, for any constants $\pi ,\rho >0$ such that $\pi +2\rho <1$, we construct a sequence of error correction codes with block length $N$ approaching infinity, block error probability $\exp (-N^{\pi })$, code rate $N^{-\rho }$ less than the Shannon capacity, and encoding and decoding complexity $O(N\log N)$ per code block. The putative codes take uniform $\varsigma$-ary messages for sender's choice of prime $\varsigma$. The putative codes are optimal in the following manner: Should $\pi +2\rho >1$, no such codes exist for generic channels regardless of alphabet and complexity.

arXiv comment55 pages, 8 figures, 2 tables

References in corpus (21)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
• Achieving the Secrecy Capacity of Wiretap Channels Using Polar Codes
• Source Polarization
• Finite-Length Scaling of Polar Codes
• Rate-Dependent Analysis of the Asymptotic Behavior of Channel Polarization
• Polar Codes For Broadcast Channels
• Exact Random Coding Secrecy Exponents for the Wiretap Channel
• Achieving the Capacity of any DMC using only Polar Codes
• Relaxed Polar Codes
• Ergodic Theory Meets Polarization. I: An Ergodic Theory for Binary Operations
• Ergodic Theory Meets Polarization. II: A Foundation of Polarization Theory
• Properties and Construction of Polar Codes
• Scaling Exponent and Moderate Deviations Asymptotics of Polar Codes for the AWGN Channel
• On the Scaling Exponent of Polar Codes for Binary-Input Energy-Harvesting Channels
• Polar Coding for Processes with Memory
• On the Capacity of Channels with Deletions and States
• Polar-like Codes and Asymptotic Tradeoff among Block Length, Code Rate, and Error Probability
• Explicit Polar Codes with Small Scaling Exponent
• Arıkan meets Shannon: Polar codes with near-optimal convergence to channel capacity
• Reed-Muller codes polarize

Cited by in corpus (5)

• Adjacent-Bits-Swapped Polar codes: A new code construction to speed up polarization
• Log-logarithmic Time Pruned Polar Coding
• Fast Search Method for Large Polarization Kernels
• ABS+ Polar Codes: Exploiting More Linear Transforms on Adjacent Bits
• Complexity and Second Moment of the Mathematical Theory of Communication