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

IEEE Convention of Electrical and Electronics Engineers in Israel

Analysis of belief-propagation decoding of LDPC codes over the biAWGN channel using improved Gaussian approximation based on the mutual information measure

E. Sharon

Published Jun 26, 2003• 4 citations
Publisher

Abstract

Summary form only given. The capacity of the message-passing decoder for LDPC codes can be computed by the density evolution algorithm by iteratively computing message densities. The infinite-dimensional problem of iteratively calculating the message densities in the case of the binary input AWGN channel and the belief propagation decoder can be simplified to a one-dimensional problem by using a Gaussian approximation. By assuming Gaussian densities the density evolution simplifies to updating means of Gaussian densities. An improved Gaussian approximation algorithm is suggested for computing the capacity of the BP decoder based on the mutual information measure. An analytical method for computing the mutual information of a transmitted bit with the message corresponding to it is proposed. Using this method we can approximate the non-Gaussian message by a Gaussian message that has the same mutual information with the transmitted bit. Computationally, the algorithm is similar to the Gaussian approximation algorithm proposed in Chung (2001). For various regular LDPC codes that were examined, the algorithm computed threshold values within 0.01dB or less from the exact threshold which is an improvement over the Gaussian approximation. Furthermore, additional insight on the convergence process can be gained from EXIT charts that can be derived from the algorithm. This can assist in designing better irregular LDPC codes.

DOI
10.1109/eeei.2002.1178446

Related papers

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

Analysis of low-density parity-check codes based on EXIT functions

E. Sharon, Alexei Ashikhmin, Simon N. Litsyn

We exploit extrinsic information transfer functions of single parity-check and repetition codes over the binary input additive white Gaussian noise (biAWGN) channel, derived by the authors, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that this method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods

IEEE Transactions on Communications•Aug 1, 2006•38 citations

Density evolution analysis of spatially coupled LDPC codes over BIAWGN channel

Md. Noor‐A‐Rahim, Gottfried Lechner, Khoa D. Nguyen

In this paper, we study the density evolution analysis of spatially coupled low-density parity-check (SC-LDPC) codes over binary input additive white Gaussian noise (BIAWGN) channels under the belief propagation (BP) decoding algorithm. Using reciprocal channel approximation and Gaussian approximation, we propose averaging techniques for the density evolution of SC-LDPC codes over BIAWGN channels. We show that the proposed techniques can closely predict the decoding threshold while offering reduced complexity compared to the existing multi-edge-type density evolution.

arXiv:1510.04763•Australian Communications Theory Workshop•Jan 1, 2016•14 citations

Measure on the Performance of Belief Propagation Decoding Algorithm

He Yu

Formulas for updated rules of the belief propagation algorithm applied to low density parity check (LDPC) codes are systematically derived based on the tree and the finite state machine (FSM).The probability measure on the continuous message space is introduced to evaluate the evolution of message densities within iterative decoding rounds,and derivations of the output distributions of common binary symmetric channels and the message density evolution are given in detail.The parameterized estimation of the performance of the algorithm is also discussed.The analytic and calculable means can be used to make systematical analysis for the convergence of BP algorithms independent of channels,and can be of help in designing LDPC codes and analyzing quantization effects for the fast decoding on the purpose of practical applications of LDPC codes to real time communication systems.

Dianzi xuebao•Jan 1, 2002•0 citations

Analysis of Low-Density Parity-Check Codes Based on EXIT Functions

Eran Sharon, Alexei Ashikhmin, Simon N. Litsyn

We exploit extrinsic information tranfer functions of single parity-check and prepetition codes over the binay input additive white Gaussian noise (biAWGN) channel, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that our method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods.

IEEE Transactions on Communications•Jul 1, 2006•37 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
Summary form only given. The capacity of the message-passing decoder for LDPC codes can be computed by the density evolution algorithm by iteratively computing message densities. The infinite-dimensional problem of iteratively calculating the message densities in the case of the binary input AWGN channel and the belief propagation decoder can be simplified to a one-dimensional problem by using a Gaussian approximation. By assuming Gaussian densities the density evolution simplifies to updating means of Gaussian densities. An improved Gaussian approximation algorithm is suggested for computing the capacity of the BP decoder based on the mutual information measure. An analytical method for computing the mutual information of a transmitted bit with the message corresponding to it is proposed. Using this method we can approximate the non-Gaussian message by a Gaussian message that has the same mutual information with the transmitted bit. Computationally, the algorithm is similar to the Gaussian approximation algorithm proposed in Chung (2001). For various regular LDPC codes that were examined, the algorithm computed threshold values within 0.01dB or less from the exact threshold which is an improvement over the Gaussian approximation. Furthermore, additional insight on the convergence process can be gained from EXIT charts that can be derived from the algorithm. This can assist in designing better irregular LDPC codes.
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.
We exploit extrinsic information transfer functions of single parity-check and repetition codes over the binary input additive white Gaussian noise (biAWGN) channel, derived by the authors, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that this method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods
In this paper, we study the density evolution analysis of spatially coupled low-density parity-check (SC-LDPC) codes over binary input additive white Gaussian noise (BIAWGN) channels under the belief propagation (BP) decoding algorithm. Using reciprocal channel approximation and Gaussian approximation, we propose averaging techniques for the density evolution of SC-LDPC codes over BIAWGN channels. We show that the proposed techniques can closely predict the decoding threshold while offering reduced complexity compared to the existing multi-edge-type density evolution.
Formulas for updated rules of the belief propagation algorithm applied to low density parity check (LDPC) codes are systematically derived based on the tree and the finite state machine (FSM).The probability measure on the continuous message space is introduced to evaluate the evolution of message densities within iterative decoding rounds,and derivations of the output distributions of common binary symmetric channels and the message density evolution are given in detail.The parameterized estimation of the performance of the algorithm is also discussed.The analytic and calculable means can be used to make systematical analysis for the convergence of BP algorithms independent of channels,and can be of help in designing LDPC codes and analyzing quantization effects for the fast decoding on the purpose of practical applications of LDPC codes to real time communication systems.
We exploit extrinsic information tranfer functions of single parity-check and prepetition codes over the binay input additive white Gaussian noise (biAWGN) channel, for asymptotic performance analysis of belief propagation decoding of low-density parity-check codes. The approach is based on a Gaussian approximation (GA) of the density evolution algorithm using the mutual information measure. We show that our method allows more accurate prediction of the decoding threshold in the biAWGN channel than the earlier known GA methods.
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).