基于跳过机制的低复杂度顺序统计译码算法

王千帆; 郭延庚; 宋林琦; 马啸

doi:10.11999/JEIT250447

基于跳过机制的低复杂度顺序统计译码算法

doi: 10.11999/JEIT250447 cstr: 32379.14.JEIT250447

王千帆^{1, 2},
郭延庚³,
宋林琦^{1, 2, ,},
马啸³

1.
香港城市大学香港 999077
2.
香港城市大学深圳研究院深圳 518000
3.
中山大学计算机学院广州 510006

基金项目: 国家重点研发计划(2021YFA1000500)，国家自然科学基金(62301617, 62371411, 62471506)，广东省自然科学基金面上项目(2023A1515011056, 2025A1515011650)，港澳“青年科技人才托举工程”项目(QT-2025-048)

详细信息

作者简介:
王千帆：男，博士后，研究方向为信道编码及其在无线通信中的应用

郭延庚：男，本科生，研究方向为信道编码与译码技术

宋林琦：男，副教授，博士生导师，研究方向为人工智能和信息论领域的结合等

马啸：男，教授，博士生导师，研究方向为信息与编码理论、编码调制技术、无线通信和光通信等

通讯作者:
宋林琦　linqi.song@cityu.edu.hk

中图分类号: TN911.22
计量
- 文章访问数: 173
- HTML全文浏览量: 66
- PDF下载量: 21
- 被引次数: 0
出版历程
- 收稿日期: 2025-05-21
- 修回日期: 2025-08-27
- 网络出版日期: 2025-09-02

Low-complexity Ordered Statistic Decoding Algorithm Based on Skipping Mechanisms

WANG Qianfan^{1, 2},
GUO Yangeng³,
SONG Linqi^{1, 2
, ,},
MA Xiao³

1.
City University of Hong Kong, Hong Kong 999077, China
2.
Shenzhen Research Institute City University of Hong Kong, Shenzhen 518000, China
3.
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China

Funds: The National Key Research and Development Program (2021YFA1000500), The National Natural Science Foundation of China (62301617, 62371411, 62471506), Guangdong Basic and Applied Basic Research Foundation (2023A1515011056, 2025A1515011650), Young Talent Support Project of Guangzhou Association for Science and Technology (QT-2025-048)

摘要

摘要: 5G高可靠低时延(URLLC)场景和未来6G极高可靠极低时延(HRLLC)场景对于通信可靠性和时延等具有极其严格的需求，这给短码研究带来了新的机遇与挑战。该文聚焦于顺序统计译码(OSD)，针对其重编码次数过多的问题，分别提出了基于软信息和额外校验的重编码跳过机制，并进一步提出了结合软信息和额外校验的联合跳过机制。具体地，基于软信息的跳过机制是根据当前列表中最优候选的软度量来判断是否跳过测试错误模式(TEP)的重编码；基于额外校验的跳过机制则是将TEP的搜索维度从$ k $维扩展到$ k+\delta $维，从而引入额外的校验来跳过不合法TEP的重编码；联合跳过机制则将两者结合，先以软信息进行跳过判断，再通过额外校验进一步跳过非法TEP。数值结果显示，所提联合跳过机制可以有效减少重编码次数，并优于现有文献的跳过设计。特别地，所提联合跳过机制可以在中高信噪比区域将重编码次数从约670 000次降低至十余次，且几乎不损失纠错性能。
- 信道译码 /
- 顺序统计译码 /
- 跳过机制 /
- 额外校验
Abstract: Objective Ultra-Reliable Low-Latency Communication (URLLC) in 5G and the emerging Hyper-Reliable Low-Latency Communication (HRLLC) in 6G impose exceptionally stringent requirements on both reliability and end-to-end delay. These requirements create opportunities and challenges for short-length channel codes, particularly in scenarios where Maximum-Likelihood (ML) or near-ML decoding is desirable but computational complexity and latency are prohibitive. Ordered Statistic Decoding (OSD) is a universal near-ML decoding technique that can closely approach finite-length performance bounds. However, its re-encoding step suffers from combinatorial explosion, resulting in impractical complexity in high-throughput and low-latency systems. The excessive number of Test-Error-Pattern (TEP) re-encodings fundamentally restricts the deployment of OSD in URLLC and HRLLC contexts. To address this bottleneck, we design multiple efficient skip mechanisms that substantially reduce re-encoding operations while maintaining negligible performance degradation. Methods Three complementary skipping mechanisms are developed to prune the OSD re-encoding search: (1) Soft-information based skipping. Two criteria are introduced—Trivial and Dynamic Approximate Ideal (DAI), to compare the soft metric of each TEP against the minimum soft weight in the current list. Candidates with excessively large soft weights, which are unlikely to be correct, are skipped. Unlike prior work that evaluates only the first TEP at each Hamming weight increment, both criteria are applied to every candidate. The Trivial criterion ensures no performance loss by skipping only when a TEP’s soft metric exceeds the best-so-far. The DAI criterion incorporates an expected residual soft-weight compensation term over non-basis bits, enabling more aggressive skipping with minimal performance degradation. (2) Extra-parity skipping. The search dimension is expanded from $ k $ to $ k+\delta $ by appending the $ \delta $ most reliable non-basis bit positions to the test vector. Additional parity checks arising from the extended generator matrix eliminate invalid TEPs. Any candidate failing these extra parity constraints is bypassed. (3) Joint skipping. This approach integrates the two preceding mechanisms. Each partial TEP $ ({\boldsymbol{e}}_{\mathrm{L}},{\boldsymbol{e}}_{\delta })\in {\mathbb{F}}_{2}^{k+\delta } $ is first tested using the DAI rule and then subjected to the extra-parity check. Only candidates passing both criteria are re-encoded. Results and Discussions Extensive simulations on extended BCH $ \left[\mathrm{128,64}\right] $ and BCH $ \left[\mathrm{127,64}\right] $ codes over the BPSK-AWGN channel demonstrate the efficacy of the proposed skipping mechanisms. Soft-information skipping: When compared with conventional OSD using maximum flipping order $ t=4 $, the Trivial rule is found to reduce average re-encodings by 50%～90% across the SNR range. The DAI rule achieves an additional 60%～99% reduction beyond the Trivial rule. At SNR = 3 dB, the average number of re-encodings decreases from approximately $ 6.7\times {10}^{5} $ to $ 1.2\times {10}^{3} $, with negligible degradation in Frame-Error Rate (FER) (Fig. 1). Extra-parity skipping: For $ \delta =4 $, over $ 90 \% $ of re-encodings are eliminated uniformly across SNR values, thereby reducing dependence on channel conditions. This reduction is achieved without significant FER loss (Fig. 2). Joint skipping: The combined mechanism demonstrates superior performance over individual schemes. It reduces average re-encodings by an additional ～40% compared with the DAI rule alone, and by more than $ > 99.9 \% $ compared with extra-parity alone in high-SNR regimes. In this region, re-encodings decrease from $ \sim 6.7\times {10}^{5} $ to fewer than 100, while FER remains nearly identical to that of baseline OSD (Fig. 3). The joint skipping mechanism is further evaluated on BCH codes with different rates, including $ \left[\mathrm{127,36}\right] $, $ \left[\mathrm{127,64}\right] $, and $ \left[\mathrm{127,92}\right] $. In all cases, substantial reductions in re-encodings are consistently achieved with negligible performance degradation (Fig. 4). A comparative analysis with state-of-the-art schemes—including Probabilistic Sufficient/Necessary Conditions (PSC/PNC), Fast OSD (FOSD), and Order-Skipping OSD (OS-OSD)—shows that the proposed joint skipping OSD with $ \delta =4 $ achieves the lowest re-encoding count. Up to two orders of magnitude fewer re-encodings are observed relative to OS-OSD at low SNR, and superiority over FOSD is maintained at moderate SNR, while error-correction performance is preserved across all tested SNRs (Fig. 5). Conclusions To address the stringent reliability and latency requirements of 5G URLLC and future 6G HRLLC, this work presents novel skipping mechanisms for OSD that substantially reduce re-encoding complexity. For offline pre-computed TEPs, the soft-information, extra-parity, and joint skipping rules eliminate more than $ 99 \% $ of redundant re-encodings in typical operating regimes with negligible degradation in Frame-Error Rate (FER). In particular, the proposed joint skipping mechanism lowers the average re-encoding count from approximately $ 6.7\times {10}^{5} $ to only tens in the high-SNR region, thereby meeting practical latency constraints while preserving near-ML performance. These findings demonstrate the potential of the proposed skipping framework to enable high-performance short-block decoding in next-generation HRLLC.
- Channel decoding /
- Ordered Statistic Decoding (OSD) /
- Skipping mechanism /
- Extra-parity check

HTML全文

图 1 传统OSD, Trivial跳过OSD和DAI跳过OSD的性能比较

下载: 全尺寸图片幻灯片

图 2 $ \delta =\mathrm{1,2},4 $下的额外校验跳过OSD与传统OSD[19]性能比较

下载: 全尺寸图片幻灯片

图 3 $ \delta =\mathrm{1,2},4 $下联合跳过机制与分离跳过机制的性能对比

下载: 全尺寸图片幻灯片

图 4 联合跳过OSD与传统OSD性能对比

下载: 全尺寸图片幻灯片

图 5 联合跳过准则与其他跳过方案性能对比

下载: 全尺寸图片幻灯片

参考文献(38)

[1]	3GPP. Study on scenarios and requirements for next generation access technologies (release 14)[R/OL]. https://portal.3gpp.org/desktopmodules/Specifications/SpecificationDetails.aspx?specificationId=2996, 2017.
[2]	ITU. Framework and overall objectives of the future development of IMT for 2030 and beyond[R/OL]. https://www.itu.int/rec/R-REC-M.2160-0-202311-I/en, 2023.
[3]	ROWSHAN M, QIU Min, XIE Yixuan, et al. Channel coding toward 6G: Technical overview and outlook[J]. IEEE Open Journal of the Communications Society, 2024, 5: 2585–2685. doi: 10.1109/OJCOMS.2024.3390000.
[4]	TATARIA H, SHAFI M, MOLISCH A F, et al. 6G wireless systems: Vision, requirements, challenges, insights, and opportunities[J]. Proceedings of the IEEE, 2021, 109(7): 1166–1199. doi: 10.1109/JPROC.2021.3061701.
[5]	杨刚华, 何高宁, 陈睿荣, 等. 6G无线空口传输技术研究进展与展望[J]. 中国科学: 信息科学, 2024, 54(5): 1078–1113. doi: 10.1360/SSI-2023-0331. YANG Ganghua, HE Gaoning, CHEN Ruirong, et al. Progress and prospect of 6G wireless air-interface transmission technology research[J]. SCIENTIA SINICA Informationis, 2024, 54(5): 1078–1113. doi: 10.1360/SSI-2023-0331.
[6]	王雪, 孟姝宇, 钱志鸿. 面向6G全域融合的智能接入关键技术综述[J]. 电子与信息学报, 2024, 46(5): 1613–1631. doi: 10.11999/JEIT231224. WANG Xue, MENG Shuyu, and QIAN Zhihong. An overview of key technologies for intelligent access toward 6G full-domain convergence[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1613–1631. doi: 10.11999/JEIT231224.
[7]	GALLAGER R. Low-density parity-check codes[J]. IRE Transactions on Information Theory, 1962, 8(1): 21–28. doi: 10.1109/TIT.1962.1057683.
[8]	MACKAY D J C and NEAL R M. Near Shannon limit performance of low density parity check codes[J]. Electronics Letters, 1996, 33(6): 457–458. doi: 10.1049/el:19970362.
[9]	李二保, 雷菁, 徐富兵. 非规则LDPC度分布优化设计[J]. 电子与信息学报, 2008, 30(11): 2788–2791. doi: 10.3724/SP.J.1146.2007.00799. LI Erbao, LEI Jing, and XU Fubing. Design and optimization of degree distributions of irregular LDPC[J]. Journal of Electronics & Information Technology, 2008, 30(11): 2788–2791. doi: 10.3724/SP.J.1146.2007.00799.
[10]	FELSTROM A J and ZIGANGIROV K S. Time-varying periodic convolutional codes with low-density parity-check matrix[J]. IEEE Transactions on Information Theory, 1999, 45(6): 2181–2191. doi: 10.1109/18.782171.
[11]	PUSANE A E, SMARANDACHE R, VONTOBEL P O, et al. Deriving good LDPC convolutional codes from LDPC block codes[J]. IEEE Transactions on Information Theory, 2011, 57(2): 835–857. doi: 10.1109/TIT.2010.2095211.
[12]	WANG Qianfan, CAI Suihua, LIN Wenchao, et al. Spatially coupled LDPC codes via partial superposition and their application to HARQ[J]. IEEE Transactions on Vehicular Technology, 2021, 70(4): 3493–3504. doi: 10.1109/TVT.2021.3065052.
[13]	王千帆, 杨佳仪, 王寅楚, 等. 面向流式通信的耦合LDPC码研究综述[J]. 电子学报, 2024, 52(8): 2913–2932. doi: 10.12263/DZXB.20240167. WANG Qianfan, YANG Jiayi, WANG Yinchu, et al. A review of coupled LDPC codes for streaming communications[J]. Acta Electronica Sinica, 2024, 52(8): 2913–2932. doi: 10.12263/DZXB.20240167.
[14]	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. doi: 10.1109/TIT.2009.2021379.
[15]	牛凯. 极化码原理与应用[M]. 北京: 科学出版社, 2021: 56–60. NIU Kai. Principles and Applications of Polar Codes[M]. Beijing: Science Press, 2021: 56–60.
[16]	蔡穗华, 王义文, 白宝明, 等. 面向高可靠低时延通信的信道编码技术研究综述[J]. 电子学报, 2025, 53(2): 629–644. doi: 10.12263/DZXB.20240137. CAI Suihua, WANG Yiwen, BAI Baoming, et al. Channel coding techniques for ultra-reliable and low-latency communication[J]. Acta Electronica Sinica, 2025, 53(2): 629–644. doi: 10.12263/DZXB.20240137.
[17]	COŞKUN M C, DURISI G, JERKOVITS T, et al. Efficient error-correcting codes in the short blocklength regime[J]. Physical Communication, 2019, 34: 66–79. doi: 10.1016/j.phycom.2019.03.004.
[18]	SHIRVANIMOGHADDAM M, MOHAMMADI M S, ABBAS R, et al. Short block-length codes for ultra-reliable low latency communications[J]. IEEE Communications Magazine, 2019, 57(2): 130–137. doi: 10.1109/MCOM.2018.1800181.
[19]	FOSSORIER M P C and LIN Shu. Soft-decision decoding of linear block codes based on ordered statistics[J]. IEEE Transactions on Information Theory, 1995, 41(5): 1379–1396. doi: 10.1109/18.412683.
[20]	DORSCH B. A decoding algorithm for binary block codes and J-Ary output channels (Corresp. )[J]. IEEE Transactions on Information Theory, 1974, 20(3): 391–394. doi: 10.1109/TIT.1974.1055217.
[21]	YUE Chentao, SHIRVANIMOGHADDAM M, PARK G, et al. Probability-based ordered-statistics decoding for short block codes[J]. IEEE Communications Letters, 2021, 25(6): 1791–1795. doi: 10.1109/LCOMM.2021.3058978.
[22]	朱士信, 虞艺超. 使用边际信息降低复杂度的分阶统计软判决译码法[J]. 电子与信息学报, 2013, 35(7): 1682–1686. doi: 10.3724/SP.J.1146.2012.01595. ZHU Shixin and YU Yichao. Reduce complexity of ordered statistics soft-decision decoding by side information[J]. Journal of Electronics & Information Technology, 2013, 35(7): 1682–1686. doi: 10.3724/SP.J.1146.2012.01595.
[23]	WANG Yiwen, LIANG Jifan, and MA Xiao. Local constraint-based ordered statistics decoding for short block codes[C]. 2022 IEEE Information Theory Workshop, Mumbai, India, 2022: 107–112. doi: 10.1109/ITW54588.2022.9965916.
[24]	LIANG Jifan, WANG Yiwen, CAI Suihua, et al. A low-complexity ordered statistic decoding of short block codes[J]. IEEE Communications Letters, 2023, 27(2): 400–403. doi: 10.1109/LCOMM.2022.3222819.
[25]	CHEN Yanzhi, LIANG Jifan, WANG Qianfan, et al. A new joint source-channel coding scheme with overlay spread spectrum transmission[C]. 2023 International Conference on Wireless Communications and Signal Processing, Hangzhou, China, 2023: 239–244. doi: 10.1109/WCSP58612.2023.10404761.
[26]	WANG Qianfan, CHEN Yanzhi, LIANG Jifan, et al. A new joint source-channel coding for short-packet communications[J]. IEEE Transactions on Communications, 2024, 72(1): 28–37. doi: 10.1109/TCOMM.2023.3320699.
[27]	WANG Qianfan, CHEN Yanzhi, LIANG Jifan, et al. A new joint source-channel coding in the short blocklength regime[C]. 2023 IEEE Globecom Workshops, Kuala Lumpur, Malaysia, 2023: 1566–1571. doi: 10.1109/GCWkshps58843.2023.10464813.
[28]	WANG Qianfan, WANG Yiwen, WANG Yixin, et al. Random staircase generator matrix codes: Coding theorem, performance analysis, and code design[J]. IEEE Transactions on Information Theory, 2025, 71(5): 3497–3509. doi: 10.1109/TIT.2025.3541734.
[29]	WANG Yiwen, LIANG Jifan, WANG Qianfan, et al. Representative ordered statistics decoding of staircase matrix codes[J]. IEEE Transactions on Communications, 2025, 73(4): 2148–2158. doi: 10.1109/TCOMM.2024.3478114.
[30]	WANG Yiwen, WANG Qianfan, LIANG Jifan, et al. Representative OSD with local constraints of ca-polar codes[J]. Chinese Journal of Electronics, 2025, 34(4): 1111–1119. doi: 10.23919/cje.2024.00.220.
[31]	王义文, 王千帆马啸. 强干扰环境下无速率随机码编译码方案及其性能分析[J]. 电子与信息学报, 2024, 46(10): 4017–4023. doi: 10.11999/JEIT230879. WANG Yiwen, WANG Qianfan, and MA Xiao. Rateless random coding scheme and performance analysis in strong interference environments[J]. Journal of Electronics & Information Technology, 2024, 46(10): 4017–4023. doi: 10.11999/JEIT230879.
[32]	JIN Wenyi and FOSSORIER M. Probabilistic sufficient conditions on optimality for reliability based decoding of linear block codes[C]. 2006 IEEE International Symposium on Information Theory, Seattle, USA, 2006: 2235–2239. doi: 10.1109/ISIT.2006.261948.
[33]	WU Yingquan and HADJICOSTIS C N. Soft-decision decoding of linear block codes using preprocessing and diversification[J]. IEEE Transactions on Information Theory, 2007, 53(1): 378–393. doi: 10.1109/TIT.2006.887478.
[34]	CHOI C and JEONG J. Fast and scalable soft decision decoding of linear block codes[J]. IEEE Communications Letters, 2019, 23(10): 1753–1756. doi: 10.1109/LCOMM.2019.2927218.
[35]	LI Xihao, CHEN Wenhao, CHEN Li, et al. Order skipping ordered statistics decoding and its performance analysis[C]. 2024 IEEE Information Theory Workshop, Shenzhen, China, 2024: 448–453. doi: 10.1109/ITW61385.2024.10807042.
[36]	LIANG Jifan and MA Xiao. A random coding approach to performance analysis of the ordered statistic decoding with local constraints[EB/OL]. https://doi.org/10.48550/arXiv.2401.16709, 2024.
[37]	MA Xiao. Guessing what, noise or codeword?[C]. 2024 IEEE Information Theory Workshop, Shenzhen, China, 2024: 460–465. doi: 10.1109/ITW61385.2024.10806987.
[38]	ZHENG Xiangping and MA Xiao. A universal list decoding algorithm with application to decoding of polar codes[J]. IEEE Transactions on Information Theory, 2025, 71(2): 975–995. doi: 10.1109/TIT.2024.3509673.