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

Low-Complexity, Low-Memory EMS Algorithm for Non-Binary LDPC Codes

Adrian Voicila, David Declercq, François S. Verdier, M.P.C. Fossorier, Pascal Urard

Published Jun 1, 2007• 75 citations
Publisher

Abstract

In this paper, we propose a new implementation of the EMS decoder for non binary LDPC codes presented in (D. Declencq and M. Fossorier, 2007). A particularity of the new algorithm is that it takes into accounts the memory problem of the non binary LDPC decoders, together with a significant complexity reduction per decoding iteration. The key feature of our decoder is to truncate the vector messages of the decoder to a limited number nm of values in order to reduce the memory requirements. Using the truncated messages, we propose an efficient implementation of the EMS decoder which reduces the order of complexity to O(nmlog2nm), which starts to be reasonable enough to compete with binary decoders. The performance of the low complexity algorithm with proper compensation are quite good with respect to the important complexity reduction, which is shown both with a simulated density evolution approach and actual FER simulations.

DOI
10.1109/icc.2007.115

Related papers

Low-complexity decoding for non-binary LDPC codes in high order fields

Adrian Voicila, David Declercq, François S. Verdier +2 more

In this paper, we propose a new implementation of the Extended Min-Sum (EMS) decoder for non-binary LDPC codes. A particularity of the new algorithm is that it takes into accounts the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration. The key feature of our decoder is to truncate the vector messages of the decoder to a limited number nmof values in order to reduce the memory requirements. Using the truncated messages, we propose an efficient implementation of the EMS decoder which reduces the order of complexity to ¿(nmlog2nm). This complexity starts to be reasonable enough to compete with binary decoders. The performance of the low complexity algorithm with proper compensation is quite good with respect to the important complexity reduction, which is shown both with a simulated density evolution approach and actual simulations.

IEEE Transactions on Communications•May 1, 2010•223 citations

Architecture of a low-complexity non-binary LDPC decoder for high order fields

Adrian Voicila, François S. Verdier, David Declercq +2 more

In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC codes, presented in [10]. To the knowledge of the authors this is the first implementation of a GF(q) LDPC decoder for high order fields (q ges 64). The originality of the proposed architecture is that it takes into account the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field order. We present the estimation of the non-binary decoder implementation and key metrics including throughput and hardware complexity. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results show also that an implementation of a non-binary LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, non-binary LDPC codes provide a promising vehicle for real-life efficient coding system implementations.

International Symposium on Communications and Information Technologies•Oct 1, 2007•61 citations

Architecture of a Low-Complexity Non-Binary LDPC Decoder

Adrian Voicila, David Declercq, François S. Verdier +2 more

In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC (NB-LDPC) codes, presented in [4]. To the knowledge of the authors this is the first implementation of an GF(q) LDPC decoder for high order fields (q ≥ 64). The originality of the proposed architecture is that it takes into account the memory problem of the NB-LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field's order. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results prove also that an implementation of a NB-LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, NB-LDPC codes provides a promising vehicle for real-life efficient coding system implementations.

International Conference on Consumer Electronics•Jan 1, 2008•1 citation

Efficient EMS decoding for non-binary LDPC codes

Leixin Zhou, Jin Sha, Zhongfeng Wang

Non-binary low-density parity-check (NB-LDPC) codes are an extension of binary LDPC codes with significantly better performance when the code length is moderate. Previously, forward-backward schemes are used to implement check node processing, which need large memory. In this paper, a novel approach is proposed for EMS NB-LDPC decoding. Compared to EMS decoding algorithm, the message memory and the average number of iterations have been reduced. Also, the overall decoder architecture is proposed.

International SoC Design Conference•Nov 1, 2012•9 citations

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

Fulong Wang, Ming Zhan, Qian Zhang +4 more

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)$.

•Oct 14, 2021•0 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 propose a new implementation of the EMS decoder for non binary LDPC codes presented in (D. Declencq and M. Fossorier, 2007). A particularity of the new algorithm is that it takes into accounts the memory problem of the non binary LDPC decoders, together with a significant complexity reduction per decoding iteration. The key feature of our decoder is to truncate the vector messages of the decoder to a limited number nm of values in order to reduce the memory requirements. Using the truncated messages, we propose an efficient implementation of the EMS decoder which reduces the order of complexity to O(nmlog2nm), which starts to be reasonable enough to compete with binary decoders. The performance of the low complexity algorithm with proper compensation are quite good with respect to the important complexity reduction, which is shown both with a simulated density evolution approach and actual FER simulations.
In this paper, we propose a new implementation of the Extended Min-Sum (EMS) decoder for non-binary LDPC codes. A particularity of the new algorithm is that it takes into accounts the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration. The key feature of our decoder is to truncate the vector messages of the decoder to a limited number nmof values in order to reduce the memory requirements. Using the truncated messages, we propose an efficient implementation of the EMS decoder which reduces the order of complexity to ¿(nmlog2nm). This complexity starts to be reasonable enough to compete with binary decoders. The performance of the low complexity algorithm with proper compensation is quite good with respect to the important complexity reduction, which is shown both with a simulated density evolution approach and actual simulations.
In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC codes, presented in [10]. To the knowledge of the authors this is the first implementation of a GF(q) LDPC decoder for high order fields (q ges 64). The originality of the proposed architecture is that it takes into account the memory problem of the non-binary LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field order. We present the estimation of the non-binary decoder implementation and key metrics including throughput and hardware complexity. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results show also that an implementation of a non-binary LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, non-binary LDPC codes provide a promising vehicle for real-life efficient coding system implementations.
In this paper, we propose a hardware implementation of the EMS decoding algorithm for non-binary LDPC (NB-LDPC) codes, presented in [4]. To the knowledge of the authors this is the first implementation of an GF(q) LDPC decoder for high order fields (q ≥ 64). The originality of the proposed architecture is that it takes into account the memory problem of the NB-LDPC decoders, together with a significant complexity reduction per decoding iteration which becomes independent from the field's order. The error decoding performance of the low complexity algorithm with proper compensation has been obtained through computer simulations. The frame error rate results are quite good with respect to the important complexity reduction. The results prove also that an implementation of a NB-LDPC decoder is now feasible and the extra complexity of the decoder is balanced by the superior performance of this class of codes. With their foreseen simple architectures and good-error correcting performances, NB-LDPC codes provides a promising vehicle for real-life efficient coding system implementations.
Non-binary low-density parity-check (NB-LDPC) codes are an extension of binary LDPC codes with significantly better performance when the code length is moderate. Previously, forward-backward schemes are used to implement check node processing, which need large memory. In this paper, a novel approach is proposed for EMS NB-LDPC decoding. Compared to EMS decoding algorithm, the message memory and the average number of iterations have been reduced. Also, the overall decoder architecture is proposed.
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.