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

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

David Declercq, M.P.C. Fossorier

Published Apr 1, 2007• 724 citations
Publisher

Abstract

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

DOI
10.1109/tcomm.2007.894088

Related papers

Adaptive Extended Min-Sum Algorithm for Nonbinary LDPC Decoding

Xuan Guan, Yunsi Fei

Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.

Globecom•Dec 1, 2011•7 citations

Reduced complexity and improved performance decoding algorithm for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men

Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.

IEEE International Conference on Communication Technology (ICCT)•Nov 1, 2008•6 citations

Combined normalized and offset extended min sum decoding algorithm for LDPC codes over GF (q)

Md Murad Hossain, Mohammad Rakibul Islam

In this paper the combined normalized and offset extended min sum (EMS) is proposed for efficient decoding of non-binary low density parity check (LDPC) codes. EMS is the approximation of the sum product algorithm for reducing the computation complexity. However there is a performance gap between EMS and SP algorithm due to this approximation. The approximate check node messages of the extended min sum are compensated by both normalized and offset factor. The normalized factor and offset factor is determined for one iteration and is kept constant for all SNRs and iterations. It will shown in bit error rate simulation of (1008, 504) LDPC code over GF (4) that combined normalized offset extended min sum has superior performance than normalized and offset extended min sum. However, it requires only extra one multiplication for each cycle.

International Conference on Computer and Information Technology (ICCIT)•Dec 1, 2011•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

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

Non-binary LDPC decoder architectures

Zhang Xinmiao

This chapter reviews nonbinary low–density parity–check (NB–LDPC) decoder architectures, with emphasis given to algorithmic and architectural modification techniques for the check node units. The belief propagation (BP) for binary low-density parity-check decoding can be extended to decode NB–LDPC codes. In non–binary BP, the check node processing also computes sums of products of probabilities. The computations in non–binary check node processing can be considered as convolutions of the incoming messages. Multiplications in probability domain are implemented as additions in log domain. The most prominent ones are the extended Minsum algorithm and the Min–max algorithm. Both of them are log-domain algorithms. The approximations lead to slight performance loss compared to the BP, the hardware complexity has been greatly reduced in these algorithms, and only additions on the reliability messages are involved in their check node processing. The number of multiplications in the check node processing is reduced in the frequency–domain approach.

CRC Press eBooks•Jun 29, 2015•0 citations
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
Low Density Parity Check (LDPC) codes over a Galois Field GF(q) can provide significantly better error- correcting quality than binary LDPC codes with moderate code length. However, the computational complexity and memory requirement of nonbinary codes are much higher, limiting the application of non- binary LDPC codes. In this paper, we propose an adaptive message truncation algorithm for non-binary LDPC decoding, guided by the estimated code error rates. Compared to the previous fixed message truncation method, it can cut the messages adaptively, and therefore provide better decoding quality and computation complexity reduction. To further reduce the computation, we propose another adaptive check node update algorithm, simplifying the decoding by reducing the number of check nodes updating. Our simulation results demonstrate that by combining these two algorithms together, the average message size can be reduced greatly and good decoding quality is achieved, at a little cost of iterations. Compared to the existing truncation algorithms, our approach can reduce the order of complexity to O(nalog2(na)) (where nais messages size), with less performance degradation.
Low-density parity-check (LDPC) codes over finite fields GF(q) have a better performance than those of the binary low-density parity-check codes, at short and medium block lengths, but the decoder of GF(q)-LDPC has more complexity. In this paper, we present a new reduced-complexity belief propagation (BP) decoding algorithm for GF(q)-LDPC codes by analyzing the reliability of code symbols. Instead of update all the variable nodes during iteration, we just update variable nodes which are mostly to be in an error. The algorithm also shows a property to reduce the effects of oscillating on decoding. The simulations prove that we could improve performance and reduce complexity at the same time for short and medium GF(q)-LDPC codes.
In this paper the combined normalized and offset extended min sum (EMS) is proposed for efficient decoding of non-binary low density parity check (LDPC) codes. EMS is the approximation of the sum product algorithm for reducing the computation complexity. However there is a performance gap between EMS and SP algorithm due to this approximation. The approximate check node messages of the extended min sum are compensated by both normalized and offset factor. The normalized factor and offset factor is determined for one iteration and is kept constant for all SNRs and iterations. It will shown in bit error rate simulation of (1008, 504) LDPC code over GF (4) that combined normalized offset extended min sum has superior performance than normalized and offset extended min sum. However, it requires only extra one multiplication for each cycle.
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 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.
This chapter reviews nonbinary low–density parity–check (NB–LDPC) decoder architectures, with emphasis given to algorithmic and architectural modification techniques for the check node units. The belief propagation (BP) for binary low-density parity-check decoding can be extended to decode NB–LDPC codes. In non–binary BP, the check node processing also computes sums of products of probabilities. The computations in non–binary check node processing can be considered as convolutions of the incoming messages. Multiplications in probability domain are implemented as additions in log domain. The most prominent ones are the extended Minsum algorithm and the Min–max algorithm. Both of them are log-domain algorithms. The approximations lead to slight performance loss compared to the BP, the hardware complexity has been greatly reduced in these algorithms, and only additions on the reliability messages are involved in their check node processing. The number of multiplications in the check node processing is reduced in the frequency–domain approach.