Document Open Access Logo

Accelerating Polarization via Alphabet Extension

Authors Iwan Duursma , Ryan Gabrys , Venkatesan Guruswami , Ting-Chun Lin , Hsin-Po Wang

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.17.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Iwan Duursma
  • University of Illinois Urbana-Champaign, IL, USA
Ryan Gabrys
  • University of California San Diego, CA, USA
Venkatesan Guruswami
  • University of California, Berkeley, CA, USA
Ting-Chun Lin
  • University of California San Diego, CA, USA
  • Hon Hai (Foxconn) Research Institute, Taipei, Taiwan
Hsin-Po Wang
  • University of California San Diego, CA, USA

Funding

  • Gabrys, Ryan: NSF CCF-2107346.
  • Guruswami, Venkatesan: NSF CCF-2210823 and Simons Investigator Award.
  • Wang, Hsin-Po: NSF CCF-1764104.

Cite As Get BibTex

Iwan Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, and Hsin-Po Wang. Accelerating Polarization via Alphabet Extension. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.17

Abstract

Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is three-fold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for real-life applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code.
In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke Mori-Tanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almost-one-parameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first non-binary matrix whose scaling exponent is upper-bounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Coding theory
  • Theory of computation → Error-correcting codes
Keywords
  • polar code
  • scaling exponent

Metrics

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

Related Versions

References

  1. Fariba Abbasi, Hessam Mahdavifar, and Emanuele Viterbo. Hybrid non-binary repeated polar codes. IEEE Transactions on Wireless Communications, pages 1-1, 2022. URL: https://doi.org/10.1109/TWC.2022.3159807.
  2. Erdal Arikan. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7):3051-3073, July 2009. URL: https://doi.org/10.1109/TIT.2009.2021379.
  3. Erdal Arikan and Emre Telatar. On the rate of channel polarization. In 2009 IEEE International Symposium on Information Theory, pages 1493-1495, June 2009. URL: https://doi.org/10.1109/ISIT.2009.5205856.
  4. D. Baron, M.A. Khojastepour, and R.G. Baraniuk. How quickly can we approach channel capacity? In Conference Record of the Thirty-Eighth Asilomar Conference on Signals, Systems and Computers, 2004., volume 1, pages 1096-1100 Vol.1, November 2004. URL: https://doi.org/10.1109/ACSSC.2004.1399310.
  5. Manan Bhandari, Ishan Bansal, and V. Lalitha. On the polarizing behavior and scaling exponent of polar codes with product kernels. In 2020 National Conference on Communications (NCC), pages 1-6, February 2020. URL: https://doi.org/10.1109/NCC48643.2020.9056096.
  6. Valerio Bioglio, Frédéric Gabry, Ingmar Land, and Jean-Claude Belfiore. Multi-kernel polar codes: Concept and design principles. IEEE Transactions on Communications, 68(9):5350-5362, September 2020. URL: https://doi.org/10.1109/TCOMM.2020.3006212.
  7. Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan. General strong polarization. J. ACM, 69(2), March 2022. URL: https://doi.org/10.1145/3491390.
  8. Jaroslaw Blasiok, Venkatesan Guruswami, and Madhu Sudan. Polar Codes with Exponentially Small Error at Finite Block Length. In Eric Blais, Klaus Jansen, José D. P. Rolim, and David Steurer, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), volume 116 of Leibniz International Proceedings in Informatics (LIPIcs), pages 34:1-34:17, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.34.
  9. Sarit Buzaglo, Arman Fazeli, Paul H. Siegel, Veeresh Taranalli, and Alexander Vardy. Permuted successive cancellation decoding for polar codes. In 2017 IEEE International Symposium on Information Theory (ISIT), pages 2618-2622, June 2017. URL: https://doi.org/10.1109/ISIT.2017.8007003.
  10. Eduardo Camps, Hiram H. López, Gretchen L. Matthews, and Eliseo Sarmiento. Polar decreasing monomial-cartesian codes. IEEE Transactions on Information Theory, 67(6):3664-3674, June 2021. URL: https://doi.org/10.1109/TIT.2020.3047624.
  11. Semih Cayci, Toshiaki Koike-Akino, and Ye Wang. Nonbinary polar coding for multilevel modulation. In 2019 Optical Fiber Communications Conference and Exhibition (OFC), pages 1-3, 2019. Google Scholar
  12. Peiyao Chen, Baoming Bai, and Xiao Ma. Two-stage polarization-based nonbinary polar codes for 5g urllc, 2018. URL: https://doi.org/10.48550/ARXIV.1801.08059.
  13. Mao-Ching Chiu. Non-binary polar codes with channel symbol permutations. In 2014 International Symposium on Information Theory and its Applications, pages 433-437, October 2014. Google Scholar
  14. Iwan Duursma, Ryan Gabrys, Venkatesan Guruswami, Ting-Chun Lin, and Hsin-Po Wang. Accelerating polarization via alphabet extension, 2022. URL: https://doi.org/10.48550/ARXIV.2207.04522.
  15. Arman Fazeli, Hamed Hassani, Marco Mondelli, and Alexander Vardy. Binary linear codes with optimal scaling: Polar codes with large kernels. IEEE Transactions on Information Theory, 67(9):5693-5710, September 2021. URL: https://doi.org/10.1109/TIT.2020.3038806.
  16. Arman Fazeli and Alexander Vardy. On the scaling exponent of binary polarization kernels. In 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 797-804, September 2014. URL: https://doi.org/10.1109/ALLERTON.2014.7028536.
  17. Dina Goldin and David Burshtein. Improved bounds on the finite length scaling of polar codes. IEEE Transactions on Information Theory, 60(11):6966-6978, November 2014. URL: https://doi.org/10.1109/TIT.2014.2359197.
  18. Ali Goli, S. Hamed Hassani, and Rüdiger Urbanke. Universal bounds on the scaling behavior of polar codes. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 1957-1961, July 2012. URL: https://doi.org/10.1109/ISIT.2012.6283641.
  19. Venkatesan Guruswami, Andrii Riazanov, and Min Ye. Arıkan meets shannon: Polar codes with near-optimal convergence to channel capacity. IEEE Transactions on Information Theory, pages 1-1, 2022. URL: https://doi.org/10.1109/TIT.2022.3146786.
  20. Venkatesan Guruswami and Patrick Xia. Polar codes: Speed of polarization and polynomial gap to capacity. IEEE Transactions on Information Theory, 61(1):3-16, January 2015. URL: https://doi.org/10.1109/TIT.2014.2371819.
  21. S. Hamed Hassani, Kasra Alishahi, and Rudiger Urbanke. On the scaling of polar codes: Ii. the behavior of un-polarized channels. In 2010 IEEE International Symposium on Information Theory, pages 879-883, June 2010. URL: https://doi.org/10.1109/ISIT.2010.5513585.
  22. S. Hamed Hassani, Ryuhei Mori, Toshiyuki Tanaka, and Rüdiger L. Urbanke. Rate-dependent analysis of the asymptotic behavior of channel polarization. IEEE Transactions on Information Theory, 59(4):2267-2276, April 2013. URL: https://doi.org/10.1109/TIT.2012.2228295.
  23. Seyed Hamed Hassani, Kasra Alishahi, and Rüdiger L. Urbanke. Finite-length scaling for polar codes. IEEE Transactions on Information Theory, 60(10):5875-5898, October 2014. URL: https://doi.org/10.1109/TIT.2014.2341919.
  24. Masahito Hayashi. Information spectrum approach to second-order coding rate in channel coding. IEEE Transactions on Information Theory, 55(11):4947-4966, November 2009. URL: https://doi.org/10.1109/TIT.2009.2030478.
  25. Satish Babu Korada, Andrea Montanari, Emre Telatar, and Rüdiger Urbanke. An empirical scaling law for polar codes. In 2010 IEEE International Symposium on Information Theory, pages 884-888, June 2010. URL: https://doi.org/10.1109/ISIT.2010.5513579.
  26. Satish Babu Korada, Eren Şaşoğlu, and Rüdiger Urbanke. Polar codes: Characterization of exponent, bounds, and constructions. IEEE Transactions on Information Theory, 56(12):6253-6264, December 2010. URL: https://doi.org/10.1109/TIT.2010.2080990.
  27. Ingmar Land and Johannes Huber. Information combining. Foundations and Trendsregistered in Communications and Information Theory, 3(3):227-330, 2006. URL: https://doi.org/10.1561/0100000013.
  28. Liping Lin. On the construction of the kernel matrix by primitive bch codes for polar codes. Communications and Network, 14(1):23-35, 2021. Google Scholar
  29. Guan-Chen Liu and Qi-Yue Yu. Non-binary polar coded system for the two-user multiple-access channel, 2021. URL: https://doi.org/10.48550/ARXIV.2111.03839.
  30. Marco Mondelli, S. Hamed Hassani, and Rüdiger L. Urbanke. Scaling exponent of list decoders with applications to polar codes. IEEE Transactions on Information Theory, 61(9):4838-4851, September 2015. URL: https://doi.org/10.1109/TIT.2015.2453315.
  31. Marco Mondelli, S. Hamed Hassani, and Rüdiger L. Urbanke. Unified scaling of polar codes: Error exponent, scaling exponent, moderate deviations, and error floors. IEEE Transactions on Information Theory, 62(12):6698-6712, December 2016. URL: https://doi.org/10.1109/TIT.2016.2616117.
  32. Ryuhei Mori and Toshiyuki Tanaka. Non-binary polar codes using reed-solomon codes and algebraic geometry codes. In 2010 IEEE Information Theory Workshop, pages 1-5, August 2010. URL: https://doi.org/10.1109/CIG.2010.5592755.
  33. Ryuhei Mori and Toshiyuki Tanaka. Source and channel polarization over finite fields and reed-solomon matrices. IEEE Transactions on Information Theory, 60(5):2720-2736, May 2014. URL: https://doi.org/10.1109/TIT.2014.2312181.
  34. Rajai Nasser. An ergodic theory of binary operations - part i: Key properties. IEEE Transactions on Information Theory, 62(12):6931-6952, December 2016. URL: https://doi.org/10.1109/TIT.2016.2616642.
  35. Woomyoung Park and Alexander Barg. Polar codes for q-ary channels, q = 2^r. IEEE Transactions on Information Theory, 59(2):955-969, 2013. URL: https://doi.org/10.1109/TIT.2012.2219035.
  36. Henry D. Pfister and Rüdiger Urbanke. Near-optimal finite-length scaling for polar codes over large alphabets. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 215-219, July 2016. URL: https://doi.org/10.1109/ISIT.2016.7541292.
  37. Yury Polyanskiy, H. Vincent Poor, and Sergio Verdu. Channel coding rate in the finite blocklength regime. IEEE Transactions on Information Theory, 56(5):2307-2359, May 2010. URL: https://doi.org/10.1109/TIT.2010.2043769.
  38. Noam Presman, Ofer Shapira, and Simon Litsyn. Mixed-kernels constructions of polar codes. IEEE Journal on Selected Areas in Communications, 34(2):239-253, February 2016. URL: https://doi.org/10.1109/JSAC.2015.2504278.
  39. Constantin Runge, Thomas Wiegart, Diego Lentner, and Tobias Prinz. Multilevel binary polar-coded modulation achieving the capacity of asymmetric channels, 2022. URL: http://arxiv.org/abs/2202.04010.
  40. Aria G. Sahebi and S. Sandeep Pradhan. Multilevel polarization of polar codes over arbitrary discrete memoryless channels. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1718-1725, September 2011. URL: https://doi.org/10.1109/Allerton.2011.6120375.
  41. Eren Şaşoğlu. Polar codes for discrete alphabets. In 2012 IEEE International Symposium on Information Theory Proceedings, pages 2137-2141, July 2012. URL: https://doi.org/10.1109/ISIT.2012.6283740.
  42. Eren Şaşoğlu, Emre Telatar, and Erdal Arikan. Polarization for arbitrary discrete memoryless channels. In 2009 IEEE Information Theory Workshop, pages 144-148, October 2009. URL: https://doi.org/10.1109/ITW.2009.5351487.
  43. Valentin Savin. Non-binary polar codes for spread-spectrum modulations. In 2021 11th International Symposium on Topics in Coding (ISTC), pages 1-5, August 2021. URL: https://doi.org/10.1109/ISTC49272.2021.9594166.
  44. Mathis Seidl, Andreas Schenk, Clemens Stierstorfer, and Johannes B. Huber. Polar-coded modulation. IEEE Transactions on Communications, 61(10):4108-4119, October 2013. URL: https://doi.org/10.1109/TCOMM.2013.090513.130433.
  45. Grigorii Trofimiuk. Shortened polarization kernels. In 2021 IEEE Globecom Workshops (GC Wkshps), pages 1-6, December 2021. URL: https://doi.org/10.1109/GCWkshps52748.2021.9681982.
  46. Grigorii Trofimiuk and Peter Trifonov. Window processing of binary polarization kernels. IEEE Transactions on Communications, 69(7):4294-4305, July 2021. URL: https://doi.org/10.1109/TCOMM.2021.3072730.
  47. Hsin-Po Wang. Complexity and second moment of the mathematical theory of communication, 2021. URL: http://arxiv.org/abs/2107.06420.
  48. Hsin-Po Wang and Iwan M. Duursma. Polar codes' simplicity, random codes' durability. IEEE Transactions on Information Theory, 67(3):1478-1508, 2021. Google Scholar
  49. Hsin-Po Wang, Ting-Chun Lin, Alexander Vardy, and Ryan Gabrys. Sub-4.7 scaling exponent of polar codes, 2022. URL: https://doi.org/10.48550/ARXIV.2204.11683.
  50. Hanwen Yao, Arman Fazeli, and Alexander Vardy. Explicit polar codes with small scaling exponent. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1757-1761, 2019. URL: https://doi.org/10.1109/ISIT.2019.8849741.
  51. Peihong Yuan and Fabian Steiner. Construction and decoding algorithms for polar codes based on 2 × 2 non-binary kernels. In 2018 IEEE 10th International Symposium on Turbo Codes Iterative Information Processing (ISTC), pages 1-5, December 2018. URL: https://doi.org/10.1109/ISTC.2018.8625284.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact