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

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

Minyue Fu

Published Jan 1, 2006• 19 citations
Publisher

Abstract

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.

DOI
10.1109/icc.2006.254895

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

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

Density Evolution for Nonbinary LDPC Codes Under Gaussian Approximation

Ge Li, I.J. Fair, Witold A. Krzymień

This paper extends the work on density evolution for binary low-density parity-check (LDPC) codes with Gaussian approximation to LDPC codes over GF(q) . We first generalize the definition of channel symmetry for nonbinary inputs to include q-ary phase-shift keying (PSK) modulated channels for prime q and binary-modulated channels for q that is a power of 2. For the well-defined q-ary-input symmetric-output channel, we prove that under the Gaussian assumption, the density distribution for messages undergoing decoding is fully characterized by (q-1) quantities. Assuming uniform edge weights, we further show that the density of messages computed by the check node decoder (CND) is fully defined by a single number. We then present the approximate density evolution for regular and irregular LDPC codes, and show that the (q-1) -dimensional integration involved can be simplified using a dimensionality reduction algorithm for the important case of q=2p. Through application of approximate density evolution and linear programming, we optimize the degree distribution of LDPC codes over GF(3) and GF(4). The optimized irregular LDPC codes demonstrate performance close to the Shannon capacity for long codewords. We also design GF(q) codes for high-order modulation by using the idea of a channel adapter. We find that codes designed in this fashion outperform those optimized specifically for the binary additive white Gaussian noise (AWGN) channel for a short codewords and a spectral efficiency of 2 bits per channel use (b/cu).

IEEE Transactions on Information Theory•Feb 26, 2009•80 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

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

Thresholds Calculation of LDPC Code Ensembles Using a Novel Gaussian Approximation Algorithm

Piming Ma, Kyungsup Kwak

A novel Gaussian approximation algorithm is proposed for calculating the thresholds of low-density parity- check (LDPC) code ensembles under sum-product decoding. The updating rules of means and error probability are derived. Numerical results show that the thresholds obtained by the proposed algorithm closely coincide with the values computed by density evolution (DE). Moreover, our algorithm can calculate the thresholds of irregular LDPC codes with higher accuracy than the algorithm proposed by Lehmann and Maggio.

IEEE Wireless Communications and Networking Conference•Apr 1, 2009•3 citations
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.
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.
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 extends the work on density evolution for binary low-density parity-check (LDPC) codes with Gaussian approximation to LDPC codes over GF(q) . We first generalize the definition of channel symmetry for nonbinary inputs to include q-ary phase-shift keying (PSK) modulated channels for prime q and binary-modulated channels for q that is a power of 2. For the well-defined q-ary-input symmetric-output channel, we prove that under the Gaussian assumption, the density distribution for messages undergoing decoding is fully characterized by (q-1) quantities. Assuming uniform edge weights, we further show that the density of messages computed by the check node decoder (CND) is fully defined by a single number. We then present the approximate density evolution for regular and irregular LDPC codes, and show that the (q-1) -dimensional integration involved can be simplified using a dimensionality reduction algorithm for the important case of q=2p. Through application of approximate density evolution and linear programming, we optimize the degree distribution of LDPC codes over GF(3) and GF(4). The optimized irregular LDPC codes demonstrate performance close to the Shannon capacity for long codewords. We also design GF(q) codes for high-order modulation by using the idea of a channel adapter. We find that codes designed in this fashion outperform those optimized specifically for the binary additive white Gaussian noise (AWGN) channel for a short codewords and a spectral efficiency of 2 bits per channel use (b/cu).
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.
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.
A novel Gaussian approximation algorithm is proposed for calculating the thresholds of low-density parity- check (LDPC) code ensembles under sum-product decoding. The updating rules of means and error probability are derived. Numerical results show that the thresholds obtained by the proposed algorithm closely coincide with the values computed by density evolution (DE). Moreover, our algorithm can calculate the thresholds of irregular LDPC codes with higher accuracy than the algorithm proposed by Lehmann and Maggio.