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

Frontiers of Information Technology & Electronic Engineering

An improved low-complexity sum-product decoding algorithm for low-density parity-check codes

Michaelraj Kingston Roberts, Ramesh Jayabalan

Published Jun 1, 2015• 12 citations
Publisher

Abstract

In this paper, an improved low-complexity sum-product decoding algorithm is presented for low-density parity-check (LDPC) codes. In the proposed algorithm, reduction in computational complexity is achieved by utilizing fast Fourier transform (FFT) with time shift in the check node process. The improvement in the decoding performance is achieved by utilizing an optimized integer constant in the variable node process. Simulation results show that the proposed algorithm achieves an overall coding gain improvement ranging from 0.04 to 0.46 dB. Moreover, when compared with the sum-product algorithm (SPA), the proposed decoding algorithm can achieve a reduction of 42%–67% of the total number of arithmetic operations required for the decoding process.

DOI
10.1631/fitee.1400269

Related papers

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

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

Performance and processing time enhancement of LDPC decoder using stopping node modified Sum Product algorithm

Nguyen Thi Dieu Linh, Gang Wang, Abdelhafidh Barkana +1 more

In this paper, a new method based on Sum Product algorithm (SPA) using stopping node to reduce computing complexity on Low Density Parity Check Codes (LDPC) decoding algorithms is presented. We show how to make early decisions to reduce calculation of the next iteration. Simulation results show that performance of iterative decoding for LDPC codes using stopping node algorithm can reduce up to 10 times computational complexity with maintaining quality level.

IEEE International Conference on Communication Technology (ICCT)•Sep 1, 2011•2 citations

FFT Based Sum-Product Algorithm for Decoding LDPC Lattices

Lida Safarnejad, Mohammad‐Reza Sadeghi

LDPC lattices were introduced by Sadeghi et al. in [13] and have a good performance under generalized minsum and sum-product algorithms. The high complexity of these algorithms is mainly due to the search for local valid codewords in each check node process. In addition, when the dimension of such lattices is increased, these decoding algorithms are very time-consuming. In this paper, we propose an FFT based sum-product algorithm to decode LDPC lattices. In the check node process, using the FFT method reduces the check node complexity from O(dcg2) to O(dcg log g) where dcis the degree of a check equation and g is the alphabet size of an LDPC lattice. As a result, with almost the same complexity cost, we have a significant improvement over the performance of the minsum based decoding 2-level LDPC lattices with the symbol error probability smaller than 10-5at SNR = 1.5 dB.

IEEE Communications Letters•Aug 3, 2012•20 citations

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 quantization algorithm for low-density parity-check code decoding

Jianhua Lü

A variable step uniform quantization(VSUQ) sum-product algorithm(SPA) was developed to reduce the hardware complexity of low-density parity-check(LDPC) code decoding.The extrinsic information in the check nodes and bit nodes is quantized in the same quantization step.Then,the quantization steps for the check nodes and bit nodes are multiplied and divided by a predetermined parameter.Simulation and implementation using a field programmable gate array(FPGA) show that the performance degradation in the algorithm is within 0.1 dB comparing to the unquantized standard SPA,while reducing the hardware size by 50% comparing to a uniform quantization SPA with the same performance.

Journal of Tsinghua University(Science and Technology)•Jan 1, 2007•0 citations
In this paper, an improved low-complexity sum-product decoding algorithm is presented for low-density parity-check (LDPC) codes. In the proposed algorithm, reduction in computational complexity is achieved by utilizing fast Fourier transform (FFT) with time shift in the check node process. The improvement in the decoding performance is achieved by utilizing an optimized integer constant in the variable node process. Simulation results show that the proposed algorithm achieves an overall coding gain improvement ranging from 0.04 to 0.46 dB. Moreover, when compared with the sum-product algorithm (SPA), the proposed decoding algorithm can achieve a reduction of 42%–67% of the total number of arithmetic operations required for the decoding process.
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
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.
LDPC lattices were introduced by Sadeghi et al. in [13] and have a good performance under generalized minsum and sum-product algorithms. The high complexity of these algorithms is mainly due to the search for local valid codewords in each check node process. In addition, when the dimension of such lattices is increased, these decoding algorithms are very time-consuming. In this paper, we propose an FFT based sum-product algorithm to decode LDPC lattices. In the check node process, using the FFT method reduces the check node complexity from O(dcg2) to O(dcg log g) where dcis the degree of a check equation and g is the alphabet size of an LDPC lattice. As a result, with almost the same complexity cost, we have a significant improvement over the performance of the minsum based decoding 2-level LDPC lattices with the symbol error probability smaller than 10-5at SNR = 1.5 dB.
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.
A variable step uniform quantization(VSUQ) sum-product algorithm(SPA) was developed to reduce the hardware complexity of low-density parity-check(LDPC) code decoding.The extrinsic information in the check nodes and bit nodes is quantized in the same quantization step.Then,the quantization steps for the check nodes and bit nodes are multiplied and divided by a predetermined parameter.Simulation and implementation using a field programmable gate array(FPGA) show that the performance degradation in the algorithm is within 0.1 dB comparing to the unquantized standard SPA,while reducing the hardware size by 50% comparing to a uniform quantization SPA with the same performance.