Design and decoding of polar codes with large kernels: a survey

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

We present techniques for the construction of polar codes with large kernels and their decoding. A crucial problem in the implementation of the successive cancellation decoding algorithm and its derivatives is kernel processing, i.e., fast evaluation of the log-likelihood ratios for kernel input symbols. We discuss window and recursive trellis processing methods. We consider techniques for evaluation of the reliability of bit subchannels and for obtaining codes with improved distance properties.

Негізгі сөздер

Авторлар туралы

P. Trifonov

ITMO University

Email: pvtrifonov@itmo.ru
St.-Petersburg, Russia

Әдебиет тізімі

  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

© Russian Academy of Sciences, 2023

Осы сайт cookie-файлдарды пайдаланады

Біздің сайтты пайдалануды жалғастыра отырып, сіз сайттың дұрыс жұмыс істеуін қамтамасыз ететін cookie файлдарын өңдеуге келісім бересіз.< / br>< / br>cookie файлдары туралы< / a>