Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Conference on Communication Technology (ICCT)

A reduced complexity decoding algorithm for NB-LDPC codes

Suwen Song, Jun Ting Lin, Jing Tian, Zhongfeng Wang

Published Oct 1, 2017• 2 citations
Publisher

Abstract

Non-binary low-density parity-check (NB-LDPC) codes perform much better than their binary counterparts, when codeword length is moderate or high-order modulation is used. However, the implementation of a NB-LDPC decoder usually suffers from excessive hardware complexity and large memory requirement. Many new algorithms and decoding schedules have been introduced in recent literatures to reduce the decoding complexity in further. However, the complexity of current decoding algorithms for NB-LDPC codes is still high. In this paper, a two-extra-column trellis min-sum algorithm (TEC-TMSA) is proposed. The TEC-TMSA combines the two-extra-column method and the trellis min-sum algorithm in an intelligent way. Since only the minimum value of a row needs to be sorted out for configuration constructions, the computational complexity of the proposed TEC-TMSA is much lower than that of the TMSA. Furthermore, we develop a novel location-fixed selection scheme, which significantly decreases the number of required comparison operations in the TEC-TMSA with negligible performance loss.

DOI
10.1109/icct.2017.8359617

Related papers

Efficient T-EMS Based Decoding Algorithms for High-Order LDPC Codes

Jing Tian, Suwen Song, Jun Ting Lin +1 more

Non-binary low-density parity-check (NB-LDPC) codes show larger coding gain and lower error floor than their binary counterparts in many cases. However, the existing soft decoding algorithms of NB-LDPC codes generally suffer from high computational complexity. Recently, the trellis-based extended min-sum (T-EMS) decoding algorithm has attracted much attention since it can achieve good decoding performance with high parallelism and low computational complexity. In this paper, we propose two new methods to further reduce the computational complexity and enhance the decoding performance. Firstly, we introduce, with theoretical justification, a universal scheme called threshold-based shrinking (TS) scheme, which facilitates significant reduction of computational complexity for decoding of NB-LDPC codes. Secondly, we present a modified two-extra-column (TEC) scheme and apply it to the T-EMS. Furthermore, a high-performance low-complexity decoding algorithm, named TEC-TEMS algorithm, is obtained. Combining the TS scheme with the TEC-TEMS, the new algorithm, named TS-TEC-TEMS algorithm, achieves much lower computational complexity and has negligible performance loss compared to the TEC-TEMS. For a 256-ary (256, 203) example code, compared to the T-EMS, the computational complexities of the TEC-TEMS and TS-TEC-TEMS algorithms are reduced by more than 50% and nearly 90%, respectively. Moreover, the TEC-TEMS and TS-TEC-TEMS both outperform the T-EMS by about 0.3dB when the frame error rate (FER) is around 10-5.

IEEE Access•Jan 1, 2019•7 citations

Low-complexity Check Node Processing for Trellis Min-max Nonbinary LDPC Decoding

Huyen Pham Thi, Dao Tuan Hung, Le Dinh Trang Dang +2 more

Nonbinary low-density-parity-check (NB-LDPC) code outperforms their binary counterpart in terms of error-correcting performance when the code length is moderate. Check node processing is a bottleneck of the NB-LDPC decoding. In this paper, a novel half-row modified two-extra-column trellis min-max (HR-mTEC-TMM) algorithm is proposed for the check node processing to reduce not only the complexity but also the storage memory. The check node unit (CNU) architecture corresponding to the proposed algorithm is designed for the (837, 726) NB-LDPC code over GF(32). The implementation results using 90-nm CMOS technology show that the proposed CNU architecture obtains a reduction of 28.3% for the area and 43.87% for the storage memory with an acceptable error-correcting performance loss, compared to existing work.

International Conference on Advanced Technologies for Communications•Oct 1, 2018•0 citations

Reduced-complexity extended Min-sum check node processing for non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

Non-binary low-density parity-check (NB-LDPC) codes can achieve higher coding gain than binary LDPC codes when the code length is moderate at the cost of higher complexity. One major step of NB-LDPC decoding is check node processing. Previously, iterative forward-backward approaches are employed to implement this step. However, the storage of the intermediate results of the forward and backward computations requires large memory. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the extended Min-sum NB-LDPC decoding. The proposed scheme only stores a limited number of sorted variable-to-check messages. Then the check-to-variable messages for different variable node are generated independently. For a (837, 726) NB-LDPC code over GF(25), the proposed architecture only requires 64% of the area of the previous design with the same throughput and error-correcting performance.

IEEE International Midwest Symposium on Circuits and Systems (MWSCAS)•Aug 1, 2010•5 citations

LOW COMPLEXITY DESIGN OF NON-BINARY LDPC DECODER USING EXTENDED MIN-SUM ALGORITHM

C.S.Elamaran

Low Density Parity Check (LDPC) codes, is a linear block code having the decoding performance closer to Shannon's limit.Nonbinary LDPC is the class of binary LDPC, which works on the higher order Galois field.The decoding performance of non-binary (NB) LDPC is better than binary LDPC for moderate code lengths.The increased computation with the increased order of field is the major challenge in hardware realization of NB-LDPC.The extension of conventional sum-product algorithm, known as extended Min-Sum (EMS) algorithm, with reduced computational complexity is used in this paper.However, a tradeoff exists between computational complexity and decoding performance. This paper aims at reducing the computational complexity by focusing on the Parity Check Matrix (PCM) modifications. The bottleneck of the design is large memory requirement and more computation intensive. The modification in the EMS algorithm can be incorporated to design low complexity hardware architecture of NB-LDPC decoder.

International Journal of Research in Engineering and Technology•Apr 25, 2015•1 citation

A new min-sum based decoding algorithm for non-binary LDPC codes

Chung-Li Wang, Zongwang Li, Shaohua Yang

Non-binary low-density parity-check (NB-LDPC) codes are robust to various channel impairments. In this paper, we present a new decoding algorithm for the NB-LDPC decoder that is based on the q-ary min-sum algorithm (QMSA). The new one modifies the check node (CN) computations of the QMSA into two steps. By reorganizing the message entries and providing the most likely symbol, a compressed intermediate message can be easily obtained and stored, from which the check-to-variable messages can be computed with a look-up table. Thus the decoder architecture can have a straightforward design for the CN with reduced complexity and memory requirements. Besides, the simulation results demonstrate that the proposed algorithm has negligible performance loss compared to the QMSA over AWGN channel.

2012 International Conference on Computing, Networking and Communications (ICNC)•Jan 1, 2012•5 citations

Efficient Search Path Reduction for NB-LDPC Codes with T-EMS Algorithm

Xuewei Quan, Houren Ji, Xiaohu You +1 more

In comparison to the forward-backward update of extended min-sum (EMS) algorithm, the trellis EMS (T-EMS) algorithm for non-binary low density parity check codes (NB-LDPC) introduces an extra trellis column during check nodes (CNs) updates, significantly enhancing parallelism and facilitating hardware implementation. However, in high-order or high code rate scenarios, the T-EMS algorithm exhibits considerable latency caused by excessive configurations searching for the largest reliability selection. To address this, the paper propose an enhanced algorithm, named as path reduction T-EMS (RT-EMS) algorithm, to simplify the configuration space through applying an additional filtering to the elements in each column of the trellis, retaining only the elements that are deemed more trustworthy from the column’s perspective. Moreover, a data compensation strategy is also proposed to tackle the data scarcity issues for some syndrome values in the extra trellis column. Finally, the simulation results demonstrate that RT-EMS algorithm can achieve more than 50% complexity reduction with a negligible performance degradation.

IEEE International Conference on ASIC (ASICON)•Oct 24, 2023•0 citations
Non-binary low-density parity-check (NB-LDPC) codes perform much better than their binary counterparts, when codeword length is moderate or high-order modulation is used. However, the implementation of a NB-LDPC decoder usually suffers from excessive hardware complexity and large memory requirement. Many new algorithms and decoding schedules have been introduced in recent literatures to reduce the decoding complexity in further. However, the complexity of current decoding algorithms for NB-LDPC codes is still high. In this paper, a two-extra-column trellis min-sum algorithm (TEC-TMSA) is proposed. The TEC-TMSA combines the two-extra-column method and the trellis min-sum algorithm in an intelligent way. Since only the minimum value of a row needs to be sorted out for configuration constructions, the computational complexity of the proposed TEC-TMSA is much lower than that of the TMSA. Furthermore, we develop a novel location-fixed selection scheme, which significantly decreases the number of required comparison operations in the TEC-TMSA with negligible performance loss.
Non-binary low-density parity-check (NB-LDPC) codes show larger coding gain and lower error floor than their binary counterparts in many cases. However, the existing soft decoding algorithms of NB-LDPC codes generally suffer from high computational complexity. Recently, the trellis-based extended min-sum (T-EMS) decoding algorithm has attracted much attention since it can achieve good decoding performance with high parallelism and low computational complexity. In this paper, we propose two new methods to further reduce the computational complexity and enhance the decoding performance. Firstly, we introduce, with theoretical justification, a universal scheme called threshold-based shrinking (TS) scheme, which facilitates significant reduction of computational complexity for decoding of NB-LDPC codes. Secondly, we present a modified two-extra-column (TEC) scheme and apply it to the T-EMS. Furthermore, a high-performance low-complexity decoding algorithm, named TEC-TEMS algorithm, is obtained. Combining the TS scheme with the TEC-TEMS, the new algorithm, named TS-TEC-TEMS algorithm, achieves much lower computational complexity and has negligible performance loss compared to the TEC-TEMS. For a 256-ary (256, 203) example code, compared to the T-EMS, the computational complexities of the TEC-TEMS and TS-TEC-TEMS algorithms are reduced by more than 50% and nearly 90%, respectively. Moreover, the TEC-TEMS and TS-TEC-TEMS both outperform the T-EMS by about 0.3dB when the frame error rate (FER) is around 10-5.
Nonbinary low-density-parity-check (NB-LDPC) code outperforms their binary counterpart in terms of error-correcting performance when the code length is moderate. Check node processing is a bottleneck of the NB-LDPC decoding. In this paper, a novel half-row modified two-extra-column trellis min-max (HR-mTEC-TMM) algorithm is proposed for the check node processing to reduce not only the complexity but also the storage memory. The check node unit (CNU) architecture corresponding to the proposed algorithm is designed for the (837, 726) NB-LDPC code over GF(32). The implementation results using 90-nm CMOS technology show that the proposed CNU architecture obtains a reduction of 28.3% for the area and 43.87% for the storage memory with an acceptable error-correcting performance loss, compared to existing work.
Non-binary low-density parity-check (NB-LDPC) codes can achieve higher coding gain than binary LDPC codes when the code length is moderate at the cost of higher complexity. One major step of NB-LDPC decoding is check node processing. Previously, iterative forward-backward approaches are employed to implement this step. However, the storage of the intermediate results of the forward and backward computations requires large memory. In this paper, a novel check node processing scheme and corresponding VLSI architectures are proposed for the extended Min-sum NB-LDPC decoding. The proposed scheme only stores a limited number of sorted variable-to-check messages. Then the check-to-variable messages for different variable node are generated independently. For a (837, 726) NB-LDPC code over GF(25), the proposed architecture only requires 64% of the area of the previous design with the same throughput and error-correcting performance.
Low Density Parity Check (LDPC) codes, is a linear block code having the decoding performance closer to Shannon's limit.Nonbinary LDPC is the class of binary LDPC, which works on the higher order Galois field.The decoding performance of non-binary (NB) LDPC is better than binary LDPC for moderate code lengths.The increased computation with the increased order of field is the major challenge in hardware realization of NB-LDPC.The extension of conventional sum-product algorithm, known as extended Min-Sum (EMS) algorithm, with reduced computational complexity is used in this paper.However, a tradeoff exists between computational complexity and decoding performance. This paper aims at reducing the computational complexity by focusing on the Parity Check Matrix (PCM) modifications. The bottleneck of the design is large memory requirement and more computation intensive. The modification in the EMS algorithm can be incorporated to design low complexity hardware architecture of NB-LDPC decoder.
Non-binary low-density parity-check (NB-LDPC) codes are robust to various channel impairments. In this paper, we present a new decoding algorithm for the NB-LDPC decoder that is based on the q-ary min-sum algorithm (QMSA). The new one modifies the check node (CN) computations of the QMSA into two steps. By reorganizing the message entries and providing the most likely symbol, a compressed intermediate message can be easily obtained and stored, from which the check-to-variable messages can be computed with a look-up table. Thus the decoder architecture can have a straightforward design for the CN with reduced complexity and memory requirements. Besides, the simulation results demonstrate that the proposed algorithm has negligible performance loss compared to the QMSA over AWGN channel.
In comparison to the forward-backward update of extended min-sum (EMS) algorithm, the trellis EMS (T-EMS) algorithm for non-binary low density parity check codes (NB-LDPC) introduces an extra trellis column during check nodes (CNs) updates, significantly enhancing parallelism and facilitating hardware implementation. However, in high-order or high code rate scenarios, the T-EMS algorithm exhibits considerable latency caused by excessive configurations searching for the largest reliability selection. To address this, the paper propose an enhanced algorithm, named as path reduction T-EMS (RT-EMS) algorithm, to simplify the configuration space through applying an additional filtering to the elements in each column of the trellis, retaining only the elements that are deemed more trustworthy from the column’s perspective. Moreover, a data compensation strategy is also proposed to tackle the data scarcity issues for some syndrome values in the extra trellis column. Finally, the simulation results demonstrate that RT-EMS algorithm can achieve more than 50% complexity reduction with a negligible performance degradation.