Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR13-050 | 15th October 2013 23:01

Polar Codes: Speed of polarization and polynomial gap to capacity

RSS-Feed




Revision #1
Authors: Venkatesan Guruswami, Patrick Xia
Accepted on: 15th October 2013 23:01
Downloads: 3594
Keywords: 


Abstract:

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. 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/\epsilon)$ 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 $\approx \epsilon$ 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/\epsilon$. The generator matrix of such polar codes can be constructed in polynomial time by algorithmically computing an adequate approximation of the polarization process.



Changes to previous version:

Simpler conditional entropy based proof for effective bounds on speed of polarization, plus some editorial changes to presentation.


Paper:

TR13-050 | 1st April 2013 17:29

Polar Codes: Speed of polarization and polynomial gap to capacity


Abstract:

We prove that, for all binary-input symmetric memoryless channels, polar codes enable reliable communication at rates within $\epsilon > 0$ of the Shannon capacity with a block length, construction complexity, and decoding complexity all bounded by a *polynomial* in $1/\epsilon$. 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.



ISSN 1433-8092 | Imprint