Построение и декодирование полярных кодов с большими ядрами: обзор

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Представлены методы построения и декодирования полярных кодов с большими ядрами. Важнейшей проблемой при реализации алгоритма последовательного исключения декодирования полярных кодов и его обобщений является обработка ядра, т.е. быстрое вычисление логарифмических отношений правдоподобия для входных символов ядра. Представлены оконный и рекурсивный решетчатый методы обработки больших ядер. Рассмотрены методы оценки надежности битовых подканалов и получения кодов с улучшенными свойствами расстояния.

Ключевые слова

Об авторах

Петр Владимирович Трифонов

Университет ИТМО

Email: pvtrifonov@itmo.ru
Санкт-Петербург, Россия

Список литературы

  1. Arıkan E. Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels // IEEE Trans. Inform. Theory. 2009. V. 55. № 7. P. 3051-3073. https://doi.org/10.1109/TIT.2009.2021379
  2. Korada S.B., Şaşoğlu E., Urbanke R. Polar Codes: Characterization of Exponent, Bounds, and Constructions // IEEE Trans. Inform. Theory. 2010. V. 56. № 12. P. 6253-6264. https://doi.org/10.1109/TIT.2010.2080990
  3. Fazeli A., Hassani H., Mondelli M., Vardy A. Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels // IEEE Trans. Inform. Theory. 2021. V. 67. № 9. P. 5693-5710. https://doi.org/10.1109/TIT.2020.3038806
  4. Wang H.-P., Duursma I.M. Polar Codes' Simplicity, Random Codes' Durability // IEEE Trans. Inform. Theory. 2021. V. 67. № 3. P. 1478-1508. https://doi.org/10.1109/TIT.2020.3041570
  5. Guruswami V., Riazanov A., Ye M. Arıkan Meets Shannon: Polar Codes with Near-Optimal Convergence to Channel Capacity // IEEE Trans. Inform. Theory. 2022. V. 68. № 5. P. 2877-2919. https://doi.org/10.1109/TIT.2022.3146786
  6. Presman N., Shapira O., Litsyn S. Mixed-Kernels Constructions of Polar Codes // IEEE J. Select. Areas Commun. 2016. V. 34. № 2. P. 239-253. https://doi.org/10.1109/JSAC.2015.2504278
  7. Bioglio V., Gabry F., Land I., Bel ore J.-C. Multi-Kernel Polar Codes: Concept and Design Principles // IEEE Trans.Commun. 2020. V. 68. № 9. P. 5350-5362. https://doi.org/10.1109/TCOMM.2020.3006212
  8. Trifonov P. Binary Successive Cancellation Decoding of Polar Codes with Reed-Solomon Kernel // Proc. 2014 IEEE Int. Symp. on Information Theory (ISIT'2014). Honolulu, HI, USA. June 29 - July 4, 2014. P. 2972-2976. https://doi.org/10.1109/ISIT.2014.6875379
  9. Bioglio V., Land I. On the Marginalization of Polarizing Kernels // Proc. 2018 IEEE 10th Int. Symp. on Turbo Codes & Iterative Information Processing (ISTC'2018). Hong Kong, China. Dec. 3-7, 2018. P. 1-5. https://doi.org/10.1109/ISTC.2018.8625378
  10. Tal I., Vardy A. List Decoding of Polar Codes // IEEE Trans. Inform. Theory. 2015. V. 61. № 5. P. 2213-2226. https://doi.org/10.1109/TIT.2015.2410251
  11. Miloslavskaya V., Trifonov P. Sequential Decoding of Polar Codes // IEEE Commun. Lett. 2014. V. 18. № 7. P. 1127-1130. https://doi.org/10.1109/LCOMM.2014.2323237
  12. Chandesris L., Savin V., Declercq D. Dynamic-SCFlip Decoding of Polar Codes // IEEE Trans.Commun. 2018. V. 66. № 6. P. 2333-2345. https://doi.org/10.1109/TCOMM.2018.2793887
  13. Trifonov P. A Score Function for Sequential Decoding of Polar Codes // Proc. 2018 IEEE Int. Symp. on Information Theory (ISIT'2018). Vail, CO, USA. June 17-22, 2018. P. 1470-1474. https://doi.org/10.1109/ISIT.2018.8437559
  14. Polyanskiy Y., Poor H.V., Verdú S. Channel Coding Rate in the Finite Blocklength Regime // IEEE Trans. Inform. Theory. 2010. V. 56. № 5. P. 2307-2359. https://doi.org/10.1109/TIT.2010.2043769
  15. Mondelli M., Hassani S.H., Urbanke R.L. Unified Scaling of Polar Codes: Error Exponent, Scaling Exponent, Moderate Deviations, and Error Floors // IEEE Trans. Inform. Theory. 2016. V. 62. № 12. P. 6698-6712. https://doi.org/10.1109/TIT.2016.2616117
  16. Fazeli A., Vardy A. On the Scaling Exponent of Binary Polarization Kernels // Proc. 52nd Annu. Allerton Conf. on Communication, Control, and Computing (Allerton'2014). Monticello, IL, USA. Sept. 30 - Oct. 3, 2014. P. 797-804. https://doi.org/10.1109/ALLERTON.2014.7028536
  17. Yao H., Fazeli A., Vardy A. Explicit Polar Codes with Small Scaling Exponent // Proc. 019 IEEE Int. Symp. on Information Theory (ISIT'2019). Paris, France. July 7-12, 2019. 1 1 2 P. 1757-1761. https://doi.org/10.1109/ISIT.2019.8849741
  18. Mondelli M., Hassani S.H., Urbanke R.L. How to Achieve the Capacity of Asymmetric Channels // IEEE Trans. Inform. Theory. 2018. V. 64. № 5. P. 3371-3393. https://doi.org/10.1109/TIT.2018.2789885
  19. Park W., Barg A. Polar Codes for q-ary Channels, q = 2r // IEEE Trans. Inform. Theory. 2013. V. 59. № 2. P. 955-969. https://doi.org/10.1109/TIT.2012.2219035
  20. Şaşoğlu E., Telatar E., Arıkan E. Polarization for Arbitrary Discrete Memoryless Channels // Proc. IEEE 2009 Information Theory Workshop (ITW'2009). Taormina, Italy. Oct. 11-16, 2009. P. 144-148. https://doi.org/10.1109/ITW.2009.5351487
  21. Mori R., Tanaka T. Source and Channel Polarization over Finite Fields and Reed-Solomon Matrices // IEEE Trans. Inform. Theory. 2014. V. 60. № 5. P. 2720-2736. https://doi.org/10.1109/TIT.2014.2312181
  22. Presman N., Shapira O., Litsyn S., Etzion T., Vardy A. Binary Polarization Kernels from Code Decompositions // IEEE Trans. Inform. Theory. 2015. V. 61. № 5. P. 2227-2239. https://doi.org/10.1109/TIT.2015.2409257
  23. Trofimiuk G., Trifonov P. Efficient Decoding of Polar Codes with Some 16 × 16 Kernels // Proc. IEEE 2018 Information Theory Workshop (ITW'2018). Guangzhou, China. Nov. 25-29, 2018. P. 11-15. https://doi.org/10.1109/ITW.2018.8613307
  24. Trofimiuk G. A Search Method for Large Polarization Kernels // Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT'2021). Melbourne, Australia. July 12-20, 2021. P. 2084-2089. https://doi.org/10.1109/ISIT45174.2021.9517729
  25. Lin H.-P., Lin S., Abdel-Ghaffar K.A.S. Linear and Nonlinear Binary Kernels of Polar Codes of Small Dimensions with Maximum Exponents // IEEE Trans. Inform. Theory. 2015. V. 61. № 10. P. 5253-5270. https://doi.org/10.1109/TIT.2015.2469298
  26. Moskovskaya E., Trifonov P. Design of BCH Polarization Kernels with Reduced Processing Complexity // IEEE Commun. Lett. 2020. V. 24. № 7. P. 1383-1386. https://doi.org/10.1109/LCOMM.2020.2984382
  27. Abbasi F., Viterbo E. Large Kernel Polar Codes with Efficient Window Decoding // IEEE Trans. Veh. Technol. 2020. V. 69. № 11. P. 14031-14036. https://doi.org/10.1109/TVT.2020.3029305
  28. Trofimiuk G. Shortened Polarization Kernels // Proc. 2021 IEEE Globecom Work shops (GC Wkshps). Madrid, Spain. Dec. 7-11, 2021. P. 1-6. https://doi.org/10.1109/GCWkshps52748.2021.9681982
  29. Miloslavskaya V., Trifonov P. Sequential Decoding of Polar Codes with Arbitrary Binary Kernel // Proc. IEEE 2014 Information Theory Workshop (ITW'2014). Hobart, TAS, Australia. Nov. 2-5, 2014. P. 376-380. https://doi.org/10.1109/ITW.2014.6970857
  30. Fujiwara T., Yamamoto H., Kasami T., Lin S. A Trellis-Based Recursive Maximum Likelihood Decoding Algorithm for Binary Linear Block Codes // IEEE Trans. Inform. Theory. 1998. V. 44. № 2. P. 714-729. https://doi.org/10.1109/18.661515
  31. Trifonov P. Trellis-Based Decoding Techniques for Polar Codes with Large Kernels // Proc. IEEE 2019 Information Theory Workshop (ITW'2019). Visby, Sweden. Aug. 25-28, 2019. P. 249-253. https://doi.org/10.1109/ITW44776.2019.8989386
  32. Trifonov P., Karakchieva L. Recursive Processing Algorithm for Low Complexity Decoding of Polar Codes with Large Kernels // IEEE Trans.Commun. Early access June 2023, https://doi.org/10.1109/TCOMM.2023.3285773
  33. Balatsoukas-Stimming A., Bastani Parizi M., Burg A. LLR-Based Successive Cancellation List Decoding of Polar Codes // IEEE Trans. Signal Process. 2015. V. 63. № 19. P. 5165-5179. https://doi.org/10.1109/TSP.2015.2439211
  34. Trofimiuk G., Iakuba N., Rets S., Ivanov K., Trifonov P. Fast Block Sequential Decoding of Polar Codes // IEEE Trans. Veh. Technol. 2020. V. 69. № 10. P. 10988-10999. https://doi.org/10.1109/TVT.2020.3006369
  35. Trofimiuk G., Trifonov P. Window Processing of Binary Polarization Kernels // IEEE Trans.Commun. 2021. V. 69. № 7. P. 4294-4305. https://doi.org/10.1109/TCOMM.2021.3072730
  36. Trofimiuk G., Trifonov P. Construction of Binary Polarization Kernels for Low Complexity Window Processing // Proc. IEEE 2019 Information Theory Workshop (ITW'2019). Visby, Sweden. Aug. 25-28, 2019. P. 115-119. https://doi.org/10.1109/ITW44776.2019.8989344
  37. Valembois A., Fossorier M. Box and Match Techniques Applied to Soft-Decision Decoding // IEEE Trans. Inform. Theory. 2004. V. 50. № 5. P. 796-810. https://doi.org/10.1109/TIT.2004.826644
  38. Gupta B., Yao H., Fazeli A., Vardy A. Polar List Decoding for Large Polarization Kernels // Proc. 2021 IEEE Globecom Workshops (GC Wkshps). Madrid, Spain. Dec. 7-11, 2021. P. 1-6. https://doi.org/10.1109/GCWkshps52748.2021.9681935
  39. Trifonov P. Efficient Design and Decoding of Polar Codes // IEEE Trans.Commun. 2012. V. 60. № 11. P. 3221-3227. https://doi.org/10.1109/TCOMM.2012.081512.110872
  40. Tal I., Vardy A. How to Construct Polar Codes // IEEE Trans. Inform. Theory. 2013. V. 59. № 10. P. 6562-6582. https://doi.org/10.1109/TIT.2013.2272694
  41. Mori R., Tanaka T. Performance of Polar Codes with the Construction Using Density Evolution // IEEE Commun. Lett. 2009. V. 13. № 7. P. 519-521. https://doi.org/10.1109/LCOMM.2009.090428
  42. Kern D., Vorköper S., Kühn V. A New Code Construction for Polar Codes Using Min-Sum Density // Proc. 2014 8th Int. Symp. on Turbo Codes and Iterative Information Processing (ISTC'2014). Bremen, Germany. Aug. 18-22, 2014. P. 228-232. https://doi.org/10.1109/ISTC.2014.6955119
  43. Miloslavskaya V., Trifonov P. Design of Binary Polar Codes with Arbitrary Kernels // Proc. 2012 IEEE Information Theory Workshop (ITW'2012). Lausanne, Switzerland. Sept. 3-7, 2012. P. 119-123. https://doi.org/10.1109/ITW.2012.6404639
  44. Richardson T., Urbanke R. Modern Coding Theory. Cambridge, UK: Cambridge Univ. Press, 2008
  45. Trifonov P. On Construction of Polar Subcodes with Large Kernels // Proc. 2019 IEEE Int. Symp. on Information Theory (ISIT'2019). Paris, France. July 7-12, 2019. P. 1932-1936. https://doi.org/10.1109/ISIT.2019.8849672
  46. Karakchieva L., Trifonov P. An Approximate Method for Construction of Polar Codes with Kernels over F2t // IEEE Commun. Lett. 2020. V. 24. № 9. P. 1857-1860. https://doi.org/10.1109/LCOMM.2020.2995257
  47. Trifonov P., Miloslavskaya V. Polar Subcodes // IEEE J. Select. Areas Commun. 2016. V. 34. № 2. P. 254-266. https://doi.org/10.1109/JSAC.2015.2504269
  48. Trifonov P. Randomized Polar Subcodes with Optimized Error Coefficient // IEEE Trans.Commun. 2020. V. 68. № 11. P. 6714-6722. https://doi.org/10.1109/TCOMM.2020.3018781
  49. Trifonov P., Trofimiuk G. A Randomized Construction of Polar Subcodes // Proc. 2017 IEEE Int. Symp. on Information Theory (ISIT'2017). Aachen, Germany. June 25-30, 2017. P. 1863-1867. https://doi.org/10.1109/ISIT.2017.8006852
  50. Miloslavskaya V., Vucetic B., Li Y., Park G., Park O.-S. Recursive Design of Precoded Polar Codes For SCL Decoding // IEEE Trans.Commun. 2021. V. 69. № 12. P. 7945-7959. https://doi.org/10.1109/TCOMM.2021.3111625
  51. Trifonov P. Recursive Trellis Processing of Large Polarization Kernels // Proc. 2021 IEEE Int. Symp. on Information Theory (ISIT'2021). Melbourne, Australia. July 12-20, 2021. P. 2090-2095. https://doi.org/10.1109/ISIT45174.2021.9517783

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2023