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

Low Complexity X-EMS Algorithms for Nonbinary LDPC Codes

Xiao Ma, Kai Zhang, Haiqiang Chen, Baoming Bai

Published Oct 3, 2011• 57 citations
Publisher

Abstract

The extended min-sum (EMS) algorithm is redescribed as a reduced-search trellis algorithm (called M-EMS algorithm). Two variants of the M-EMS algorithm, called T-EMS algorithm and D-EMS algorithm, are presented. Simulation results show that, these three algorithms (referred to as X-EMS algorithms for convenience), combined with factor correction techniques, perform almost as well as the Q-ary sum-product algorithm (QSPA) but with a much lower complexity.

DOI
10.1109/tcomm.2011.092011.110082

Related papers

A Variant of the EMS Decoding Algorithm for Nonbinary LDPC Codes

Shancheng Zhao, Zhifei Lu, Xiao Ma +1 more

This letter is concerned with low-complexity decoding algorithms for nonbinary low-density parity-check (NB-LDPC) codes. A new truncation rule based on an adaptive threshold μ is proposed for the extended min-sum (EMS) algorithm. The threshold μ is determined by the mean of the message vector. Therefore, it can be matched to channel observation and decoding iteration. The resulting algorithm is referred to as μ-EMS algorithm. Simulation results show that the μ-EMS algorithm performs almost as well as the Q-ary sum-product algorithm (QSPA). Simulation results also show that the μ-EMS algorithm is simpler than the other X-EMS algorithms for NB-LDPC over high order finite fields.

IEEE Communications Letters•Jul 16, 2013•24 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

Dynamic extended mim-sum decoding algorithm for Q-ary LDPC codes

Xuepeng Wang

Decoded with the extended min-sum(EMS) algorithm,q-ary LDPC codes suffer great performance degradation compared with that decoded with the q-ary sum-product algorithm(QSPA) in case the length nm of message vectors is too small.To solve this problem,a dynamic EMS(D-EMS) algorithm is proposed in this paper.First,we examined the distribution of likelihood values among GF(q) symbols in the message vectors,and concluded that the likelihood values would concentrate to a small portion of symbols as the iteration number increases.Therefore,the D-EMS algorithm first set the length of message vectors to nm1,then truncate it to nm2 after certain decoding iterations,thus the decoding computational complexity can be efficiently reduced.Meanwhile,in order to reduce the complexity of real comparisons in the decoder,the proposed algorithm employs the bubble check(BC) algorithm during the check node elementary steps.Complexity analysis and simulation results indicate that,under appropriate parameter configurations,while efficiently reducing the decoding complexity of the EMS algorithm,the D-EMS algorithm performs nearly as well as the corresponding EMS algorithm over both AWGN and Rayleigh fading channels,and thus can be efficiently applied to practical communication systems based on q-ary LDPC codes.

Journal of Xidian University•Jan 1, 2012•0 citations

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

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

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
The extended min-sum (EMS) algorithm is redescribed as a reduced-search trellis algorithm (called M-EMS algorithm). Two variants of the M-EMS algorithm, called T-EMS algorithm and D-EMS algorithm, are presented. Simulation results show that, these three algorithms (referred to as X-EMS algorithms for convenience), combined with factor correction techniques, perform almost as well as the Q-ary sum-product algorithm (QSPA) but with a much lower complexity.
This letter is concerned with low-complexity decoding algorithms for nonbinary low-density parity-check (NB-LDPC) codes. A new truncation rule based on an adaptive threshold μ is proposed for the extended min-sum (EMS) algorithm. The threshold μ is determined by the mean of the message vector. Therefore, it can be matched to channel observation and decoding iteration. The resulting algorithm is referred to as μ-EMS algorithm. Simulation results show that the μ-EMS algorithm performs almost as well as the Q-ary sum-product algorithm (QSPA). Simulation results also show that the μ-EMS algorithm is simpler than the other X-EMS algorithms for NB-LDPC over high order finite fields.
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.
Decoded with the extended min-sum(EMS) algorithm,q-ary LDPC codes suffer great performance degradation compared with that decoded with the q-ary sum-product algorithm(QSPA) in case the length nm of message vectors is too small.To solve this problem,a dynamic EMS(D-EMS) algorithm is proposed in this paper.First,we examined the distribution of likelihood values among GF(q) symbols in the message vectors,and concluded that the likelihood values would concentrate to a small portion of symbols as the iteration number increases.Therefore,the D-EMS algorithm first set the length of message vectors to nm1,then truncate it to nm2 after certain decoding iterations,thus the decoding computational complexity can be efficiently reduced.Meanwhile,in order to reduce the complexity of real comparisons in the decoder,the proposed algorithm employs the bubble check(BC) algorithm during the check node elementary steps.Complexity analysis and simulation results indicate that,under appropriate parameter configurations,while efficiently reducing the decoding complexity of the EMS algorithm,the D-EMS algorithm performs nearly as well as the corresponding EMS algorithm over both AWGN and Rayleigh fading channels,and thus can be efficiently applied to practical communication systems based on q-ary LDPC codes.
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.
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.
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.