Polar Codes: Speed of polarization and polynomial gap to capacity

摘要

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within 0">0 of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in 1 . Polar coding gives the *first known explicit construction* with rigorous proofs of all these properties; previous constructions were not known to achieve capacity with less than exp(1) decoding complexity except for erasure channels.We establish the capacity-achieving property of polar codes via a direct analysis of the underlying martingale of conditional entropies, without relying on the martingale convergence theorem. This step gives rough polarization (noise levels for the ``good" channels), which can then be adequately amplified by tracking the decay of the channel Bhattacharyya parameters. Our effective bounds imply that polar codes can have block length (and encoding/decoding complexity) bounded by a polynomial in 1 . The generator matrix of such polar codes can be constructed in polynomial time by algorithmically computing an adequate approximation of the polarization process