Design of Polar Codes with Large Binary Kernels

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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

References

  1. 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
  2. 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
  3. Marshakov E., Balitskiy G., Andreev K., Frolov A. A Polar Code Based Unsourced Random Access for the Gaussian MAC // Proc. 2019 IEEE 90th Vehicular Technology Conf. (VTC2019-Fall). Honolulu, HI, USA. Sept. 22–25, 2019. P. 1–5. https://doi.org/10.1109/ VTCFall.2019.8891583
  4. Xie Z., Chen P., Mei Z., Long S., Cai K., Fang Y. Polar-Coded Physical Layer Network Coding Over Two-Way Relay Channels // IEEE Commun. Lett. 2019. V. 23. № 8. P. 1301–1305. https://doi.org/10.1109/LCOMM.2019.2922633
  5. Andersson M., Rathi V., Thobaben R., Kliewer J., Skoglund M. Nested Polar Codes for Wiretap and Relay Channels // IEEE Commun. Lett. 2010. V. 14. № 8. P. 752–754. https: //doi.org/10.1109/LCOMM.2010.08.100875
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. Timokhin I., Ivanov F. Sequential Polar Decoding with Cost Metric Threshold // Appl. Sci. 2024. V. 14. № 5. Paper No. 1847 (13 pp.). https://doi.org/10.3390/app14051847
  12. Korada S.B., S¸as¸og˘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
  13. Mori R., Tanaka T. Channel Polarization on q-ary Discrete Memoryless Channels by Arbitrary Kernels // Proc. 2010 IEEE Int. Sympos. on Information Theory (ISIT 2010). Austin, TX, USA. June 13–18, 2010. P. 894–898. https://doi.org/10.1109/ISIT.2010.5513568
  14. Pfister H.D., Urbanke R.L. Near-Optimal Finite-Length Scaling for Polar Codes over large alphabets // Proc. 2016 IEEE Int. Symp. on Information Theory (ISIT 2016), Barcelona, Spain, July 10–15, 2016. P. 215–219. https://doi.org/10.1109/ISIT.2016.7541292
  15. Fazeli A., Hassani H., Mondelli M., Vardy A. Binary Linear Codes with Optimal Scaling: Polar Codes with Large Kernels // Proc. IEEE 2018 Information Theory Workshop (ITW’2018). Guangzhou, China. Nov. 25–29, 2018. P. 1–5. https://doi.org/10.1109/ITW. 2018.8613428
  16. 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
  17. 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
  18. 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
  19. 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
  20. Vangala H., Viterbo E., Hong Y. A Comparative Study of Polar Code Constructions for the AWGN Channel, https://arxiv.org/abs/1501.02473 [cs.IT], 2015.
  21. Bioglio V., Gabry F., Land I., Belfiore 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
  22. 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
  23. Trifonov P., Trofimiuk G. Design of Polar Codes with Large Kernels // Probl. Inf. Transm. 2024. V. 60. № 4 (to appear). https://doi.org/10.1134/S0032946024040033
  24. 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
  25. 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
  26. 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
  27. Гриссер Х., Сидоренко В.Р. Апостериорно-вероятностное декодирование несистематических блоковых кодов // Пробл. передачи информ. 2002. Т. 38. № 3. С. 20–33. https://www.mathnet.ru/rus/ppi1313
  28. Trifonov P. Algebraic Matching Techniques for Fast Decoding of Polar Codes with Reed– Solomon Kernel // Proc. 2018 IEEE Int. Symp. on Information Theory (ISIT 2018), Vail, CO, USA, June 17–22, 2018. P. 1475–1479. https://doi.org/10.1109/ISIT.2018.8437829
  29. Huang Z., Zhang S., Zhang F., Duanmu C., Zhong F., Chen M. Simplified Successive Cancellation Decoding of Polar Codes With Medium-Dimensional Binary Kernels // IEEE Access. 2018. V. 6. P. 26707–26717. https://doi.org/10.1109/ACCESS.2018.2834465
  30. Trifonov P., Karakchieva L. Recursive Processing Algorithm for Low Complexity Decoding of Polar Codes with Large Kernels // IEEE Trans. Commun. 2023. V. 71. № 9. P. 5039–5050. https://doi.org/10.1109/TCOMM.2023.3285773
  31. Трифонов П.В. Построение и декодирование полярных кодов с большими ядрами: обзор // Пробл. передачи информ. 2023. Т. 59. № 1. С. 25–45. https://doi.org/10.31857/ S0555292323010035
  32. Guillen i Fabregas A., Land I., Martinez A. Extremes of Error Exponents // IEEE Trans. Inform. Theory. 2013. V. 59. № 4. P. 2201–2207. https://doi.org/10.1109/TIT.2012. 2233271
  33. Колесников С.Г., Леонтьев В.М. Серии формул для параметров Бхаттачарьи в теории полярных кодов // Пробл. передачи информ. 2023. Т. 59. № 1. С. 3–16. https://doi. org/10.31857/S0555292323010011
  34. 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
  35. Yao H., Fazeli A., Vardy A. Explicit Polar Codes with Small Scaling Exponent // Proc. 2019 IEEE Int. Symp. on Information Theory (ISIT’2019). Paris, France. July 7–12, 2019. P. 1757–1761. https://doi.org/10.1109/ISIT.2019.8849741
  36. Ashikhmin A., Trifonov P. Efficient Evaluation of Polarization Behavior for Large Kernels // Proc. 2023 IEEE Int. Symp. on Information Theory (ISIT 2023). Taipei, Taiwan. June 25–30, 2023. P. 1717–1722. https://doi.org/10.1109/ISIT54713.2023.10206496
  37. Kern D., Vork¨oper S., Ku¨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
  38. Zhou Y., Li R., Zhang H., Luo H., Wang J. Polarization Weight Family Methods for Polar Code Construction // Proc. 2018 IEEE 87th Vehicular Technology Conf. (VTC Spring). Porto, Portugal. June 3–6, 2018. P. 1–5. https://doi.org/10.1109/VTCSpring. 2018.8417498
  39. Hussami N., Korada S.B., Urbanke R. Performance of Polar Codes for Channel and Source Coding // Proc. 2009 IEEE Int. Symp. on Information Theory (ISIT 2009). Seoul, Korea. June 28 – July 3, 2009. P. 1488–1492. https://doi.org/10.1109/ISIT.2009.5205860
  40. 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
  41. Miloslavskaya V., Li Y., Vucetic B. Design of Compactly Specified Polar Codes With Dynamic Frozen Bits Based on Reinforcement Learning // IEEE Trans. Commun. 2024. V. 72. № 3. P. 1257–1272. https://doi.org/10.1109/TCOMM.2023.3331532
  42. Oreshin M., Trifonov P. Polar Subcodes with Improved Weight Spectrum // 2024 IEEE Int. Multi-Conf. on Engineering, Computer and Information Sciences (SIBIRCON). Novosibirsk, Russian Federation. Sept. 30 – Oct. 2, 2024. P. 41–46. https://doi.org/10.1109/ SIBIRCON63777.2024.10758477
  43. Sun H., Viterbo E., Liu R. Analysis of Polarization-adjusted Convolutional Codes (PAC): A Source-Channel Coding Method // Proc. 2021 IEEE Globecom Workshops (GC Wkshps). Madrid, Spain. Dec. 7–11, 2021. P. 1–6. https://doi.org/10.1109/GCWkshps52748.2021. 9682079
  44. Rowshan M., Dau S.H., Viterbo E. On the Formation of Min-Weight Codewords of Po-lar/PAC Codes and Its Applications // IEEE Trans. Inform. Theory. 2023. V. 69. № 12. P. 7627–7649. https://doi.org/10.1109/TIT.2023.3319015
  45. Kann T., Kudekar S., Bloch M.R. A Path Metric Based Construction of Polarization-Adjusted Convolutional Codes // Proc. 2024 IEEE Int. Symp. on Information Theory (ISIT 2024). Athens, Greece. July 7–12, 2024. P. 2406–2411. https://doi.org/10.1109/ ISIT57864.2024.10619693
  46. Coffey J.T., Kiely A.B. The Capacity of Coded Systems // IEEE Trans. Inform. Theory. 1997. V. 43. № 1. P. 113–127. https://doi.org/10.1109/18.567656
  47. MacMul lan S.J., Col lins O.M. The Capacity of Binary Channels That Use Linear Codes and Decoders // IEEE Trans. Inform. Theory. 1998. V. 44. № 1. P. 197–214. https://doi. org/10.1109/18.651018
  48. ten Brink S. Convergence Behavior of Iteratively Decoded Parallel Concatenated Codes // IEEE Trans. Commun. 2001. V. 49. № 10. P. 1727–1737. https://doi.org/10.1109/26. 957394
  49. Richardson T., Urbanke R. Modern Coding Theory. Cambridge, UK: Cambridge Univ. Press, 2008.
  50. 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
  51. Trofimiuk G. Shortened 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.9681982
  52. Land I. Reliability Information in Channel Decoding: Practical Aspects and Information Theoretical Bounds. Ph.D. Thesis. Faculty of Engineering, Christian-Albrechts-University of Kiel, Germany, 2005. Availale at https://macau.uni-kiel.de/receive/diss_mods_ 00001414.
  53. Trofimiuk G., Trifonov P. Efficient Decoding of Polar Codes with Some 16 x 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

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».