Belief Propagation-Ordered Statistics Decoding Algorithm with Parameterized List Structures

LIANG Jifan; WANG Qianfan; SONG Linqi; LI Lvzhou; MA Xiao

doi:10.11999/JEIT250552

Article Contents

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

LIANG Jifan, WANG Qianfan, SONG Linqi, LI Lvzhou, MA Xiao. Belief Propagation-Ordered Statistics Decoding Algorithm with Parameterized List Structures[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250552

Citation:

LIANG Jifan, WANG Qianfan, SONG Linqi, LI Lvzhou, MA Xiao. Belief Propagation-Ordered Statistics Decoding Algorithm with Parameterized List Structures[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250552

Citation:

PDF( 1994 KB)

Belief Propagation-Ordered Statistics Decoding Algorithm with Parameterized List Structures

doi: 10.11999/JEIT250552 cstr: 32379.14.JEIT250552

LIANG Jifan^{1, 2},
WANG Qianfan^{3, 4
,
,},
SONG Linqi^{3, 4},
LI Lvzhou¹,
MA Xiao^{1, 2}

1.
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510006, China
2.
Guangdong Province Key Laboratory of Information Security Technology, Guangzhou 510006, China
3.
City University of Hong Kong, Hong Kong 999077, China
4.
City University of Hong Kong Shenzhen Research Institute, Shenzhen 518057, China

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

Received Date: 2025-06-16
Rev Recd Date: 2025-09-15

Available Online: 2025-09-21

Abstract

Abstract

Objective Traditional Belief Propagation–Ordered Statistics Decoding (BP-OSD) algorithms for quantum error-correcting codes often rely on a single normalization factor ($ \alpha $) in the Belief Propagation (BP) stage, which restricts the search space and limits decoding performance. An enhanced BP-OSD algorithm is presented to address this limitation by employing a list of candidate $ \alpha $ values. The central idea is to perform BP decoding iteratively for multiple $ \alpha $ values, with the resulting posterior probabilities post-processed by Ordered Statistics Decoding (OSD). To balance performance gains with computational tractability, the multi-$ \alpha $ BP-OSD process is embedded within a two-stage framework: the more computationally intensive parameter-listed decoding is activated only when an initial BP decoding with a fixed $ {\alpha }_{0} $ fails. This design broadens the parameter search to improve decoding performance, while conditional activation ensures that computational complexity remains manageable, particularly at low physical error rates. Methods The proposed enhanced BP-OSD algorithm (Algorithm 1) introduces a two-stage decoding process. In the first stage, decoding is attempted using standard BP with a single predetermined normalization factor ($ {\alpha }_{0} $), providing a computationally efficient baseline. If this attempt fails to produce a valid syndrome match, the second stage is activated. In the second stage, parameter listing is employed: BP decoding is executed independently across a predefined list of $ L $ distinct normalization factors $ \left\{{\alpha }_{1},{\alpha }_{2}, \cdots,{\alpha }_{L}\right\} $. Each run generates a set of posterior probabilities corresponding to a different BP operational point. These posterior probabilities are then individually post-processed by an OSD module, forming a pool of candidate error patterns. The final decoded output is selected from this pool according to the maximum likelihood criterion, or the minimum Hamming weight criterion under a depolarizing channel. Complexity analysis shows that this conditional two-stage design ensures that the average computational cost remains comparable to that of standard BP decoding, particularly at low physical error rates where the first stage frequently succeeds. Results and Discussions The effectiveness of the proposed algorithm is evaluated through Monte Carlo simulations on both Surface codes $ \left[\kern-0.15em\left[ {2{d}^{2}-2d+\mathrm{1,1},d} \right]\kern-0.15em\right] $ and Quantum Low-Density Parity-Check (QLDPC) codes $ \left[\kern-0.15em\left[ {\mathrm{882,24}} \right]\kern-0.15em\right] $ under a depolarizing channel. For Surface codes, the enhanced BP-OSD algorithm achieves a substantially lower logical error rate compared with both the Minimum-Weight Perfect Matching (MWPM) algorithm and the original BP algorithm (Fig. 4(a)). The error threshold is improved from approximately $ 15.5\% $ (MWPM) to about $ 18.3\% $ with the proposed method. The average decoding time comparison in Fig. 4(b) demonstrates that, particularly at low physical error rates, the proposed algorithm maintains a decoding speed comparable to the original BP algorithm. This efficiency results from the two-stage design, in which the more computationally intensive parameter-listed search is activated only when required. For QLDPC codes (Fig. 5(a), the proposed algorithm outperforms both the original BP and BP-OSD algorithms in terms of logical error rate, even when a smaller OSD candidate list per α value is employed. As shown in Table 3, increasing the parameter list size L (e.g., $ L=\mathrm{4,8},16 $) improves decoding performance, although the gains diminish as L grows. This observation supports the choice of L = 16 as an effective balance between performance and complexity. Furthermore, the activation probability of the second stage (Table 2) decreases rapidly as the physical error rate declines, confirming the efficiency of the two-stage framework. Conclusions An enhanced BP-OSD algorithm for quantum error-correcting codes is presented, featuring a parameter-listing strategy for the normalization factor ($ \alpha $) in the BP stage. Unlike conventional approaches that rely on a single $ \alpha $, the proposed method explores multiple $ \alpha $ values, with the resulting posterior probabilities processed by the OSD module to select the most likely output. This systematic expansion of the search space improves decoding performance. To control computational overhead, a two-stage decoding mechanism is employed: the parameter-listed BP-OSD is activated only when an initial BP decoding with a fixed $ {\alpha }_{0} $ fails. Complexity analysis, supported by numerical simulations, shows that the average computational cost of the proposed algorithm remains comparable to that of standard BP decoding in low physical error rate regimes. Monte Carlo simulations further demonstrate its efficacy. For Surface codes, the enhanced BP-OSD achieves lower logical error rates than the MWPM algorithm and raises the error threshold from approximately 15.5% to 18.3%. For QLDPC codes, it exceeds both the original BP and BP-OSD algorithms in logical error rate performance, even with a reduced OSD candidate list size in the second stage. Overall, the proposed algorithm provides a promising pathway toward high-performance, high-threshold quantum error correction by balancing decoding power with operational efficiency, highlighting its potential for practical applications.

FullText(HTML)

References(38)

References

[1]	ZHANG Shihao and LI Lvzhou. A brief introduction to quantum algorithms[J]. CCF Transactions on High Performance Computing, 2022, 4(1): 53–62. doi: 10.1007/s42514-022-00090-3.
[2]	GOTTESMAN D. Stabilizer codes and quantum error correction[D]. [Ph. D. dissertation], California Institute of Technology, 1997.
[3]	NIELSEN M A and CHUANG I L. Quantum Computation and Quantum Information[M]. 10th ed. Cambridge: Cambridge University Press, 2010. .
[4]	KITAEV A Y. Fault-tolerant quantum computation by anyons[J]. Annals of Physics, 2003, 303(1): 2–30. doi: 10.1016/S0003-4916(02)00018-0.
[5]	DENNIS E, KITAEV A, LANDAHL A, et al. Topological quantum memory[J]. Journal of Mathematical Physics, 2002, 43(9): 4452–4505. doi: 10.1063/1.1499754.
[6]	MACKAY D J C, MITCHISON G, and MCFADDEN P L. Sparse-graph codes for quantum error correction[J]. IEEE Transactions on Information Theory, 2004, 50(10): 2315–2330. doi: 10.1109/TIT.2004.834737.
[7]	赵生妹, 朱修利, 肖宇. 一种基于BIBD的量子LDPC码构造新方法[J]. 电子与信息学报, 2011, 33(1): 218–222. doi: 10.3724/SP.J.1146.2009.01482. ZHAO Shengmei, ZHU Xiuli, and XIAO Yu. A novel construction of quantum LDPC codes based on balanced incomplete block designs[J]. Journal of Electronics & Information Technology, 2011, 33(1): 218–222. doi: 10.3724/SP.J.1146.2009.01482.
[8]	邢莉娟, 李卓, 王新梅, 等. CSS型量子卷积码的编译码方法[J]. 电子与信息学报, 2008, 30(10): 2388–2391. doi: 10.3724/SP.J.1146.2007.00503. XING Lijuan, LI Zhuo, WANG Xinmei, et al. Encoding and decoding of CSS-type quantum convolutional codes[J]. Journal of Electronics & Information Technology, 2008, 30(10): 2388–2391. doi: 10.3724/SP.J.1146.2007.00503.
[9]	PANTELEEV P and KALACHEV G. Quantum LDPC codes with almost linear minimum distance[J]. IEEE Transactions on Information Theory, 2022, 68(1): 213–229. doi: 10.1109/TIT.2021.3119384.
[10]	TILLICH J P and ZEMOR G. Quantum LDPC codes with positive rate and minimum distance proportional to n^1/2[C]. IEEE International Symposium on Information Theory, Seoul, Korea (South), 2009: 799–803. doi: 10.1109/ISIT.2009.5205648.
[11]	PANTELEEV P and KALACHEV G. Asymptotically good quantum and locally testable classical LDPC codes[C]. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, 2022: 375–388. doi: 10.1145/3519935.3520017.
[12]	LEVERRIER A and ZÉMOR G. Quantum Tanner codes[C]. 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), Denver, USA, 2022: 872–883. doi: 10.1109/FOCS54457.2022.00117.
[13]	DINUR I, HSIEH M H, LIN T C, et al. Good quantum LDPC codes with linear time decoders[C]. Proceedings of the 55th Annual ACM Symposium on Theory of Computing, Orlando, USA, 2023: 905–918. doi: 10.1145/3564246.3585101.
[14]	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.
[15]	PANTELEEV P and KALACHEV G. Degenerate quantum LDPC codes with good finite length performance[J]. Quantum, 2021, 5: 585. doi: 10.22331/q-2021-11-22-585.
[16]	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.
[17]	LIANG Jifan and MA Xiao. A random coding approach to performance analysis of the ordered statistic decoding with local constraints[J]. arXiv preprint arXiv: 2401.16709, 2024. doi: 10.48550/arXiv.2401.16709. (不确定本条文献类型及格式是否正确,请确认).
[18]	LIANG Jifan, WANG Qianfan, LI Lvzhou, et al. The BP-LCOSD algorithm for toric codes[C]. IEEE International Symposium on Information Theory Workshops (ISIT-W), Athens, Greece, 2024: 1–6. doi: 10.1109/ISIT-W61686.2024.10591758.
[19]	LIANG Jifan, WANG Qianfan, LI Lvzhou, et al. A low-complexity BP-OSD algorithm for quantum LDPC codes[J]. The European Physical Journal Special Topics, 2025. doi: 10.1140/epjs/s11734-025-01712-x. (查阅网上资料,未找到本条文献卷号和页码信息,请确认).
[20]	LIANG Jifan, WANG Qianfan, LI Lvzhou, et al. A high-performance list decoding algorithm for surface codes with erroneous syndrome[J]. arXiv preprint arXiv: 2409.06979, 2024. doi: 10.48550/arXiv.2409.06979. (不确定本条文献类型及格式是否正确,请确认).
[21]	HIGGOTT O and BREUCKMANN N P. Improved single-shot decoding of higher-dimensional hypergraph-product codes[J]. PRX Quantum, 2023, 4(2): 020332. doi: 10.1103/PRXQuantum.4.020332.
[22]	WANG Qifan, 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.
[23]	WANG Qifan, CHEN Yanzhi, LIANG Jifan, et al. A new joint source-channel coding in the short blocklength regime[C]. 2023 IEEE Globecom Workshops (GC Wkshps), Kuala Lumpur, Malaysia, 2023: 1566–1571. doi: 10.1109/GCWkshps58843.2023.10464813.
[24]	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 (WCSP), Hangzhou, China, 2023: 239–244. doi: 10.1109/WCSP58612.2023.10404761.
[25]	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.
[26]	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.
[27]	WANG Yiwen, WANG Qianfan, LIANG Jifan, et al. Representative ordered statistics decoding of polar codes[C]. IEEE 99th Vehicular Technology Conference (VTC2024-Spring), Singapore, Singapore, 2024: 1–5. doi: 10.1109/VTC2024-Spring62846.2024.10683273.
[28]	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.
[29]	王义文, 王千帆, 马啸. 强干扰环境下无速率随机码编译码方案及其性能分析[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.
[30]	吕毅博, 胡伟, 王琳. Beyond-BP译码算法综述: 原理与应用[J]. 电子与信息学报, 2017, 39(6): 1503–1514. doi: 10.11999/JEIT161288. LV Yibo, HU Wei, and WANG Lin. Survey of beyond-BP decoding algorithms: Theory and applications[J]. Journal of Electronics & Information Technology, 2017, 39(6): 1503–1514. doi: 10.11999/JEIT161288.
[31]	MACKAY D J C. Information Theory, Inference and Learning Algorithms[M]. Cambridge: Cambridge University Press, 2003. .
[32]	WAINWRIGHT M J, JAAKKOLA T, and WILLSKY A S. Tree-based reparameterization for approximate inference on loopy graphs[C]. Proceedings of the 15th International Conference on Neural Information Processing Systems: Natural and Synthetic, Vancouver, Canada, 2001: 1001–1008. doi: 10.5555/2980539.2980668.
[33]	POULIN D and CHUNG Y. On the iterative decoding of sparse quantum codes[J]. Quantum Information & Computation, 2008, 8(10): 987–1000. doi: 10.5555/2016985.2016993.
[34]	FOSSORIER M P C. Iterative reliability-based decoding of low-density parity check codes[J]. IEEE Journal on Selected Areas in Communications, 2001, 19(5): 908–917. doi: 10.1109/49.924874.
[35]	ISAKA M, FOSSORIER M P C, and IMAI H. On the suboptimality of iterative decoding for turbo-like and LDPC codes with cycles in their graph representation[J]. IEEE Transactions on Communications, 2004, 52(5): 845–854. doi: 10.1109/TCOMM.2004.826236.
[36]	JIANG Ming, ZHAO Chunming, XU Enyang, et al. Reliability-based iterative decoding of LDPC codes using likelihood accumulation[J]. IEEE Communications Letters, 2007, 11(8): 677–679. doi: 10.1109/LCOMM.2007.070450.
[37]	LAI C Y and KUO K Y. Log-domain decoding of quantum LDPC codes over binary finite fields[J]. IEEE Transactions on Quantum Engineering, 2021, 2: 2103615. doi: 10.1109/TQE.2021.3113936.
[38]	FOWLER A G. Minimum weight perfect matching of fault-tolerant topological quantum error correction in average O(1) parallel time[J]. Quantum Information & Computation, 2015, 15(1/2): 145–158. doi: 10.5555/2685188.2685197.