基于奇偶校验和循环冗余校验的增强Fast-SCL译码算法

Enhanced fast-SCL decoding based on parity check and cyclic redundancy check

摘要

极化码主流的快速串行消除列表（Fast-SCL）译码算法虽能实现低时延，但在中短码长下性能较差。针对该问题，提出了一种结合奇偶校验（parity check, PC）与循环冗余校验（CRC）的Fast-SCL算法。在Fast-SCL算法中引入PC位以实现早期的路径验证，提升路径选择的可靠性；同时，在校验位总数不变的前提下，考虑PC位与CRC位的多种组合方式。仿真结果表明，在短码长、帧错误率（FER）为10⁻²的条件下，与原始的CRC辅助Fast-SCL算法相比，该算法性能增益最高可达0.35 dB，计算复杂度最多可降低10%。

Abstract

The fast successive cancellation list (Fast-SCL) decoding algorithm for polar codes can achieve low latency, but still performs poorly under medium and short code lengths. To deal with this issue, this paper proposes an improved Fast-SCL algorithm by combining parity check (PC) and cyclic redundancy check (CRC). Specifically, PC bits are introduced into the Fast-SCL algorithm to enable real-time path verification, which makes the path selection more reliable. Additionally, with the same total number of check bits, various combinations of PC bits and CRC bits are considered. The simulation results demonstrate that the proposed algorithm achieves a performance gain of 0.35 dB and a complexity reduction of 10% compared to the original CRC-assisted Fast-SCL algorithm under the short code lengths with the frame error rate (FER) being 10⁻².

关键词

极化码 / 特殊节点 / 快速串行消除列表 / 奇偶校验 / 循环冗余校验

Key words

polar code / special nodes / Fast-SCL / parity check / cyclic redundancy check

参考文献

[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.

[2] Tal I, Vardy A. List decoding of polar codes[J].IEEE Transactions on Information Theory, 2015, 61(5): 2213-2226.

[3] Niu Kai, Chen Kai. CRC-aided decoding of polar codes[J].IEEE Communications Letters, 2012, 16(10): 1668-1671.

[4] Chen Jie, Chen Yu, Jayasinghe K, et al. Distributing CRC bits to aid polar decoding[C]//2017 IEEE Globecom Workshops. Singapore: IEEE, 2017: 1-6.

[5] Guo Jianfeng, Shi Zhiping, Liu Zilong, et al. Multi-CRC polar codes and their applications[J].IEEE Communications Letters, 2016, 20(2): 212-215.

[6] Wang Tao, Qu Daiming, Jiang Tao. Parity-check-concatenated polar codes[J].IEEE Communications Letters, 2016, 20(12): 2342-2345.

[7] Yu Qingping, Shi Zhiping, Yan Qinhuai, et al. Hybrid parity-check and CRC aided SCL decoding for polar codes[C]//2016 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). Chengdu: IEEE, 2016: 711-716.

[8] Li Wanzhen, He Zhongqiu. An efficient CRC-aided parity-check concatenated polar coding[C]//2021 IEEE Asia Conference on Information Engineering. Sanya: IEEE, 2021: 1-5.

[9] Alamdar-Yazdi A, Kschischang F R. A simplified successive-cancellation decoder for polar codes[J].IEEE Communications Letters, 2011, 15(12): 1378-1380.

[10] 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.

[11] Sarkis G, Giard P, Vardy A, et al. Fast list decoders for polar codes[J].IEEE Journal on Selected Areas in Communications, 2016, 34(2): 318-328.

[12] Hashemi S A, Condo C, Gross W J. A fast polar code list decoder architecture based on sphere decoding[J].IEEE Transactions on Circuits and Systems I: Regular Papers, 2016, 63(12): 2368-2380.

[13] 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.

[14] Ye Longjian, Zhai Xiongfei, Zeng Zifeng, et al. High-throughput polar code SCL decoding with dynamically configurable pipeline architecture[C]//2023 IEEE/CIC International Conference on Communications in China. Dalian: IEEE, 2023: 1-6.

[15] Zheng Haotian, Balatsoukas-Stimming A, Cao Zizheng, et al. Implementation of a high-throughput fast-SSC polar decoder with sequence repetition node[C]//2020 IEEE Workshop on Signal Processing Systems. Coimbra: IEEE, 2020: 1-6.

[16] Jeong S L, Bae J H, Sunwoo M H. Fast multibit decision polar decoder for successive-cancellation list decoding[J].Journal of Signal Processing Systems, 2021, 93(1): 127-136.

[17] 张宇 . Polar码译码算法研究及FPGA实现[D]. 成都: 电子科技大学,2023.

[18] Zhang Yu . The research and FPGA implementation of polar code decoding algorithm[D]. Chengdu: University of Electronic Science and Technology of China,2023. (in Chinese)

[19] 曾子峰 . 极化码低时延SCL译码器研究与设计[D]. 广州: 广东工业大学,2025.

[20] Zeng Zifeng . Research and design of low-latency SCL decoder for polar codes[D]. Guangzhou: Guangdong University of Technology,2025. (in Chinese)

[21] 王涛, 屈代明, 江涛 . 降低SCL译码错误的级联极化码[J].中兴通讯技术, 2019, 25(1): 5-11.

[22] Wang Tao, Qu Daiming, Jiang Tao . Concatenated polar codes for SCL decoding error reduction[J].ZTE Technology Journal, 2019, 25(1): 5-11. (in Chinese)

基金资助

国家自然科学基金(62301166)

国家自然科学基金(62471151)

国家自然科学基金(U2001203)

国家自然科学基金(62371101)

广州市科技计划项目(2025A04J2904)

广东省重点领域研发计划“芯片、软件与计算（芯片类）”专项计划(2021B1101270001)