A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes

XX XX

doi:10.11999/JEIT260958

Article Contents

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

XX XX. A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260958

Citation:

XX XX. A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260958

XX XX. A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260958

Citation:

XX XX. A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260958

PDF( 3254 KB)

A Dual-Trellis Message-Passing Decoding for Non-Binary LDPC Codes

doi: 10.11999/JEIT260958 cstr: 32379.14.JEIT260958

XX XX

Accepted Date: 2026-08-28
Rev Recd Date: 2026-08-28

Available Online: 2026-09-03

Abstract

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.
- Non-Binary Low-Density Parity-Check (NB-LDPC) codes,
- Truncated messages,
- Dual-trellis,
- Message passing,
- Variable Node (VN)

FullText(HTML)

References(23)

References

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