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

arXiv:cs/0509014 · IEEE Transactions on Information Theory

Density Evolution for Asymmetric Memoryless Channels

C.-C. Wang, Sanjeev R. Kulkarni, H.V. Poor

Published Nov 22, 2005• 55 citations
arXivHTMLPDF

Abstract

Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), binary additive white Gaussian noise (BiAWGN) channels, etc. This paper generalizes density evolution for asymmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g., z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed-size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation (BP) algorithm even when only symmetric channels are considered. Hence, the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.

DOI
10.1109/tit.2005.858931

Related papers

Density Evolution for Asymmetric Memoryless Channels

Chih-chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Abstract — Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution (DE) has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian noise channels, etc. This paper generalizes density evolution for non-symmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g. z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation algorithm even when only symmetric channels are considered. Hence the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels. Index Terms — Low-density parity-check (LDPC) codes, density evolution, sum-product algorithm, asymmetric channels, z-channels, rank of random matrices. I.

•Jan 1, 2003•64 citations

Density Evolution for Asymmetric Memoryless Channels: The Perfect Projection Condition and the Typicality of the Linear LDPC Code Ensemble

Chih-Chun Wang, Sanjeev R. Kulkarni, H. Vincent Poor

Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian channels, etc. This paper generalizes density evolution for non-symmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g. z-channels, binary asymmetric channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation algorithm even when only

•Jan 1, 2004•1 citation

On the Typicality of the Linear Code Among the LDPC Coset Code Ensemble

Chih-Chun Wang, H. Vincent Poor, Sanjeev R. Kulkarni

Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes on memoryless binary-input/symmetric-output channels. The case of non-symmetric channels is tackled either by the LDPC coset code ensemble (a channel symmetrizing argument) or by the generalized DE for linear codes on non-symmetric channels. Existing simulations show that the bit error rate performances of these two different approaches are nearly identical. This paper explains this phenomenon by proving that as the minimum check node degree $d_c$ becomes sufficiently large, the performance discrepancy of the linear and the coset LDPC codes is theoretically indistinguishable. This typicality of linear codes among the LDPC coset code ensemble provides insight into the concentration theorem of LDPC coset codes.

arXiv:cs/0502084•Feb 22, 2005•4 citations

On LDPC codes over symmetric channels

Hamid Saeedi, Hossein Pishro-Nik

In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.

IEEE Information Theory Workshop (ITW)•Jun 1, 2009•0 citations

Performance Analysis of Iterative Decoding Algorithms with Memory over Memoryless Channels

Emil Janulewicz, Amir H. Banihashemi

Density evolution is often used to determine the performance of an ensemble of low-density parity-check (LDPC) codes under iterative message-passing algorithms. Conventional density evolution techniques over memoryless channels are based on the assumption that messages at iteration \ell are only a function of the messages at iteration \ell -1 and possibly the channel output. This assumption is valid for many algorithms such as standard belief propagation (BP) and min-sum (MS) algorithms. However, there are other important iterative algorithms such as successive relaxation (SR) versions of BP and MS, and differential decoding with binary message passing (DD-BMP) algorithm of Mobini et al., for which this assumption is not valid. The reason is the introduction of memory in these algorithms. In this work, we propose a model for iterative decoding algorithms with memory which covers SR and DD-BMP algorithms as special cases. Based on this model, we derive a Bayesian network for iterative algorithms with memory over memoryless channels and use this representation to analyze the performance of the algorithms using density evolution. The density evolution technique is developed based on truncating the memory of the decoding process and approximating it with a finite order Markov process, and can be implemented efficiently. As an example, we apply our technique to analyze the performance of DD-BMP on regular LDPC code ensembles, and make a number of interesting observations with regard to the performance/complexity tradeoff of DD-BMP in comparison with BP and MS algorithms. The model presented in this paper is based on certain simplifying assumptions about the memory structure of iterative algorithms such as the existence of memory only at the output of variable nodes in the code's Tanner graph rather than at both outputs of variable and check nodes. The Bayesian network framework introduced here however, can still be used to analyze the more general scenarios.

IEEE Transactions on Communications•Sep 3, 2012•7 citations

Performance analysis of iterative decoding algorithms with memory

Emil Janulewicz, Amir H. Banihashemi

Density evolution is often used to determine the performance of an ensemble of low-density parity-check (LDPC) codes under iterative message-passing algorithms. Conventional density evolution techniques over memoryless channels are based on the independence assumption amongst all the processed messages in variable and check nodes. This assumption is valid for many algorithms such as standard belief propagation (BP) and min-sum (MS) algorithms. However, there are other important iterative algorithms such as successive relaxation (SR) versions of BP and MS, and differential decoding with binary message passing (DD-BMP) algorithm of Mobini et. al., for which this assumption is not valid. The dependence created among messages for these algorithms is due to the introduction of memory in the iterative algorithm. In this work, we propose a model for iterative decoding algorithms with memory which covers SR and DD-BMP algorithms as special cases. Based on this model, we derive a Bayesian network for iterative algorithms with memory over memoryless channels and use this representation to analyze the algorithms using density evolution. The density evolution technique is developed based on truncating the memory of the decoding process and approximating it with a finite order Markov process, and can be implemented efficiently. As an example, we apply our technique to analyze the performance of DD-BMP on regular LDPC code ensembles, and make a number of interesting observations with regard to the performance/complexity trade off of DD-BMP in comparison with BP and MS algorithms.

IEEE Information Theory Workshop (ITW)•Jan 1, 2010•2 citations
Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels (BECs), binary symmetric channels (BSCs), binary additive white Gaussian noise (BiAWGN) channels, etc. This paper generalizes density evolution for asymmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g., z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed-size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation (BP) algorithm even when only symmetric channels are considered. Hence, the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.
Abstract — Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution (DE) has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian noise channels, etc. This paper generalizes density evolution for non-symmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g. z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation algorithm even when only symmetric channels are considered. Hence the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels. Index Terms — Low-density parity-check (LDPC) codes, density evolution, sum-product algorithm, asymmetric channels, z-channels, rank of random matrices. I.
Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian channels, etc. This paper generalizes density evolution for non-symmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g. z-channels, binary asymmetric channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation algorithm even when only
Density evolution (DE) is one of the most powerful analytical tools for low-density parity-check (LDPC) codes on memoryless binary-input/symmetric-output channels. The case of non-symmetric channels is tackled either by the LDPC coset code ensemble (a channel symmetrizing argument) or by the generalized DE for linear codes on non-symmetric channels. Existing simulations show that the bit error rate performances of these two different approaches are nearly identical. This paper explains this phenomenon by proving that as the minimum check node degree dcd_cdc​ becomes sufficiently large, the performance discrepancy of the linear and the coset LDPC codes is theoretically indistinguishable. This typicality of linear codes among the LDPC coset code ensemble provides insight into the concentration theorem of LDPC coset codes.
In the past decade, there has been tremendous amount of research on the analysis and design of the Low-Density Parity-Check (LDPC) codes with belief propagation decoding over different types of Binary-Input Output-Symmetric Memoryless (BIOSM) channels. However, with the exception of the Binary Erasure Channel (BEC), analytical results on LDPC codes over such channels are limited and most results are based on numerical methods and optimization. In particular, systematic design of provably capacity achieving sequences of LDPC code ensembles over general class of BIOSM channels has remained a fundamental open problem. Such sequences have been designed only for the binary erasure channel (BEC). In this paper, we first prove some novel analytical properties of the LDPC code ensembles over BIOSM channels. In particular, we prove a result that generalizes the previously known stability condition over symmetric channels. This suggests that a modified version of the flatness condition, a property which has been shown to be critical for capacity achieving sequences over the BEC, can be used to devise capacity achieving sequences for general class of BIOSM channels. Based on this assumption, we propose a method which could result in the systematic design of such sequences over BIOSM channels. Numerical evidence is promising and provides a consistent convergence behavior to capacity over the considered BIOSM channels as the average check node degree increases.
Density evolution is often used to determine the performance of an ensemble of low-density parity-check (LDPC) codes under iterative message-passing algorithms. Conventional density evolution techniques over memoryless channels are based on the assumption that messages at iteration \ell are only a function of the messages at iteration \ell -1 and possibly the channel output. This assumption is valid for many algorithms such as standard belief propagation (BP) and min-sum (MS) algorithms. However, there are other important iterative algorithms such as successive relaxation (SR) versions of BP and MS, and differential decoding with binary message passing (DD-BMP) algorithm of Mobini et al., for which this assumption is not valid. The reason is the introduction of memory in these algorithms. In this work, we propose a model for iterative decoding algorithms with memory which covers SR and DD-BMP algorithms as special cases. Based on this model, we derive a Bayesian network for iterative algorithms with memory over memoryless channels and use this representation to analyze the performance of the algorithms using density evolution. The density evolution technique is developed based on truncating the memory of the decoding process and approximating it with a finite order Markov process, and can be implemented efficiently. As an example, we apply our technique to analyze the performance of DD-BMP on regular LDPC code ensembles, and make a number of interesting observations with regard to the performance/complexity tradeoff of DD-BMP in comparison with BP and MS algorithms. The model presented in this paper is based on certain simplifying assumptions about the memory structure of iterative algorithms such as the existence of memory only at the output of variable nodes in the code's Tanner graph rather than at both outputs of variable and check nodes. The Bayesian network framework introduced here however, can still be used to analyze the more general scenarios.
Density evolution is often used to determine the performance of an ensemble of low-density parity-check (LDPC) codes under iterative message-passing algorithms. Conventional density evolution techniques over memoryless channels are based on the independence assumption amongst all the processed messages in variable and check nodes. This assumption is valid for many algorithms such as standard belief propagation (BP) and min-sum (MS) algorithms. However, there are other important iterative algorithms such as successive relaxation (SR) versions of BP and MS, and differential decoding with binary message passing (DD-BMP) algorithm of Mobini et. al., for which this assumption is not valid. The dependence created among messages for these algorithms is due to the introduction of memory in the iterative algorithm. In this work, we propose a model for iterative decoding algorithms with memory which covers SR and DD-BMP algorithms as special cases. Based on this model, we derive a Bayesian network for iterative algorithms with memory over memoryless channels and use this representation to analyze the algorithms using density evolution. The density evolution technique is developed based on truncating the memory of the decoding process and approximating it with a finite order Markov process, and can be implemented efficiently. As an example, we apply our technique to analyze the performance of DD-BMP on regular LDPC code ensembles, and make a number of interesting observations with regard to the performance/complexity trade off of DD-BMP in comparison with BP and MS algorithms.