Log-logarithmic Time Pruned Polar Coding

Abstract

A pruned variant of polar coding is proposed for binary erasure channels. For sufficiently small $\epsilon >0$, we construct a series of capacity achieving codes with block length $N={\epsilon }^{-5}$, code rate $R=\text{Capacity}-\epsilon$, error probability $P=\epsilon$, and encoding and decoding time complexity $\text{bC}=O(\log \left|\log \epsilon \right|)$ per information bit. The given per-bit complexity $\text{bC}$ is log-logarithmic in $N$, in $\text{Capacity}-R$, and in $P$; no known family of codes possesses this property. It is also the second lowest $\text{bC}$ after repeat-accumulate codes and their variants. While random codes and classical polar codes are the only two families of capacity-achieving codes whose $N$, $R$, $P$, and $\text{bC}$ were written down as explicit functions, our construction gives the third family. Then we generalize the result to: Fix a prime $q$ and fix a $q$-ary-input discrete symmetric memoryless channel. For sufficiently small $\epsilon >0$, we construct a series of capacity achieving codes with block length $N={\epsilon }^{-O(1)}$, code rate $R=\text{Capacity}-\epsilon$, error probability $P=\epsilon$, and encoding and decoding time complexity $\text{bC}=O(\log \left|\log \epsilon \right|)$ per information bit. The later construction gives the fastest family of capacity-achieving codes to date on those channels.

arXiv comment13 pages, 13 figures; we extend arXiv:1812.08106 and remove "BEC" from title

References in corpus (13)

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
• Fast Polar Decoders: Algorithm and Implementation
• Capacity-achieving ensembles for the binary erasure channel with bounded complexity
• Finite-Length Scaling of Polar Codes
• Capacity-Achieving Ensembles of Accumulate-Repeat-Accumulate Codes for the Erasure Channel with Bounded Complexity
• Relaxed Polar Codes
• Polar Codes' Simplicity, Random Codes' Durability
• Flexible Length Polar Codes through Graph Based Augmentation
• Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices
• Scaling Exponent and Moderate Deviations Asymptotics of Polar Codes for the AWGN Channel
• Polar Codes with exponentially small error at finite block length
• Polar Code Moderate Deviation: Recovering the Scaling Exponent
• Polar-like Codes and Asymptotic Tradeoff among Block Length, Code Rate, and Error Probability

Cited by in corpus (1)

• Complexity and Second Moment of the Mathematical Theory of Communication