A fast decoding algorithm for polar codes based on soft output

Yiqiao LU; Yin XU; Hao JU; Wenxue SUN; Dongdong WANG; Dazhi HE; Yongpeng WU; Zhiyong CHEN; Wenjun ZHANG

doi:10.16511/j.cnki.qhdxxb.2025.27.043

PDF(2379 KB)

Journal of Tsinghua University(Science and Technology) ›› 2025, Vol. 65 ›› Issue (11) : 2032-2041. DOI: 10.16511/j.cnki.qhdxxb.2025.27.043

Frontiers in New-Quality Communication Technology

A fast decoding algorithm for polar codes based on soft output

Yiqiao LU ¹ ,
Yin XU ¹^,³^,* ,
Hao JU ¹ ,
Wenxue SUN ¹ ,
Dongdong WANG ³^,⁴ ,
Dazhi HE ¹ ,
Yongpeng WU ² ,
Zhiyong CHEN ¹ ,
Wenjun ZHANG ¹^,²

Author information +

History +

Abstract

Objective: The development of communication systems and increasing demand for low-latency and high-reliability communications has led to a rise in application scenarios requiring soft information interaction for joint iterative decoding to improve system performance. The soft-output successive cancellation list (SO-SCL) decoding algorithm of polar codes can achieve relatively accurate soft information output and decoding with the complexity of traditional successive cancellation list (SCL) decoding by estimating the codebook and posterior probabilities. However, the serial characteristics of SCL decoding result in a high decoding delay of the SO-SCL decoding algorithm, making it difficult to satisfy the 1 Tbps peak throughput requirement of the sixth-generation mobile communication system. To reduce the decoding delay, the existing soft-output fast SCL decoding algorithm (SO -FSCL) realizes fast decoding by identifying four special nodes; however, some nodes still have a high decoding delay. Therefore, a high-performance soft-output decoding algorithm for polar codes with lower decoding delay is required. Methods: In previous studies, special nodes were identified, aiming to achieve fast decoding of different special nodes and combined decoding between nodes. Based on the SO -FSCL decoding algorithm, this study introduces five other special nodes, namely REP-2, REP-3, REP-4, SPC-2, and SPC-3, and proposes a faster soft-output SCL decoding algorithm (FS-SCL). The developed decoding algorithm enables fast decoding of the five new nodes and provides a posterior probability formula for the deleted path. For the REP-2, REP-3, and REP-4 nodes, only 4, 8, and 16 possible decoding paths need to be considered, respectively, and the sum of the probabilities of the deleted paths is calculated. According to the distribution characteristics of the information bits in the nodes, SPC-2 can be simplified to the parallel decoding of two SPC sub-nodes with N_s/2 bits. After combination, the SPC-3 node can be regarded as a repetitive code with a code rate of 1, thereby simplifying the decoding process. Moreover, compared with SCL decoding, which requires flipping all bits, while with the SPC-2 and SPC-3 nodes, only the min{L-1, N_s-2}, min{L-1, N_s-3} bits require flipping during the decoding process, thereby reducing the decoding delay. The time steps required for decoding different nodes are also analyzed herein to evaluate the decoding delay. The five newly added nodes require 3, 4, 5, max{log₂N_s+1, min{L, N_s-1}}, and max{log₂N_s+3, min{L, N_s-2}} time steps, respectively. Compared with the original SCL decoding algorithm, the node significantly reduces the time steps required for decoding. Results: The simulation results show that by employing the AWGN channel, the proposed FS-SCL decoding algorithm maintains a BER performance similar to that of SO-SCL in different modulation methods, especially under 16QAM. By reducing the proportion of high-code rate nodes, the performance loss is reduced. Compared with the existing SO -FSCL decoding algorithm, the FS-SCL decoding algorithm can further reduce the decoding delay by more than 12.5% (up to 28.7%) and can further reduce the decoding complexity. Moreover, by merging shorter nodes, the FS-SCL decoding algorithm reduces the number of nodes by 42% and achieves a minimum node code length of 8, which is conducive to improving the decoding parallelism. Conclusions: The developed FS-SCL decoding algorithm with lower delay and complexity affords lossless BER performance using different modulation methods. The research results can provide an efficient polar-code decoding scheme for low-latency communication scenarios with soft output, which has important theoretical value and application prospects.

Key words

polar code / list decoding / soft output / special node / fast decoding

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

Yiqiao LU , Yin XU , Hao JU , et al . A fast decoding algorithm for polar codes based on soft output[J]. Journal of Tsinghua University(Science and Technology). 2025, 65(11): 2032-2041 https://doi.org/10.16511/j.cnki.qhdxxb.2025.27.043

References

List( Publishing order | Descend order by publishing year | Descend order by cited within ) Chart analysis

1	ARIKAN E . 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. https://doi.org/10.1109/TIT.2009.2021379 Cited in this article [3]

2	HUI D , SANDBERG S , BLANKENSHIP Y , et al. Channel coding in 5G new radio: A tutorial overview and performance comparison with 4G LTE[J]. IEEE Vehicular Technology Magazine, 2018, 13 (4): 60- 69. https://doi.org/10.1109/MVT.2018.2867640 Cited in this article [1]

3	ARIKAN E . A performance comparison of polar codes and Reed-Muller codes[J]. IEEE Communications Letters, 2008, 12 (6): 447- 449. https://doi.org/10.1109/LCOMM.2008.080017 Cited in this article [1]

4	TAL I , VARDY A . List decoding of polar codes[J]. IEEE Transactions on Information Theory, 2015, 61 (5): 2213- 2226. https://doi.org/10.1109/TIT.2015.2410251 Cited in this article [1]

5	NIU K , CHEN K . CRC-aided decoding of polar codes[J]. IEEE Communications Letters, 2012, 16 (10): 1668- 1671. https://doi.org/10.1109/LCOMM.2012.090312.121501 Cited in this article [1]

6	DAI J C , NIU K , LIN J R . Polar-coded MIMO systems[J]. IEEE Transactions on Vehicular Technology, 2018, 67 (7): 6170- 6184. https://doi.org/10.1109/TVT.2018.2815602 Cited in this article [1]

7	PAN Z P , LI E B , ZHANG L , et al. Design and optimization of joint iterative detection and decoding receiver for uplink polar coded SCMA system[J]. IEEE Access, 2018, 6, 52014- 52026. https://doi.org/10.1109/ACCESS.2018.2869906 Cited in this article [1]

8	SHEN L , WU Y P , XU Y , et al. GLDPC-PC codes: Channel coding toward 6G communications[J]. IEEE Communications Magazine, 2025, 1- 7. Cited in this article [1]

9	FAYYAZ U U , BARRY J R . Low-complexity soft-output decoding of polar codes[J]. IEEE Journal on Selected Areas in Communications, 2014, 32 (5): 958- 966. https://doi.org/10.1109/JSAC.2014.140515 Cited in this article [1]

10	FAYYAZ U U, BARRY J R. A low-complexity soft-output decoder for polar codes[C]//2013 IEEE Global Communications Conference (GLOBECOM). Atlanta, USA: IEEE, 2013: 2692-2697. Cited in this article [1]

11	PILLET C, CONDO C, BIOGLIO V. SCAN list decoding of polar codes[C]//ICC 2020-2020 IEEE International Conference on Communications. Dublin, Ireland: IEEE, 2020: 1-6. Cited in this article [1]

12	ELKELESH A , EBADA M , CAMMERER S , et al. Belief propagation list decoding of polar codes[J]. IEEE Communications Letters, 2018, 22 (8): 1536- 1539. https://doi.org/10.1109/LCOMM.2018.2850772 Cited in this article [1]

13	BAHL L , COCKE J , JELINEK F , et al. Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)[J]. IEEE Transactions on Information Theory, 1974, 20 (2): 284- 287. Cited in this article [1]

14	PYNDIAH R M . Near-optimum decoding of product codes: Block turbo codes[J]. IEEE Transactions on Communications, 1998, 46 (8): 1003- 1010. https://doi.org/10.1109/26.705396 Cited in this article [1]

15	YUAN P H, DUFFY K R, MÉDARD M. Near-optimal generalized decoding of polar-like codes[C]//2024 IEEE International Symposium on Information Theory (ISIT). Athens, Greece: IEEE, 2024: 2939-2944. Cited in this article [9]

16	ALAMDAR-YAZDI A , KSCHISCHANG F R . A simplified successive-cancellation decoder for polar codes[J]. IEEE Communications Letters, 2011, 15 (12): 1378- 1380. https://doi.org/10.1109/LCOMM.2011.101811.111480 Cited in this article [1]

17	SARKIS G , GIARD P , VARDY A , et al. Fast polar decoders: Algorithm and implementation[J]. IEEE Journal on Selected Areas in Communications, 2014, 32 (5): 946- 957. https://doi.org/10.1109/JSAC.2014.140514 Cited in this article [1]

18	HASHEMI S A , CONDO C , GROSS W J . Fast and flexible successive-cancellation list decoders for polar codes[J]. IEEE Transactions on Signal Processing, 2017, 65 (21): 5756- 5769. https://doi.org/10.1109/TSP.2017.2740204 Cited in this article [3]

19	ARDAKANI M H , HANIF M , ARDAKANI M , et al. Fast successive-cancellation-based decoders of polar codes[J]. IEEE Transactions on Communications, 2019, 67 (7): 4562- 4574. https://doi.org/10.1109/TCOMM.2019.2906232 Cited in this article [5]

20	SHEN L, WU Y P, XU Y, et al. Soft-output fast successive-cancellation list decoder for polar codes[C]//2025 IEEE Wireless Communications and Networking Conference (WCNC). Milan, Italy: IEEE, 2025: 1-6. Cited in this article [10]

21	TRIFONOV P . Efficient design and decoding of polar codes[J]. IEEE Transactions on Communications, 2012, 60 (11): 3221- 3227. https://doi.org/10.1109/TCOMM.2012.081512.110872 Cited in this article [2]

22	CONDO C, BIOGLIO V, LAND I. Generalized fast decoding of polar codes[C]//2018 IEEE Global Communications Conference (GLOBECOM). Abu Dhabi, United Arab Emirates: IEEE, 2018: 1-6. Cited in this article [1]