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

Journal of Communication and Information Systems

A Sorting-Based Approximation of the Sum-Product Algorithm

X.-Y.. Hu, Thomas Mittelholzer

Published Apr 30, 2003• 2 citations
Publisher

Abstract

A complexity-and delay-efficient simplification of the sum-product algorithm (SPA) for decoding lowdensity parity-check (LDPC) codes is presented. The key feature of the new algorithm consists of a modification of the complexity-intensive and delay-causing update equations at the check nodes of the factor graph of the LDPC code. The modified update equations at a check node are based on ordering the reliability values of the incoming messages and on using a balanced tree topology to achieve optimum parallel processing. Furthermore, the complexity of the new algorithm can be adjusted: the least complex version of the algorithm corresponds to the so-called min-sum approximation, and the most complex version gives the full SPA.

DOI
10.14209/jcis.2003.6

Related papers

A New Reduced-Complexity Decoding Algorithm for LDPC Codes

Guiyuan Sun, Jiejun Jin, Wei Yao +1 more

This letter proposes a new algorithm for the check node update in the decoding of low-density parity-check (LDPC) codes. The proposed algorithm is based on a new approximation formula of standard sum-product algorithm (SPA) which can reduce the approximation error of min-sum algorithm (MSA) and has almost the same performance as sum-product algorithm (SPA) under both floating precision operation and fixed-point operation. Besides, the new approximation formula can be implemented in simple structures competitive with MSA.

IEICE Transactions on Communications•Jul 1, 2007•2 citations

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

Xiao-Yu Hu, Evangelos S. Eleftheriou, D.-M. Arnold +1 more

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.

Globecom•Nov 13, 2002•375 citations

Low complexity algorithm for decoding LDPC codes

Wenjuan Zhang

A low complexity algorithm(combined sum-product algorithm,CSPA)for decoding lowdensity parity-check codes is proposed,which works based on the sum-product algorithm(SPA)at first,and then switches to the selective node update(SNU)algorithm after most of the message has been converged.The computer simulations show that at a moderate code length,the proposed algorithm can overcome the deficiencies in SNU algorithm for its slow convergence rate and high error platform and effectively reduce the complexity in computation with little loss in the BER performance when compared with SPA.

Journal of Naval University of Engineering•Jan 1, 2010•0 citations

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

A Low-complexity Iterative Decoding Algorithm for LDPC Codes

Pan Yu

Among the decoding algorithms for low-density parity-check(LDPC) code,sum-product algorithm(SPA) has the optimal performance but high complexity,while min-sum algorithm has simple implementation complexity but worse performance.Considering this performance-complexity contradiction,some modified min-sum algorithms are proposed.In this paper,researches are done based on one of the modified min-sum algorithms that is close to SPA in performance but the way modifying fraction works is simplified.Simplified algorithm remains similar in performance to sum-product algorithm but has a remarkably reduced implementation complexity.

Telecommunication Engineering•Jan 1, 2006•1 citation

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
A complexity-and delay-efficient simplification of the sum-product algorithm (SPA) for decoding lowdensity parity-check (LDPC) codes is presented. The key feature of the new algorithm consists of a modification of the complexity-intensive and delay-causing update equations at the check nodes of the factor graph of the LDPC code. The modified update equations at a check node are based on ordering the reliability values of the incoming messages and on using a balanced tree topology to achieve optimum parallel processing. Furthermore, the complexity of the new algorithm can be adjusted: the least complex version of the algorithm corresponds to the so-called min-sum approximation, and the most complex version gives the full SPA.
This letter proposes a new algorithm for the check node update in the decoding of low-density parity-check (LDPC) codes. The proposed algorithm is based on a new approximation formula of standard sum-product algorithm (SPA) which can reduce the approximation error of min-sum algorithm (MSA) and has almost the same performance as sum-product algorithm (SPA) under both floating precision operation and fixed-point operation. Besides, the new approximation formula can be implemented in simple structures competitive with MSA.
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.
A low complexity algorithm(combined sum-product algorithm,CSPA)for decoding lowdensity parity-check codes is proposed,which works based on the sum-product algorithm(SPA)at first,and then switches to the selective node update(SNU)algorithm after most of the message has been converged.The computer simulations show that at a moderate code length,the proposed algorithm can overcome the deficiencies in SNU algorithm for its slow convergence rate and high error platform and effectively reduce the complexity in computation with little loss in the BER performance when compared with SPA.
Among the decoding algorithms for low-density parity-check(LDPC) code,sum-product algorithm(SPA) has the optimal performance but high complexity,while min-sum algorithm has simple implementation complexity but worse performance.Considering this performance-complexity contradiction,some modified min-sum algorithms are proposed.In this paper,researches are done based on one of the modified min-sum algorithms that is close to SPA in performance but the way modifying fraction works is simplified.Simplified algorithm remains similar in performance to sum-product algorithm but has a remarkably reduced implementation complexity.
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.