Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ERROR-CORRECTION ALGORITHMS:
Reports tagged with Error-correction algorithms:
TR13-050 | 1st April 2013
Venkatesan Guruswami, Patrick Xia

Polar Codes: Speed of polarization and polynomial gap to capacity

Revisions: 1

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 ... more >>>




ISSN 1433-8092 | Imprint