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.

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