Polar Codes: Speed of Polarization and Polynomial Gap to Capacity

We prove that, for all binary-input symmetric memory less channels, polar codes enable reliable communication at rates within ε > 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. We give an elementary proof of the capacity achieving property of polar codes that does not rely on the martingale convergence theorem. As a result, we are able to explicitly show that polar codes can have block length (and consequently also encoding and decoding complexity) that is bounded by a polynomial in the gap to capacity. The generator matrix of such polar codes can be constructed in polynomial time using merging of channel output symbols to reduce the alphabet size of the channels seen at the decoder.