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

A Low-Complexity EMS Algorithm with Dynamic Message Truncation for Non-Binary LDPC Codes

Fulong Wang, Ming Zhan, Qian Zhang, Hao Tang, Yunkai Feng, Mingjuan Qiu, Liangxi Liu

Published Oct 14, 2021• 0 citations
Publisher

Abstract

The extended min-sum (EMS) algorithm is adopted for non-binary low density parity check (NB-LDPC) codes. The high complexity of EMS algorithm is a hot topic in recent years. Aiming at the problem, a low-complexity EMS algorithm based on NB-LDPC codes is proposed. Dynamic bubble-check (DBC) algorithm in elementary check node (ECN) steps is adopted to reduce the complexity of check node. Furthermore, the proposed algorithm dynamically truncates the length of the message vector by the number of decoding iterations. Taking the length of message vector truncated again as half of the original one as an example, the simulation results and complexity are analyzed. Analysis shows that, compared to the EMS algorithm, computational complexity of comparisons and real additions of check node of the proposed algorithm have reduced by about 70% and 25% respectively. Meantime, the decoding performance of the proposed algorithm approach that of EMS algorithm and the loss is only near 0.08 dB when the bit error rate (BER) is 10−3and the Galois field$GF(q)(q=16)$.

DOI
10.1109/icitee53064.2021.9611936

Related papers

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

A Novel Truncation Rule for the EMS Decoding of Non-binary LDPC Codes

Kuntal Deka, A. Rajesh, Prabin Kumar Bora

This paper presents a novel truncation rule for the extended min-sum (EMS) decoding of non-binary low-density parity-check (NB-LDPC) codes. The conventional NB-LDPC decoders involve vector-messages of length equal to the field size q. The complexity of these decoders increases significantly as q increases. In the EMS algorithm, the vector-messages are truncated by discarding the less-likely symbols. In this paper, we propose a truncation rule so that the lengths of the vector-messages are reduced to the so-far best limit without compromising on the error correction capability. We devise a proximity matrix which helps to identify the essential components of a vector-message for truncation. The proposed truncation rule has been applied to several NB-LDPC codes of different field sizes. Simulation results for these codes show that the proposed rule can achieve the maximum truncation with negligible performance loss.

International Conference on Signal Processing and Communications (SPCOM)•Jul 1, 2018•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

Weighting Factors Optimization for NB-LDPC Codes Based on Extended Min-Sum Algorithm

Mingjuan Qiu, Ming Zhan, Liangxi Liu +2 more

The decoding algorithms of Nonbinary low-density parity-check (NB-LDPC) codes mainly include Belief Propagation (BP), Fast Fourier Transforms (FFT) and Extended Min-Sum (EMS). Among these decoding algorithms, although EMS has the lowest decoding complexity, there is still room for improvement. Therefore, this paper proposes a new algorithm based on the EMS algorithm to further improve the decoding complexity and performance. In order to reduce complexity, an adaptive truncation rule is added to the decoding process. The adaptive truncation rule chooses the length of automatic truncation to reduce the average number of iterations. Thus, the complexity of decoding algorithm is reduced. Besides the weighting factors is added to the variable update iteration process, which effectively improves the decoding performance. The results show that the proposed algorithm has about 0.9 dB gain compared with the EMS decoding algorithm when the bit error rate (BER) is 10--4and the Galois field GF(q) (q16).

IEEE International Conference on High Performance Computing and Communications; IEEE International Conference on Smart City; IEEE International Conference on Data Science and Systems (HPCC/SmartCity/DSS)•Dec 1, 2020•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

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
The extended min-sum (EMS) algorithm is adopted for non-binary low density parity check (NB-LDPC) codes. The high complexity of EMS algorithm is a hot topic in recent years. Aiming at the problem, a low-complexity EMS algorithm based on NB-LDPC codes is proposed. Dynamic bubble-check (DBC) algorithm in elementary check node (ECN) steps is adopted to reduce the complexity of check node. Furthermore, the proposed algorithm dynamically truncates the length of the message vector by the number of decoding iterations. Taking the length of message vector truncated again as half of the original one as an example, the simulation results and complexity are analyzed. Analysis shows that, compared to the EMS algorithm, computational complexity of comparisons and real additions of check node of the proposed algorithm have reduced by about 70% and 25% respectively. Meantime, the decoding performance of the proposed algorithm approach that of EMS algorithm and the loss is only near 0.08 dB when the bit error rate (BER) is 10−3and the Galois fieldGF(q)(q=16)GF(q)(q=16)GF(q)(q=16).
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.
This paper presents a novel truncation rule for the extended min-sum (EMS) decoding of non-binary low-density parity-check (NB-LDPC) codes. The conventional NB-LDPC decoders involve vector-messages of length equal to the field size q. The complexity of these decoders increases significantly as q increases. In the EMS algorithm, the vector-messages are truncated by discarding the less-likely symbols. In this paper, we propose a truncation rule so that the lengths of the vector-messages are reduced to the so-far best limit without compromising on the error correction capability. We devise a proximity matrix which helps to identify the essential components of a vector-message for truncation. The proposed truncation rule has been applied to several NB-LDPC codes of different field sizes. Simulation results for these codes show that the proposed rule can achieve the maximum truncation with negligible performance loss.
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.
The decoding algorithms of Nonbinary low-density parity-check (NB-LDPC) codes mainly include Belief Propagation (BP), Fast Fourier Transforms (FFT) and Extended Min-Sum (EMS). Among these decoding algorithms, although EMS has the lowest decoding complexity, there is still room for improvement. Therefore, this paper proposes a new algorithm based on the EMS algorithm to further improve the decoding complexity and performance. In order to reduce complexity, an adaptive truncation rule is added to the decoding process. The adaptive truncation rule chooses the length of automatic truncation to reduce the average number of iterations. Thus, the complexity of decoding algorithm is reduced. Besides the weighting factors is added to the variable update iteration process, which effectively improves the decoding performance. The results show that the proposed algorithm has about 0.9 dB gain compared with the EMS decoding algorithm when the bit error rate (BER) is 10--4and the Galois field GF(q) (q16).
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.
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.