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

International Conference on Communications, Circuits and Systems

Density evolution method and threshold decision for irregular LDPC codes

Lin Wang, Juan Xiao, Guanrong Chen

Published Jan 1, 2004• 10 citations
Publisher

Abstract

Density evolution is a new method for analyzing the asymptotic performance of network capability approaching error-correcting codes. For irregular LDPC codes with message-passing decoding, the density evolution method can track the messages to find out the threshold, enabling optimization of the degree distribution. In this paper, the principle of density evolution combined with the decoding process is firstly explored. Then, two algorithms for programming the evolution proceeding are discussed: the discretized density evolution and the Gaussian approximation, as well as their application conditions. Finally, simulation results are presented.

DOI
10.1109/icccas.2004.1345932

Related papers

Analysis of threshold of regular and irregular LDPC codes using Gaussian approximation

Chia‐Lu Ho

We present the formulas for searching for the thresholds of regular and irregular low-density parity-check (LDPC) codes under message-passing (MP) algorithm. A Gaussian approximation is applied to studying the evolution of the means of the messages of the variable nodes and the check nodes. Accurate numerical integration methods by using transformations are shown for evaluating the expected values of the message of the check nodes. Tables are built first and interpolations are used for further evaluations. Two curves are used to locate the threshold. We utilize an iterative decoding tunnel between these two curves and study the decoding performance by evaluating conditions of the derivatives of these two curves. Using this method the performance of both regular and irregular LDPC codes can be studied in a unified manner without using simulation.

Wireless Telecommunications Symposium•May 1, 2009•2 citations

Research of Density Evolution of LDPC Codes over Rice Channels

Hua Xu, Chengqi Xu

Noise threshold of Low Density Parity Check (LDPC) codes ensemble could be calculated by density evolution of the decoding messages. According to the threshold, performance of the decoding algorithm could be evaluated and degree distribution pairs of irregular LDPC codes also might be optimized. In this paper, for regular LDPC codes on Rice channel, Discrete Density Evolution(DDE) for BP,BP-based and offset BP-based decoding algorithm were compared on different quantization level and step. Furthermore, degree distribution pairs of the irregular LDPC codes were optimized on Rice channel, which was based on DDE for offset BP-based decoding algorithm, the corresponding threshold is also calculated. Finally, the Probability Mass Function (PMF) evolution curve of optimized irregular LDPC codes with code rate 1/2 on Rice channel is given.

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY•Oct 19, 2006•0 citations

A New Density Evolution Approximation for LDPC and Multi-Edge Type LDPC Codes

Sachini Jayasooriya, Mahyar Shirvanimoghaddam, Lawrence Ong +2 more

This paper considers density evolution for low-density parity-check (LDPC) and multi-edge type LDPC (MET-LDPC) codes over the binary input additive white Gaussian noise channel. We first analyze three single-parameter Gaussian approximations for density evolution and discuss their accuracy under several conditions, namely, at low rates, with punctured and degree-one variable nodes. We observe that the assumption of symmetric Gaussian distribution for the density-evolution messages is not accurate in the early decoding iterations, particularly at low rates and with punctured variable nodes. Thus, single-parameter Gaussian approximation methods produce very poor results in these cases. Based on these observations, we then introduce a new density evolution approximation algorithm for LDPC and MET-LDPC codes. Our method is a combination of full density evolution and a single-parameter Gaussian approximation, where we assume a symmetric Gaussian distribution only after density-evolution messages closely follow a symmetric Gaussian distribution. Our method significantly improves the accuracy of the code threshold estimation. Additionally, the proposed method significantly reduces the computational time of evaluating the code threshold compared with full density evolution thereby making it more suitable for code design.

arXiv:1605.04665•IEEE Transactions on Communications•Jan 1, 2016•29 citations

Analysis of sum-product decoding of low-density parity-check codes using a Gaussian approximation

Sae-Young Chung, Tom Richardson, Rudiger L. Urbanke

Density evolution is an algorithm for computing the capacity of low-density parity-check (LDPC) codes under message-passing decoding. For memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels and sum-product decoders, we use a Gaussian approximation for message densities under density evolution to simplify the analysis of the decoding algorithm. We convert the infinite-dimensional problem of iteratively calculating message densities, which is needed to find the exact threshold, to a one-dimensional problem of updating the means of the Gaussian densities. This simplification not only allows us to calculate the threshold quickly and to understand the behavior of the decoder better, but also makes it easier to design good irregular LDPC codes for AWGN channels. For various regular LDPC codes we have examined, thresholds can be estimated within 0.1 dB of the exact value. For rates between 0.5 and 0.9, codes designed using the Gaussian approximation perform within 0.02 dB of the best performing codes found so far by using density evolution when the maximum variable degree is 10. We show that by using the Gaussian approximation, we can visualize the sum-product decoding algorithm. We also show that the optimization of degree distributions can be understood and done graphically using the visualization.

IEEE Transactions on Information Theory•Jan 1, 2001•1,150 citations

On Gaussian Approximation for Density Evolution of Low-Density Parity-Check Codes

Minyue Fu

This paper is concerned with density evolution for iterative decoding of low-density parity-check (LDPC) codes. We first study the problem of density evolution computation for regular LDPC codes. For this, we propose a simple computational algorithm based on the ergodicity theory. This method is shown to match very well with explicit calculations of density functions. The second problem we study is about the approach of Gaussian approximation to density evolution. We point out that it is inappropriate to use the mean of the density only to model the iterative decoding process. Instead, both the mean and variance are needed for Gaussian approximation. Finally, we consider the problem of density evolution for irregular LDPC codes. For this, we extend the density evolution algorithm for regular LDPC codes to irregular LDPC codes. We then illustrate that Gaussian approximation is also valid provided that the degree distributions are not wide. A dynamic model is also presented based on Gaussian approximation.

International Conference on Communications•Jan 1, 2006•19 citations

Statistical-Based Density Evolution Algorithm for Nonbinary Low-Density Parity-Check Codes

Jie Wu, Minjian Zhao, Jie Zhong +2 more

A statistical-based density evolution algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. It is applicable to both regular and irregular codes under study. The algorithm proposed serves as a tool to analyze the performance limit for iterative decoding of nonbinary LDPC codes, which in turn guides code design. Specifically, it provides approximated evaluations of convergence thresholds for codes given specific degree distributions. It is shown that, for a class of quasi-cyclic (QC) structured extended irregular repeat-accumulate (SeIRA) nonbinary LDPC codes, degree distributions can be optimized via the algorithm proposed. Simulation results exhibit that the nonbinary LDPC codes designed outperform the optimized binary LDPC codes on the AWGN channel with similar code length and rate in terms of bits. Performance gap between the binary and nonbinary LDPC codes is larger in the scenario of higher order modulation.

IEEE Vehicular Technology Conference•Sep 1, 2011•1 citation
Density evolution is a new method for analyzing the asymptotic performance of network capability approaching error-correcting codes. For irregular LDPC codes with message-passing decoding, the density evolution method can track the messages to find out the threshold, enabling optimization of the degree distribution. In this paper, the principle of density evolution combined with the decoding process is firstly explored. Then, two algorithms for programming the evolution proceeding are discussed: the discretized density evolution and the Gaussian approximation, as well as their application conditions. Finally, simulation results are presented.
We present the formulas for searching for the thresholds of regular and irregular low-density parity-check (LDPC) codes under message-passing (MP) algorithm. A Gaussian approximation is applied to studying the evolution of the means of the messages of the variable nodes and the check nodes. Accurate numerical integration methods by using transformations are shown for evaluating the expected values of the message of the check nodes. Tables are built first and interpolations are used for further evaluations. Two curves are used to locate the threshold. We utilize an iterative decoding tunnel between these two curves and study the decoding performance by evaluating conditions of the derivatives of these two curves. Using this method the performance of both regular and irregular LDPC codes can be studied in a unified manner without using simulation.
Noise threshold of Low Density Parity Check (LDPC) codes ensemble could be calculated by density evolution of the decoding messages. According to the threshold, performance of the decoding algorithm could be evaluated and degree distribution pairs of irregular LDPC codes also might be optimized. In this paper, for regular LDPC codes on Rice channel, Discrete Density Evolution(DDE) for BP,BP-based and offset BP-based decoding algorithm were compared on different quantization level and step. Furthermore, degree distribution pairs of the irregular LDPC codes were optimized on Rice channel, which was based on DDE for offset BP-based decoding algorithm, the corresponding threshold is also calculated. Finally, the Probability Mass Function (PMF) evolution curve of optimized irregular LDPC codes with code rate 1/2 on Rice channel is given.
This paper considers density evolution for low-density parity-check (LDPC) and multi-edge type LDPC (MET-LDPC) codes over the binary input additive white Gaussian noise channel. We first analyze three single-parameter Gaussian approximations for density evolution and discuss their accuracy under several conditions, namely, at low rates, with punctured and degree-one variable nodes. We observe that the assumption of symmetric Gaussian distribution for the density-evolution messages is not accurate in the early decoding iterations, particularly at low rates and with punctured variable nodes. Thus, single-parameter Gaussian approximation methods produce very poor results in these cases. Based on these observations, we then introduce a new density evolution approximation algorithm for LDPC and MET-LDPC codes. Our method is a combination of full density evolution and a single-parameter Gaussian approximation, where we assume a symmetric Gaussian distribution only after density-evolution messages closely follow a symmetric Gaussian distribution. Our method significantly improves the accuracy of the code threshold estimation. Additionally, the proposed method significantly reduces the computational time of evaluating the code threshold compared with full density evolution thereby making it more suitable for code design.
Density evolution is an algorithm for computing the capacity of low-density parity-check (LDPC) codes under message-passing decoding. For memoryless binary-input continuous-output additive white Gaussian noise (AWGN) channels and sum-product decoders, we use a Gaussian approximation for message densities under density evolution to simplify the analysis of the decoding algorithm. We convert the infinite-dimensional problem of iteratively calculating message densities, which is needed to find the exact threshold, to a one-dimensional problem of updating the means of the Gaussian densities. This simplification not only allows us to calculate the threshold quickly and to understand the behavior of the decoder better, but also makes it easier to design good irregular LDPC codes for AWGN channels. For various regular LDPC codes we have examined, thresholds can be estimated within 0.1 dB of the exact value. For rates between 0.5 and 0.9, codes designed using the Gaussian approximation perform within 0.02 dB of the best performing codes found so far by using density evolution when the maximum variable degree is 10. We show that by using the Gaussian approximation, we can visualize the sum-product decoding algorithm. We also show that the optimization of degree distributions can be understood and done graphically using the visualization.
This paper is concerned with density evolution for iterative decoding of low-density parity-check (LDPC) codes. We first study the problem of density evolution computation for regular LDPC codes. For this, we propose a simple computational algorithm based on the ergodicity theory. This method is shown to match very well with explicit calculations of density functions. The second problem we study is about the approach of Gaussian approximation to density evolution. We point out that it is inappropriate to use the mean of the density only to model the iterative decoding process. Instead, both the mean and variance are needed for Gaussian approximation. Finally, we consider the problem of density evolution for irregular LDPC codes. For this, we extend the density evolution algorithm for regular LDPC codes to irregular LDPC codes. We then illustrate that Gaussian approximation is also valid provided that the degree distributions are not wide. A dynamic model is also presented based on Gaussian approximation.
A statistical-based density evolution algorithm is proposed for nonbinary low-density parity-check (LDPC) codes. It is applicable to both regular and irregular codes under study. The algorithm proposed serves as a tool to analyze the performance limit for iterative decoding of nonbinary LDPC codes, which in turn guides code design. Specifically, it provides approximated evaluations of convergence thresholds for codes given specific degree distributions. It is shown that, for a class of quasi-cyclic (QC) structured extended irregular repeat-accumulate (SeIRA) nonbinary LDPC codes, degree distributions can be optimized via the algorithm proposed. Simulation results exhibit that the nonbinary LDPC codes designed outperform the optimized binary LDPC codes on the AWGN channel with similar code length and rate in terms of bits. Performance gap between the binary and nonbinary LDPC codes is larger in the scenario of higher order modulation.