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

International Symposium on Wireless Communication Systems

Trellis based Extended Min-Sum for decoding nonbinary LDPC codes

Erbao Li, Kiran Gunnam, David Declercq

Published Nov 1, 2011• 35 citations
Publisher

Abstract

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.

DOI
10.1109/iswcs.2011.6125307

Related papers

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

Erbao Li, David Declercq, Kiran Gunnam

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.

IEEE Transactions on Communications•May 15, 2013•104 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

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

An adaptive EMS algorithm for nonbinary LDPC codes

Youngjun Hwang, Sunghye Cho, Kyeongcheol Yang

The extended min-sum (EMS) algorithm for decoding low-density parity-check codes over the finite field with q elements significantly reduces decoding complexity by truncating each message of length q into a message of effective length nm. The number of effectively dominant components in each truncated message may gradually decrease with the number of decoding iterations. Based on this observation, we propose a novel adaptive EMS algorithm, called a two-length EMS (TL-EMS) algorithm. It chooses one of two candidate values as the effective message length nmfor each message by reflecting the concept called message separation. Numerical results show that it can significantly reduce the computational complexity with little performance degradation.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2017•2 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

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
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 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 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 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.
The extended min-sum (EMS) algorithm for decoding low-density parity-check codes over the finite field with q elements significantly reduces decoding complexity by truncating each message of length q into a message of effective length nm. The number of effectively dominant components in each truncated message may gradually decrease with the number of decoding iterations. Based on this observation, we propose a novel adaptive EMS algorithm, called a two-length EMS (TL-EMS) algorithm. It chooses one of two candidate values as the effective message length nmfor each message by reflecting the concept called message separation. Numerical results show that it can significantly reduce the computational complexity with little performance degradation.
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.
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.