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 International Conference on Communication Technology (ICCT)

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

Xin Chen, Aidong Men

Published Nov 1, 2008• 6 citations
Publisher

Abstract

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.

DOI
10.1109/icct.2008.4716279

Related papers

A stopping criterion for nonbinary LDPC codes over GF(q)

Xin Chen, Aidong Men, Wei Zhou

Nonbinary 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, a new stopping criterion is proposed. Based on the changes of the variance of variable node¿s extrinsic information, the criterion can predict a decoding failure and decide whether the iteration of the decoder should be stopped. The simulation results show that the stopping criterion can greatly reduces the average number of required iterations of GF(q)-LDPC decoder with negligible performance loss.

IEEE International Conference on Communication Systems (ICCS)•Nov 1, 2008•4 citations

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

David Declercq, M.P.C. Fossorier

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

IEEE Transactions on Communications•Apr 1, 2007•725 citations

Reduced-Complexity Decoding of LDPC Codes

Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.

IEEE Transactions on Communications•Jul 1, 2005•32 citations

비이진 LDPC 부호를 위한 낮은 복잡도의 복호 방법 및 인터리버 설계

김경범

Low density parity-check (LDPC) codes have been shown to approach the Shannon-limit performance when the code length goes to infinify. On the other hand, for moderate code lengths, the error performance can be farther improved by constructing LDPC codes over finite fleld fields GF(q). However, this improvement is achieved at the expense of increased decoding complexity.In this thesis, we consider the problem of decoding nonbinary LDPC codes over GF(q) with reasonable complexity and good error-rate performance. First, the decoding algorithm with low complexity for nonbinary LDPC codes is proposed, named the weighted symbol reliablity algorithm (WSR) which uses syndrome checking result for measuring reliability of symbol nodes. Second, we analyze the extended min-sum (EMS) algorithm proposed by Declearq and Fossorier. These two approaches provide an effective trade-off between decoding complexity and error-performance, compared with the existing decoding algorithms. We also consider nonbinary LDPC codes conbined with high order QAM in order to apply them to realistic communication systems.

•Jan 1, 2014•0 citations

Reduced-Complexity Decoding of LDPC Codes

J. Chen, Ajay Dholakia, Evangelos S. Eleftheriou +2 more

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

IEEE Transactions on Communications•Aug 1, 2005•964 citations

Low-Complexity Symbol-Flipping Decoding Algorithms for Nonbinary LDPC Codes

박성현

Low-density parity-check (LDPC) codes have been shown to have near Shannon-limit performance when a probabilistic decoding is used and the code length goes to infinity. On the other hand, non-binary low-density parity-check (NB-LDPC) codes outperform binary LDPC codes for short code lengths. However, the coding gain of NB-LDPC codes comes from the expense of computational complexity. \n \nIn this thesis, we consider the problem of a trade-off between reasonable complexity and good error-rate performance of decoding nonbinary LDPC codes over GF($q$). We first introduce the existing decoding algorithms of nonbinary LDPC codes and compare with decoding algorithms of binary LDPC codes. Second, low-complexity decoding algorithms of nonbinary LDPC codes is considered and two low-complexity symbol-flipping algorithms based on D-SFDP is proposed. These algorithms outperform the existing D-SFDP algorithm by improving the flipping metric. Proposed algorithms provide good trade-off between complexity and error performance.

•Jan 1, 2018•0 citations
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.
Nonbinary 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, a new stopping criterion is proposed. Based on the changes of the variance of variable node¿s extrinsic information, the criterion can predict a decoding failure and decide whether the iteration of the decoder should be stopped. The simulation results show that the stopping criterion can greatly reduces the average number of required iterations of GF(q)-LDPC decoder with negligible performance loss.
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
Reduced-Complexity Decoding of LDPC Codes Various log-likelihood-ratio-based belief-propagation (LLR- BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representation of the decoding computations are shown to achieve a reduction in complexity, by simplifying the check-node update or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from a performance, latency, computational complexity, and memory-requirement perspective.
Low density parity-check (LDPC) codes have been shown to approach the Shannon-limit performance when the code length goes to infinify. On the other hand, for moderate code lengths, the error performance can be farther improved by constructing LDPC codes over finite fleld fields GF(q). However, this improvement is achieved at the expense of increased decoding complexity.In this thesis, we consider the problem of decoding nonbinary LDPC codes over GF(q) with reasonable complexity and good error-rate performance. First, the decoding algorithm with low complexity for nonbinary LDPC codes is proposed, named the weighted symbol reliablity algorithm (WSR) which uses syndrome checking result for measuring reliability of symbol nodes. Second, we analyze the extended min-sum (EMS) algorithm proposed by Declearq and Fossorier. These two approaches provide an effective trade-off between decoding complexity and error-performance, compared with the existing decoding algorithms. We also consider nonbinary LDPC codes conbined with high order QAM in order to apply them to realistic communication systems.
Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.
Low-density parity-check (LDPC) codes have been shown to have near Shannon-limit performance when a probabilistic decoding is used and the code length goes to infinity. On the other hand, non-binary low-density parity-check (NB-LDPC) codes outperform binary LDPC codes for short code lengths. However, the coding gain of NB-LDPC codes comes from the expense of computational complexity. \n \nIn this thesis, we consider the problem of a trade-off between reasonable complexity and good error-rate performance of decoding nonbinary LDPC codes over GF(qqq). We first introduce the existing decoding algorithms of nonbinary LDPC codes and compare with decoding algorithms of binary LDPC codes. Second, low-complexity decoding algorithms of nonbinary LDPC codes is considered and two low-complexity symbol-flipping algorithms based on D-SFDP is proposed. These algorithms outperform the existing D-SFDP algorithm by improving the flipping metric. Proposed algorithms provide good trade-off between complexity and error performance.