A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes
-
摘要: 利用截短输入消息构造校验节点(Check Node, CN)的网格图，可以实现多进制低密度奇偶校验(Low-Density Parity-Check, LDPC)码CN更新的高效并行处理。然而，该类译码算法的变量节点(Variable Node, VN)更新过程通常以串行方式逐一处理候选域元素，制约了译码复杂度的进一步降低。为此，该文提出了一种双网格图消息传递的多进制LDPC码译码算法。该算法在CN网格图更新的基础上，构造了基于截短输入消息的VN网格图，通过对VN网格图节点逐行剪枝，并差异化更新输出向量，实现了VN更新的高效并行处理。实验结果表明，在相同CN网格图消息传递方法下，所提VN并行更新方法较原始VN更新显著降低了计算复杂度，且纠错性能和收敛速度基本一致；与近似置信传播译码算法相比，所提译码算法具有相近的译码性能和更低的复杂度。
-
关键词:
- 多进制低密度奇偶校验码 /
- 截短消息 /
- 双网格图 /
- 消息传递 /
- 变量节点
Abstract:Objective Due to their capacity approaching performance, Low Density Parity-Check (LDPC) codes have been widely applied to wireless communication and data storage systems. Compared to their binary counterparts, Non-Binary LDPC (NB-LDPC) codes with short or moderate code lengths have been demonstrated to achieve superior error performance under non-binary Belief Propagation (BP) decoding. However, the computational complexity of Check Node (CN) update of the optimal BP decoding is too complex for practical applications. Recently, many works have been presented to perform updates of CNs based on truncated messages, rather than full-length reliability messages, to significantly reduce the computational complexity of CN updates. Most of them construct the trellis of a CN based on the truncated input vectors, called truncated-trellis, such that CN updates are efficiently processed in parallel based on the selected candidate paths. These paths generally contain only a small number of deviation nodes, and such deviation nodes usually have high reliability. However, the Variable Node (VN) update in most decoding algorithms based on CN truncated-trellis still sequentially processes each element in the input vectors of each VN by the elementary steps. When the CN update is simplified, the complexity of the VN update may primarily determine the overall computational complexity. To address the above issues, this paper proposes the Dual-Trellis Min-Sum (DTMS) decoding algorithm. By further introducing truncated-trellises for VNs and updating the output messages of CNs and VNs in parallel, respectively, it further improves the decoding efficiency, while maintaining the similar decoding performance. Methods The different contributions of nodes in the CN truncated-trellis of the Pruning path Min-Sum (PMS) decoding algorithm on the selected highly reliable candidate paths are first analyzed, and it reveals that the selected highly reliable paths are primarily determined by the deviation nodes from the first few rows of the trellis of a CN, especially the second row. Thereby, it is not critical to update and sort every element of each output vector of one VN during the VN update. Next, a new trellis of one VN is constructed, and highly reliable elements over this trellis shared by all the output vectors of this VN are searched using a row-wise pruning strategy, such that the conventional element-wise VN updating procedure is transformed into a trellis-based parallel updating process based on an extra column in the trellis. In this basis, the unequal protection for the reliability values of each VN output vector is conducted, e.g., only the first few elements in each output vector of VN are updated and arranged, and the rest elements of each output vector are directly set to a compensation value. As a result, the computational complexity required for less reliable elements during each VN update can be significantly reduced, while retaining the crucial messages. Results and Discussions Experimental results show that compared with the PMS decoding algorithm using the original VN updating procedure, the proposed DTMS decoding algorithm maintains almost the same Bit Error Rate (BER) performance and convergence speed for decoding NB-LDPC codes under different finite fields, code lengths, and code construction methods ( Figs. 3 –7 ). Meanwhile, the number of real-domain operations required for the proposed simplified VN updates is reduced by approximately 71.8% on average (Table 2 ). In addition, the error-correction performance and convergence speed of the proposed DTMS decoding algorithm are close to those of the sub-optimal BP decoding algorithms (Figs. 3 –7 ) with relatively low computational complexity (Table 3 ). The average performance gap of the DTMS decoding algorithm from the optimal BP decoding algorithm is only about 0.11 dB (Figs. 3 –7 ). Thus, optimizing the VN updating is an effective way to further reduce the decoding complexity of truncated-trellis-based message-passing decoding algorithms.Conclusions This paper proposes a DTMS decoding algorithm to reduce the computational complexity of VN update in truncated-trellis-based decoding algorithms for NB-LDPC codes. Based on the CN updating process of the PMS decoding algorithm, the proposed algorithm further constructs a truncated-trellis and introduces the unequal protection scheme for VN update, such that the output vectors of each VN can be efficiently updated in parallel. Experimental results show that, under the same CN trellis-based update, the proposed parallel VN updating method significantly reduces the computational complexity compared with the original VN updating method, while maintaining similar decoding performance. Moreover, the proposed DTMS decoding algorithm performs closely to the sub-optimal BP decoding algorithms with similar convergence speed and lower complexity. In future studies, it will be interesting to further exploit the adaptive pruning strategies for the VN parallel updates. Based on the distribution of field elements from different iterations, less reliable field elements can be adaptively eliminated to reduce the set of candidate field elements, which may further reduce the complexity of VN update with negligible performance loss. -
表 1 各种译码算法在单次迭代下的计算复杂度
译码算法 模块 有限域下操作次数 实数域下操作次数 DTMS CN $ (3\delta +2m){n}_{\text{m}}+(8{n}_{\text{s}}-13)m $ $ (\rho +{n}_{\text{s}})\left\lceil {\log }_{2}{n}_{\text{s}}\right\rceil m+(4{n}_{\text{l}}+4{n}_{\text{s}}-6)m $ VN $ \delta (n_{\text{m}}^{2}+{s}_{\text{num}}{n}_{\text{m}}) $ $ n{n}_{\text{m}}\left\lceil {\log }_{2}{n}_{\text{m}}\right\rceil +({n}_{\text{m}}+2{s}_{\text{num}}+2{n}_{\text{vr}}-3)\delta $ PMS[20] CN $ (3\delta +2m){n}_{\text{m}}+(8{n}_{\text{s}}-13)m $ $ (\rho +{n}_{\text{s}})\left\lceil {\log }_{2}{n}_{\text{s}}\right\rceil m+(4{n}_{\text{l}}+4{n}_{\text{s}}-6)m $ VN $ (3\delta -4n)(5n_{\text{m}}^{2}/2-3{n}_{\text{m}}/2)+nn_{\text{m}}^{2} $ $ (3\delta -4n){n}_{\text{m}}\left\lceil {\log }_{2}{n}_{\text{m}}\right\rceil +(10\delta -8n){n}_{\text{m}}-n $ EMS[11] CN $ (3\delta -6m)({n}_{\text{m}}/2+3n_{\text{m}}^{2}/2+1)+2\delta {n}_{\text{m}} $ $ (3\delta -6m)(3{n}_{\mathrm{m}}+2{n}_{\mathrm{m}}\left\lceil {\log }_{2}{n}_{\mathrm{m}}\right\rceil ) $ VN $ (3\delta -4n)(5n_{\text{m}}^{2}/2-3{n}_{\text{m}}/2)+nn_{\text{m}}^{2} $ $ (3\delta -4n){n}_{\text{m}}\left\lceil {\log }_{2}{n}_{\text{m}}\right\rceil +(10\delta -8n){n}_{\text{m}}-n $ FMS[16] CN $ (3\delta +2m){n}_{\text{m}}+8\delta -13m $ $ 14\delta -15m $ VN $ (3\delta -4n)(5n_{\text{m}}^{2}/2-3{n}_{\text{m}}/2)+nn_{\text{m}}^{2} $ $ (3\delta -4n){n}_{\text{m}}\left\lceil {\log }_{2}{n}_{\text{m}}\right\rceil +(10\delta -8n){n}_{\text{m}}-n $ T-EMS[13] CN $ m\sum \limits_{w=1}^{{n}_{\text{c}}}(w-1)\left(\begin{array}{c}q-1\\w\end{array}\right){({{n}_{\text{r}}})}^{w}+\delta (5q-1) $ $ \begin{aligned}\;&3\delta (q-1)+\delta (q-1){n}_{\text{r}}+m\sum \limits_{w=2}^{{n}_{\text{c}}}w\left(\begin{array}{l}q-1\\w\end{array}\right)({{n}_{\text{r}}})^{w}\\& +\delta q-m(q-1)(n_{\text{r}}^{2}+{n}_{\text{r}})/2\end{aligned} $ VN 0 $ 2\delta q+(2\delta +n)(q-1) $ TMM[14] CN $ m(q-1)(q-2)/2+\delta (5q-1) $ $ \delta q+(3\delta +qm-5m)(q-1) $ VN 0 $ 2\delta q+(2\delta +n)(q-1) $ 
下载: 导出CSV
表 2 不同NB-LDPC码下所提简化VN更新与原始 VN 更新在单次迭代中所需的总操作次数
码字 VN更新方法 有限域下
操作次数实数域下
操作次数GF(8)上的( 1536 ,1344 )本文方法 196608 92160 原始方法[11] 442368 293376 GF(16)上的(522, 435) 本文方法 125280 39933 原始方法[11] 303804 114318 GF(32)上的(837, 726) 本文方法 1124928 164052 原始方法[11] 4339008 856251 GF(64)上的(96, 80) 本文方法 64512 12480 原始方法[11] 142848 30624 GF(256)上的(255, 223) 本文方法 1240320 94860 原始方法[11] 5385600 587265
下载: 导出CSV
表 3 不同NB-LDPC码下各种译码算法在单次迭代中所需的整体操作次数
码字 译码算法 有限域下操作次数 实数域下操作次数 GF(8)上的
(1536 ,1344 )DTMS 275520 112512 EMS[11] 958080 777216 T-EMS[13] 350976 648768 GF(16)上的
(522, 435)DTMS 161733 51765 EMS[11] 667377 358614 T-EMS[13] 770385 1226700 GF(32)上的
(837, 726)DTMS 1300884 201500 EMS[11] 8101044 2493051 T-EMS[13] 9674356 14900739 GF(64)上的
(96, 80)DTMS 74928 15024 EMS[11] 337632 115104 TMM[14] 92496 162864 GF(256)上的
(255, 223)DTMS 1343968 108364 FMS[16] 5493312 601065 TMM[14] 2340900 4197045
下载: 导出CSV
-
[1] GALLAGER R. Low-density parity-check codes[J]. IEEE Transactions on Information Theory, 1962, 8(1): 21–28. doi: 10.1109/TIT.1962.1057683. [2] 张小军, 宋鑫, 高健, 等. 用于5G超可靠低时延通信的LDPC码截断NMS列表译码算法[J]. 电子与信息学报, 2026, 48(6): 2551–2559. doi: 10.11999/JEIT250853.ZHANG Xiaojun, SONG Xin, GAO Jian, et al. A clipped NMS list decoding algorithm for LDPC codes in 5G URLLC[J]. Journal of Electronics & Information Technology, 2026, 48(6): 2551–2559. doi: 10.11999/JEIT250853. [3] YANG Jiayi, WANG Qianfan, LI Shuangyang, et al. 6G-oriented LDPC-coded faster-than-Nyquist signaling: Code design and performance analysis[J]. IEEE Journal on Selected Areas in Communications, 2026, 44: 3089–3103. doi: 10.1109/JSAC.2025.3648707. [4] 张国华, 秦煜, 娄蒙娟, 等. 围长为8的较大列重准循环低密度奇偶校验码的行重普适代数构造[J]. 电子与信息学报, 2024, 46(7): 3019–3025. doi: 10.11999/JEIT231111.ZHANG Guohua, QIN Yu, LOU Mengjuan, et al. Row-weight universal algebraic constructions of Girth-8 quasi-cyclic low-density parity-check codes with large column weights[J]. Journal of Electronics & Information Technology, 2024, 46(7): 3019–3025. doi: 10.11999/JEIT231111. [5] 周华, 李子杰. 空间耦合低密度奇偶校验码残差滑窗译码算法[J]. 电子与信息学报, 2024, 46(3): 867–874. doi: 10.11999/JEIT230288.ZHOU Hua and LI Zijie. Residual sliding window decoding algorithm for spatially-coupled low-density parity-check codes[J]. Journal of Electronics & Information Technology, 2024, 46(3): 867–874. doi: 10.11999/JEIT230288. [6] WANG Qianfan, Wang Yiwen, Yang Jiayi, et al. GE-free BP-OSD for short 5G LDPC codes[C]. 2026 IEEE Wireless Communications and Networking Conference (WCNC), Kuala Lumpur, Malaysia, 2026: 1–6. doi: 10.1109/WCNC65185.2026.11555414. [7] DAVEY M C and MACKAY D. Low-density parity check codes over GF(q)[J]. IEEE Communications Letters, 1998, 2(6): 165–167. doi: 10.1109/4234.681360. [8] 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. [9] ZHANG Yidi, JIANG Ming, and ZHAO Chunming. Genetic optimization of non-binary quasi-cyclic LDPC codes[J]. China Communications, 2025, 22(8): 76–86. doi: 10.23919/JCC.ja.2023-0786. [10] 徐恒舟, 朱海, 冯丹, 等. 低秩循环矩阵的构造方法及其关联的多元LDPC码[J]. 电子与信息学报, 2021, 43(1): 85–91. doi: 10.11999/JEIT200351.XU Hengzhou, ZHU Hai, FENG Dan, et al. Construction of low-rank circulant matrices and their associated nonbinary LDPC codes[J]. Journal of Electronics & Information Technology, 2021, 43(1): 85–91. doi: 10.11999/JEIT200351. [11] VOICILA A, DECLERCQ D, VERDIER F, et al. Low-complexity decoding for non-binary LDPC codes in high order fields[J]. IEEE Transactions on Communications, 2010, 58(5): 1365–1375. doi: 10.1109/TCOMM.2010.05.070096. [12] SAVIN V. Min-max decoding for non binary LDPC codes[C]. 2008 IEEE International Symposium on Information Theory, Toronto, Canada, 2008: 960–964. doi: 10.1109/ISIT.2008.4595129. [13] LI Erbao, DECLERCQ D, and GUNNAM K. Trellis-based extended min-sum algorithm for non-binary LDPC codes and its hardware structure[J]. IEEE Transactions on Communications, 2013, 61(7): 2600–2611. doi: 10.1109/TCOMM.2013.050813.120489. [14] LACRUZ J O, GARCÍA-HERRERO F, DECLERCQ D, et al. Simplified trellis min-max decoder architecture for nonbinary low-density parity-check codes[J]. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2015, 23(9): 1783–1792. doi: 10.1109/TVLSI.2014.2344113. [15] CHOE J and LEE Y. Area-efficient non-binary LDPC decoder with column-wise trellis min-max algorithm[J]. IEEE Journal of Solid-State Circuits, 2025, 60(3): 1082–1091. doi: 10.1109/JSSC.2024.3456765. [16] HUANG Qin, SONG Liyuan, and WANG Zulin. Set message-passing decoding algorithms for regular non-binary LDPC codes[J]. IEEE Transactions on Communications, 2017, 65(12): 5110–5122. doi: 10.1109/TCOMM.2017.2746101. [17] MARCHAND C, BOUTILLON E, HARB H, et al. Hybrid check node architectures for NB-LDPC decoders[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2019, 66(2): 869–880. doi: 10.1109/TCSI.2018.2866882. [18] CHOE J and LEE Y. High-throughput non-binary LDPC decoder architecture using parallel EMS algorithm[J]. IEEE Journal of Solid-State Circuits, 2022, 57(10): 2969–2978. doi: 10.1109/JSSC.2022.3176347. [19] LIU Zhanxian, ZHANG Haijun, HUO Jiahao, et al. Minimum-set min-sum decoding algorithms for non-binary LDPC codes[J]. IEEE Transactions on Communications, 2025, 73(2): 740–751. doi: 10.1109/TCOMM.2024.3450606. [20] SONG Liyuan, YU Hanxiang, ZHANG Xiaosong, et al. Pruning path min-sum decoding algorithm for high-rate non-binary LDPC codes[C]. 2024 16th International Conference on Wireless Communications and Signal Processing (WCSP), Hefei, China, 2024: 24–29. doi: 10.1109/WCSP62071.2024.10827053. [21] SU Chongchong, KANG Peng, CHEN Pingping, et al. Layered SEMS decoding for non-binary LDPC-coded PNC systems[J]. IEEE Wireless Communications Letters, 2025, 14(3): 866–870. doi: 10.1109/LWC.2025.3526613. [22] RANGANATHAN S V S, DIVSALAR D, VAKILINIA K, et al. Design of high-rate irregular non-binary LDPC codes using algorithmic stopping-set cancellation[C]. 2014 IEEE International Symposium on Information Theory, Honolulu, USA, 2014: 711–715. doi: 10.1109/ISIT.2014.6874925. [23] LI Juane, LIU Keke, LIN Shu, et al. A matrix-theoretic approach to the construction of non-binary quasi-cyclic LDPC codes[J]. IEEE Transactions on Communications, 2015, 63(4): 1057–1068. doi: 10.1109/TCOMM.2015.2403856. -
下载:
图(7) / 表(3)
计量
- 文章访问数: 29
- HTML全文浏览量: 7
- PDF下载量: 1
- 被引次数: 0
