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

Globecom

Efficient implementations of the sum-product algorithm for decoding LDPC codes

Xiao-Yu Hu, Evangelos S. Eleftheriou, D.-M. Arnold, Ajay Dholakia

Published Nov 13, 2002• 375 citations
Publisher

Abstract

Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.

DOI
10.1109/glocom.2001.965575

Related papers

Efficient Difference-based Decoding Implementations of LDPC Codes

Zhanji Wu, Peng Mugen, Wang Wenbo +1 more

Efficient implementations of the sum-product algorithm (SPA) for decoding low-density parity-check (LDPC) codes using difference-based messages between bit nodes and check nodes are presented. As for the updates of check nodes, reduced- complexity derivatives are also put forward. As compared with the traditional Log-Likelihood-Ratio(LLR)-based decoding implementations, the proposed method has much lower complexity and latency, while it has no obvious loss of the error performance.

IEEE Communications Letters•May 1, 2008•3 citations

Efficient implementation of the sum-product algorithm forquantized decoding of LDPC codes

Wang Xin-meii

An efficient implementation of the Sum-Product algorithm(SPA) in the log-likelihood ratio (LLR) domain is presented in [1]. In this paper, We modify a formula in [1] such that SPA can be implemented by using two small look-up tables. With this modification, all the calculations involved in this implementation involve only additions, subtractions, comparisons and table looking-ups, which leads to low computation complexity and facility in hardware implementation. Based on this modified implementation, various quantization schemes of SPA for decoding low-density parity-check (LDPC) codes are investigated. And the issues related to quantization, such as clipping levels and variables quantization, are also investigated. Simulation results show that the performance of the uniform quantization scheme is very close to that of the non-quantizaiton over the AWGN channel. Moreover, it can obtain the same performance as that of non-quantization at high SNRs.

Journal of Xidian University•Jan 1, 2004•0 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•27 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•952 citations

An improved implementation of sum-product algorithm for LDPC decoder

Zhou Wang, Bin Wu, Tianchun Ye

An improved decoding algorithm for low-density parity-check (LDPC) codes is presented. By taking advantages of the first-term Taylor’s series multiple expansion to approximate the correction term of the Jacobian logarithm used in LLR-SPA (log-likelihood ratio sum-product algorithm), we propose an algorithm which significantly simplifies the check node update computation of the optimal LLR-SPA. Besides, the parameter δ is introduced to determine suitable expansion points. The simulation result shows that the proposed method with ten expansion points when δ is set to 0.01 has almost identical performance compared with ideal SPA algorithm and outperforms both the min-sum algorithm (MS), the offset min-sum algorithm (OMS) and the normalised min-sum algorithm (NMS). The architecture of proposed method is also presented for implementation, which has reduced computational complexity and is feasible for hardware implementation.

IEICE Electronics Express•Jan 1, 2019•3 citations

Low Complexity Implementations of Sum-Product Algorithm for Decoding Low-Density Parity-Check Codes

Daesun Oh, Keshab K. Parhi

In this paper, we propose low complexity implementations of sum-product algorithm (SPA) for decoding low-density parity-check (LDPC) codes. The finite precision implementations for SPA have an important tradeoff between the decoding performance and hardware complexity caused by two dominant area consuming factors. One is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of nonlinear function Psi(x). The proposed two types of variable quantization schemes result in significant reductions of LUT sizes. Computer simulation results indicate that the performance losses of SPA with reduced LUT by proposed schemes are less than 0.05 dB compared to that of SPA with original LUT. Moreover, the proposed implementation offers a large reduction in the finite wordlength for storage of updated messages using a kind of compression technique without performance losses. As a result, using the proposed implementation based on variable quantization scheme and data compression technique, the novel proposed implementation for SPA decoder architecture offers significant reductions of 75% and 33% in hardware complexities of LUT and memories, respectively, without significant performance degradations over conventional uniform quantization scheme. Furthermore, since each LUT with variable (6:3) quantization scheme II has only 8 entries, its hardware implementation can be replaced with a small combination circuit instead of readonly-memory (ROM) for LUT

SiPS ... design and implementation - IEEE Workshop on Signal Processing Systems•Oct 1, 2006•18 citations
Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.
An efficient implementation of the Sum-Product algorithm(SPA) in the log-likelihood ratio (LLR) domain is presented in [1]. In this paper, We modify a formula in [1] such that SPA can be implemented by using two small look-up tables. With this modification, all the calculations involved in this implementation involve only additions, subtractions, comparisons and table looking-ups, which leads to low computation complexity and facility in hardware implementation. Based on this modified implementation, various quantization schemes of SPA for decoding low-density parity-check (LDPC) codes are investigated. And the issues related to quantization, such as clipping levels and variables quantization, are also investigated. Simulation results show that the performance of the uniform quantization scheme is very close to that of the non-quantizaiton over the AWGN channel. Moreover, it can obtain the same performance as that of non-quantization at high SNRs.
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.
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.
An improved decoding algorithm for low-density parity-check (LDPC) codes is presented. By taking advantages of the first-term Taylor’s series multiple expansion to approximate the correction term of the Jacobian logarithm used in LLR-SPA (log-likelihood ratio sum-product algorithm), we propose an algorithm which significantly simplifies the check node update computation of the optimal LLR-SPA. Besides, the parameter δ is introduced to determine suitable expansion points. The simulation result shows that the proposed method with ten expansion points when δ is set to 0.01 has almost identical performance compared with ideal SPA algorithm and outperforms both the min-sum algorithm (MS), the offset min-sum algorithm (OMS) and the normalised min-sum algorithm (NMS). The architecture of proposed method is also presented for implementation, which has reduced computational complexity and is feasible for hardware implementation.
In this paper, we propose low complexity implementations of sum-product algorithm (SPA) for decoding low-density parity-check (LDPC) codes. The finite precision implementations for SPA have an important tradeoff between the decoding performance and hardware complexity caused by two dominant area consuming factors. One is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of nonlinear function Psi(x). The proposed two types of variable quantization schemes result in significant reductions of LUT sizes. Computer simulation results indicate that the performance losses of SPA with reduced LUT by proposed schemes are less than 0.05 dB compared to that of SPA with original LUT. Moreover, the proposed implementation offers a large reduction in the finite wordlength for storage of updated messages using a kind of compression technique without performance losses. As a result, using the proposed implementation based on variable quantization scheme and data compression technique, the novel proposed implementation for SPA decoder architecture offers significant reductions of 75% and 33% in hardware complexities of LUT and memories, respectively, without significant performance degradations over conventional uniform quantization scheme. Furthermore, since each LUT with variable (6:3) quantization scheme II has only 8 entries, its hardware implementation can be replaced with a small combination circuit instead of readonly-memory (ROM) for LUT