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 Transactions on Communications

Trellis-Based Extended Min-Sum Algorithm for Non-Binary LDPC Codes and its Hardware Structure

Erbao Li, David Declercq, Kiran Gunnam

Published May 15, 2013• 104 citations
Publisher

Abstract

In this paper, we present an improvement and a new implementation of a simplified decoding algorithm for non-binary low density parity-check codes (NB-LDPC) in Galois fields GF(q). The base algorithm that we use is the Extended Min-Sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation (BP) algorithm, with limited complexity. In our work, we propose a new way to compute modified configuration sets, using a trellis representation of incoming messages to check nodes. We call our modification of the EMS algorithm trellis-EMS (T-EMS). In the T-EMS, the algorithm operates directly on the deviation space by considering a trellis built from differential messages, which serves as a new reliability measure to sort the configurations. We show that this new trellis representation reduces the computational complexity, without any performance degradation. In addition, we show that our modifications of the algorithm allows to greatly reduce the decoding latency, by using a larger degree of hardware parallelization.

DOI
10.1109/tcomm.2013.050813.120489

Related papers

Trellis based Extended Min-Sum for decoding nonbinary LDPC codes

Erbao Li, Kiran Gunnam, David Declercq

In this paper, we propose a new method to implement the Extended Min-Sum (EMS) algorithm based on trellis representation of inputting messages to the check node. The original EMS reduces the decoding complexity by choosing only nmmost reliable values and by introducing the idea of configuration sets conf(nm, nc), where ncis the number of deviations from the most reliable output configuration. We propose to work directly on the deviation space by building a configuration trellis based on delta messages, which serves as a new reliability measure. The algorithm is called trellis-EMS (T-EMS). By using the new trellis representation, only nc+1 minimum values from each row of the trellis need to be considered, which reduces the ordering complexity. The trellis representation in the deviation space also reduces the number of output configurations tested, without any performance degradation. Our method is especially suitable for moderate field size q and large check node degree nonbinary LDPC codes.

International Symposium on Wireless Communication Systems•Nov 1, 2011•35 citations

Threshold-based extended minimum-sum algorithm for non-binary LDPC codes

Ke Lai, Erbao Li, Jing Lei

In this paper, we propose a new improved algorithm to reduce the decoding complexity of NB-LDPC codes especially when the number of iteration is large. The proposed algorithm is based on the extended min-sum (EMS) which truncates the message vectors and trellis-based EMS (T-EMS) which employs the trellis representation. Our modification of EMS introduces the thresholds to further truncate the incoming messages to the check node. The performance of our improved new algorithm is only 0.05dB (resp 0.2dB) to BP in the waterfall region over GF(8) (resp GF(128)), but the complexity will reduce to lower than half of the EMS when the threshold is chosen reasonable.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 1, 2016•0 citations

Reduced-Complexity T-EMS Algorithm with Elitist Selection for Non-Binary LDPC Codes

Zhong Tang, Ming Zhan, Chenchang Gao +1 more

In this paper, we proposed a modified Trellis extended min-sum (T-EMS) algorithm with L truncations for non-binary low density parity check (NB-LDPC) codes. The proposed algorithm achieves to reduce complexity of T-EMS algorithm, especially on large order Galois fields GF(q). In order to improve the error-correcting performance of the algorithm, an elitist selection (ES) strategy is presented, which enlarges the belief value of the selected symbols. As a proof, the simulation results and complexity analysis show that with the increase of q, the complexity decreases obviously. However, in the case of a suitable L value, the LT-EMS algorithm with ES strategy is not inferior to the T-EMS algorithm in performance. In addition, the ES strategy can accelerate the convergence rate and reduce the number of iterations of the decoding process, which will enhance the decoding throughput.

International Symposium on Networks, Computers and Communications (ISNCC)•Jul 19, 2022•0 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

Decoding Algorithms for Nonbinary LDPC Codes Over GF$(q)$

David Declercq, M.P.C. Fossorier

In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes

IEEE Transactions on Communications•Apr 1, 2007•724 citations

A Low-Complexity Adaptive Extended Min-Sum Algorithm for Non-Binary LDPC Codes

Minho Kim, Kyeong-Bin Park, Ki‐Seok Chung

The extended min-sum algorithm (EMS) for decoding non-binary low density parity check (NB-LDPC) codes reduces the decoding complexity by truncating the message vector by retaining only the most reliable symbols. However, the EMS algorithm does not consider that the noise of the received codeword is gradually reduced as the iteration count goes up. In this paper, we propose a low-complexity adaptive EMS algorithm, called threshold-based EMS (TB-EMS). The TB-EMS algorithm has a simple adaptive rule to calculate the new message vector length compared to the A-EMS. The proposed algorithm selects one of two message vector lengths. Experimental results show that the proposed algorithm reduces the decoding complexity with minimal performance degradation compared with the EMS algorithm. Further, the decoding performance of the TB-EMS is better than A-EMS.

International Conference on Computational Intelligence and Applications (ICCIA)•Jun 1, 2020•3 citations
In this paper, we present an improvement and a new implementation of a simplified decoding algorithm for non-binary low density parity-check codes (NB-LDPC) in Galois fields GF(q). The base algorithm that we use is the Extended Min-Sum (EMS) algorithm, which has been widely studied in the recent literature, and has been shown to approach the performance of the belief propagation (BP) algorithm, with limited complexity. In our work, we propose a new way to compute modified configuration sets, using a trellis representation of incoming messages to check nodes. We call our modification of the EMS algorithm trellis-EMS (T-EMS). In the T-EMS, the algorithm operates directly on the deviation space by considering a trellis built from differential messages, which serves as a new reliability measure to sort the configurations. We show that this new trellis representation reduces the computational complexity, without any performance degradation. In addition, we show that our modifications of the algorithm allows to greatly reduce the decoding latency, by using a larger degree of hardware parallelization.
In this paper, we propose a new method to implement the Extended Min-Sum (EMS) algorithm based on trellis representation of inputting messages to the check node. The original EMS reduces the decoding complexity by choosing only nmmost reliable values and by introducing the idea of configuration sets conf(nm, nc), where ncis the number of deviations from the most reliable output configuration. We propose to work directly on the deviation space by building a configuration trellis based on delta messages, which serves as a new reliability measure. The algorithm is called trellis-EMS (T-EMS). By using the new trellis representation, only nc+1 minimum values from each row of the trellis need to be considered, which reduces the ordering complexity. The trellis representation in the deviation space also reduces the number of output configurations tested, without any performance degradation. Our method is especially suitable for moderate field size q and large check node degree nonbinary LDPC codes.
In this paper, we propose a new improved algorithm to reduce the decoding complexity of NB-LDPC codes especially when the number of iteration is large. The proposed algorithm is based on the extended min-sum (EMS) which truncates the message vectors and trellis-based EMS (T-EMS) which employs the trellis representation. Our modification of EMS introduces the thresholds to further truncate the incoming messages to the check node. The performance of our improved new algorithm is only 0.05dB (resp 0.2dB) to BP in the waterfall region over GF(8) (resp GF(128)), but the complexity will reduce to lower than half of the EMS when the threshold is chosen reasonable.
In this paper, we proposed a modified Trellis extended min-sum (T-EMS) algorithm with L truncations for non-binary low density parity check (NB-LDPC) codes. The proposed algorithm achieves to reduce complexity of T-EMS algorithm, especially on large order Galois fields GF(q). In order to improve the error-correcting performance of the algorithm, an elitist selection (ES) strategy is presented, which enlarges the belief value of the selected symbols. As a proof, the simulation results and complexity analysis show that with the increase of q, the complexity decreases obviously. However, in the case of a suitable L value, the LT-EMS algorithm with ES strategy is not inferior to the T-EMS algorithm in performance. In addition, the ES strategy can accelerate the convergence rate and reduce the number of iterations of the decoding process, which will enhance the decoding throughput.
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.
Decoding Algorithms for Nonbinary LDPC Codes Over GF(q)(q)(q)
In this letter, we address the problem of decoding nonbinary low-density parity-check (LDPC) codes over finite fields GF(q), with reasonable complexity and good performance. In the first part of the letter, we recall the original belief propagation (BP) decoding algorithm and its Fourier domain implementation. We show that the use of tensor notations for the messages is very convenient for the algorithm description and understanding. In the second part of the letter, we introduce a simplified decoder which is inspired by the min-sum decoder for binary LDPC codes. We called this decoder extended min-sum (EMS). We show that it is possible to greatly reduce the computational complexity of the check-node processing by computing approximate reliability measures with a limited number of values in a message. By choosing appropriate correction factors or offsets, we show that the EMS decoder performance is quite good, and in some cases better than the regular BP decoder. The optimal values of the factor and offset correction are obtained asymptotically with simulated density evolution. Our simulations on ultra-sparse codes over very-high-order fields show that nonbinary LDPC codes are promising for applications which require low frame-error rates for small or moderate codeword lengths. The EMS decoder is a good candidate for practical hardware implementations of such codes
The extended min-sum algorithm (EMS) for decoding non-binary low density parity check (NB-LDPC) codes reduces the decoding complexity by truncating the message vector by retaining only the most reliable symbols. However, the EMS algorithm does not consider that the noise of the received codeword is gradually reduced as the iteration count goes up. In this paper, we propose a low-complexity adaptive EMS algorithm, called threshold-based EMS (TB-EMS). The TB-EMS algorithm has a simple adaptive rule to calculate the new message vector length compared to the A-EMS. The proposed algorithm selects one of two message vector lengths. Experimental results show that the proposed algorithm reduces the decoding complexity with minimal performance degradation compared with the EMS algorithm. Further, the decoding performance of the TB-EMS is better than A-EMS.