Log-logarithmic Time Pruned Polar Coding on Binary Erasure Channels

Abstract

A pruned variant of polar coding is reinvented for all binary erasure channels. For small $\epsilon >0$, we construct codes with block length ${\epsilon }^{-5}$, code rate $\text{Capacity}-\epsilon$, error probability $\epsilon$, and encoding and decoding time complexity $O(N\log |\log \epsilon |)$ per block, equivalently $O(\log |\log \epsilon |)$ per information bit (Propositions 5 to 8). This result also follows if one applies systematic polar coding [Arıkan 10.1109/LCOMM.2011.061611.110862] with simplified successive cancelation decoding [Alamdar-Yazdi-Kschischang 10.1109/LCOMM.2011.101811.111480], and then analyzes the performance using [Guruswami-Xia arXiv:1304.4321] or [Mondelli-Hassani-Urbanke arXiv:1501.02444].

16 pages, 144 figures

References in corpus (2)

• Flexible Length Polar Codes through Graph Based Augmentation
• A Packing Lemma for Polar Codes