Low-Complexity Ordered Statistic Decoding Algorithm Based on Skipping Mechanisms

WANG Qianfan; GUO Yangeng; SONG Linqi; MA Xiao

doi:10.11999/JEIT250447

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

WANG Qianfan, GUO Yangeng, SONG Linqi, MA Xiao. Low-Complexity Ordered Statistic Decoding Algorithm Based on Skipping Mechanisms[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250447

Citation:

WANG Qianfan, GUO Yangeng, SONG Linqi, MA Xiao. Low-Complexity Ordered Statistic Decoding Algorithm Based on Skipping Mechanisms[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250447

Citation:

PDF( 6579 KB)

Low-Complexity Ordered Statistic Decoding Algorithm Based on Skipping Mechanisms

doi: 10.11999/JEIT250447 cstr: 32379.14.JEIT250447

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

1.
City University of Hong Kong, Hong Kong 999077, China
2.
City University of Hong Kong Shenzhen Research Institute, 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)

Received Date: 2025-05-21
Rev Recd Date: 2025-08-26

Available Online: 2025-09-02

Abstract

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

FullText(HTML)

References(38)

References

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