Simplified SCL decoding algorithm of polar codes based on critical sets

Abstract

In order to reduce the high complexity of the successive cancellation list (SCL) algorithm for polar codes, a simplified SCL decoding algorithm based on critical sets (CS-SCL decoding algorithm) is proposed. The algorithm firstly constructs the critical sets according to the channel characteristics of the polar codes as well as comprehensively considering both the minimum Hamming weight (MHW) of the information bits and the channel reliability. The information bits within the critical sets and the path splitting are still performed by the SCL decoding algorithm while the information bits outside the critical sets are directly performed by the hard decision. Thus, the number of path ordering, copying, and deleting can be reduced during decoding. Furthermore, the computational complexity of the SCL decoding can also be reduced. Simulation results demonstrate that the decoding complexity of the proposed CS-SCL decoding algorithm, compared with the conventional SCL decoding algorithm, is reduced by at least 70%, while compared with the simplified SCL (PS-SS-SCL) algorithm which constructs the critical set with the first and second information bits of the Rate-1 nodes, its decoding complexity can also be reduced. Moreover, the loss of the error correction performance for the proposed CS-SCL decoding algorithm is minor. Therefore, the proposed CS-SCL algorithm is effective and can provide a reasonable tradeoff between the decoding performance and complexity for the decoding algorithm of polar codes.

References

[1] ArikanE. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE transactions on information theory, 2009, 55(7):3051-3073

[2] LiX W, LiW B. A simplified successive cancellation list decoding algorithm for polar codes[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2019, 31(4):488-494

[3] LiuW, DuanH G. Adaptive successive cancellation list bit-flip decoding of polar codes[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2021, 33(1):87-93

[4] TalI, VardyA. List decoding of polar codes[J]. IEEE transactions on information theory, 2015, 61(5):2213-2226

[5] NiuK, ChenK. CRC-aided decoding of polar codes[J]. IEEE communications letters, 2012, 16(10):1668-1671

[6] ChengF Y, LiuA J, ZhangY X, et al.. CRC location design for polar codes[J]. IEEE communications letters, 2018, 22(11):2202-2205

[7] WangT, QuD, JiangT. Parity-check-concatenated polar codes[J]. IEEE communications letters, 2016, 20(12):2342-2345

[8] ShenY F, LiL P, YangJ M, et al.. Low-latency segmented list-pruning software polar list decoder[J]. IEEE transactions on vehicular technology, 2020, 69(4):3575-3589

[9] SunH, LiuR K. A simplified decoding method of polar codes based on hypothesis testing[J]. IEEE communications letters, 2020, 24(3):530-533

[10] LeeK, ParkI C. Large-small sorting for successive cancellation list decoding of polar codes[J]. IEEE access, 2020, 8: 96955-96962

[11] GaoC Y, LiuR K, DaiB, et al.. Path splitting selecting strategy-aided successive cancellation list algorithm for polar codes[J]. IEEE communications letters, 2019, 23(3):422-425

[12] PengY, WuH, ChenP, et al.. Simplified path split strategy for SCL decoding algorithm with lower latency[C], 2022, New York, IEEE: 1-6

[13] Balatsoukas-StimmingA, PariziM B, BurgA. LLR-based successive cancellation list decoding of polar codes[J]. IEEE transactions on signal processing, 2014, 63(19):5165-5179

[14] NiuK, LiY. Polar coded diversity on block fading channels via polar spectrum[J]. IEEE transactions on signal processing, 2021, 69: 4007-4022

[15] HeG N, BelfioreJ C, LandI, et al.. Beta-expansion: a theoretical framework for and recursive construction of polar codes[C], 2017, New York, IEEE: 1-6

[16] HaoS J. Research on joint channel estimation and decoding for polar codes in wireless communication[D], 2020, Xian, Xidian University: 62-66