Log-Logarithmic Time Pruned Polar Coding

A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small varepsilon >{0} , we construct a series of capacity achieving codes with block length text {N}=varepsilon {-{4.9}} , code rate text {R}=text {Capacity}-text {O}(varepsilon) , block error probability text {P}=varepsilon , and encoding and decoding time complexity mathop {mathrm {bC}} =text {O}(log lvert log varepsilon rvert) per information bit. The given per-bit complexity mathop {mathrm {bC}} is log-logarithmic in N, in text {Capacity}-text {R} , and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small varepsilon >0 , we construct a series of error correction codes with block length text {N}=varepsilon {-text {constant}} , code rate text {R}=text {Capacity}-text {O}(varepsilon) , block error probability text {P}=varepsilon , and encoding and decoding time complexity mathop {mathrm {bC}} =text {O}(log lvert log varepsilon rvert) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.