Polar Codes with Exponentially Small Error at Finite Block Length

Authors Jaroslaw Blasiok, Venkatesan Guruswami, Madhu Sudan



PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.34.pdf
  • Filesize: 0.5 MB
  • 17 pages

Document Identifiers

Author Details

Jaroslaw Blasiok
  • Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, 33 Oxford Street, Cambridge, MA 02138, USA
Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA.
Madhu Sudan
  • Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, 33 Oxford Street, Cambridge, MA 02138, USA.

Cite AsGet BibTex

Jaroslaw Blasiok, Venkatesan Guruswami, and Madhu Sudan. Polar Codes with Exponentially Small Error at Finite Block Length. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.34

Abstract

We show that the entire class of polar codes (up to a natural necessary condition) converge to capacity at block lengths polynomial in the gap to capacity, while simultaneously achieving failure probabilities that are exponentially small in the block length (i.e., decoding fails with probability exp(-N^{Omega(1)}) for codes of length N). Previously this combination was known only for one specific family within the class of polar codes, whereas we establish this whenever the polar code exhibits a condition necessary for any polarization. Our results adapt and strengthen a local analysis of polar codes due to the authors with Nakkiran and Rudra [Proc. STOC 2018]. Their analysis related the time-local behavior of a martingale to its global convergence, and this allowed them to prove that the broad class of polar codes converge to capacity at polynomial block lengths. Their analysis easily adapts to show exponentially small failure probabilities, provided the associated martingale, the "Arikan martingale", exhibits a corresponding strong local effect. The main contribution of this work is a much stronger local analysis of the Arikan martingale. This leads to the general result claimed above. In addition to our general result, we also show, for the first time, polar codes that achieve failure probability exp(-N^{beta}) for any beta < 1 while converging to capacity at block length polynomial in the gap to capacity. Finally we also show that the "local" approach can be combined with any analysis of failure probability of an arbitrary polar code to get essentially the same failure probability while achieving block length polynomial in the gap to capacity.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
Keywords
  • Polar codes
  • error exponent
  • rate of polarization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Erdal Arıkan. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, pages 3051-3073, July 2009. Google Scholar
  2. Jaroslaw Blasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan. General strong polarization. CoRR, abs/1802.02718, 2018. URL: http://arxiv.org/abs/1802.02718.
  3. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley and Sons, Hoboken, NJ, USA, 2nd edition, 2005. Google Scholar
  4. Venkatesan Guruswami and Ameya Velingker. An entropy sumset inequality and polynomially fast convergence to Shannon capacity over all alphabets. In Proceedings of 30th Conference on Computational Complexity, pages 42-57, 2015. Google Scholar
  5. Venkatesan Guruswami and Patrick Xia. Polar codes: Speed of polarization and polynomial gap to capacity. In Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), pages 310-319, October 2013. Google Scholar
  6. Seyed Hamed Hassani, Kasra Alishahi, and Rüdiger L. Urbanke. Finite-length scaling for polar codes. IEEE Trans. Information Theory, 60(10):5875-5898, 2014. URL: http://dx.doi.org/10.1109/TIT.2014.2341919.
  7. Satish Babu Korada, Eren Sasoglu, and Rüdiger L. Urbanke. Polar codes: Characterization of exponent, bounds, and constructions. IEEE Transactions on Information Theory, 56(12):6253-6264, 2010. URL: http://dx.doi.org/10.1109/TIT.2010.2080990.
  8. Ryuhei Mori and Toshiyuki Tanaka. Source and channel polarization over finite fields and reed-solomon matrices. IEEE Trans. Information Theory, 60(5):2720-2736, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail