Design and decoding of polar codes with large kernels: a survey
- Авторлар: Trifonov P.1
-
Мекемелер:
- ITMO University
- Шығарылым: Том 59, № 1 (2023)
- Беттер: 25-45
- Бөлім: Articles
- URL: https://journals.rcsi.science/0555-2923/article/view/141986
- DOI: https://doi.org/10.31857/S0555292323010035
- EDN: https://elibrary.ru/RMFRTN
- ID: 141986
Дәйексөз келтіру
Аннотация
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.
Негізгі сөздер
Әдебиет тізімі
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Ş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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- Richardson T., Urbanke R. Modern Coding Theory. Cambridge, UK: Cambridge Univ. Press, 2008
- 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
- 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
- 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
- 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
- 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
- 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
- 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