Log-logarithmic Time Pruned Polar Coding
share
A pruned variant of polar coding is proposed for binary erasure channels. For sufficiently small ε>0, we construct a series of capacity achieving codes with block length N=ε^-5, code rate R=Capacity-ε, error probability P=ε, and encoding and decoding time complexity bC=O(|ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity-R, and in P; no known family of codes possesses this property. It is also the second lowest 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 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 ε>0, we construct a series of capacity achieving codes with block length N=ε^-O(1), code rate R=Capacity-ε, error probability P=ε, and encoding and decoding time complexity bC=O(|ε|) per information bit. The later construction gives the fastest family of capacity-achieving codes to date on those channels.
READ FULL TEXT