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 Communications Letters

Stability Outage Analysis for LDPC Codes

Dieter Duyck, Joseph J. Boutros, Marc Moeneclaey

Published Sep 28, 2011• 1 citation
Publisher

Abstract

For a given channel instance and a fixed LDPC ensemble, a stability outage event is defined by the density evolution being unstable at the origin. The probability of such an event, referred to as Stability Outage Probability, is a useful lower bound for the word error rate. We formulate the stability outage probability for block fading channels and we introduce the stability diversity order. As a direct application, we show how the class of capacity-achieving ensembles on the erasure channel is bounded away from the outage limit on a block fading channel.

DOI
10.1109/lcomm.2011.090611.111559

Related papers

Stability Outage Analysis for LDPC Codes

Xiang Zhao Li, Chao Zhang

stability outage probability of LDPC code is caused by the density evolution on given channel, we formulate the stability outage probability for block fading channel by researching the SOP for the BEC channel and AWGN channel, Simulation results show that how the class of capacity-achieving ensembles on the erasure channel is bounded away from the outage limit on a block fading channel by studying of the SOP for AWGN channel and BEC channel.

Advanced materials research•Sep 1, 2013•0 citations

Asymptotic and finite-length analysis of low-density parity-check codes

Di, Changyan

This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.

•Jan 1, 2004•13 citations

Density evolution, thresholds and the stability condition for non-binary LDPC codes

Vishwambhar Rathi, Rudiger L. Urbanke

The density evolution equations for non-binary low-density parity-check (LDPC) ensembles when transmission takes place over the binary erasure channel are derived. Ensembles defined with respect to the general linear group over the binary field are introduced. For these ensembles the density evolution equations can be written compactly. The density evolution for the general linear group helps in understanding the density evolution for codes defined with respect to finite fields. Thresholds are computed for different alphabet sizes for various LDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. The stability condition for non-binary LDPC ensembles over any binary memoryless symmetric channel is stated. Upper bounds on the MAP thresholds for various non-binary ensembles based on EXIT curves and the area theorem are given.

arXiv:cs/0511100•IEE Proceedings - Communications•Jan 1, 2005•102 citations

Weight distributions of multi-edge type LDPC codes

Kenta Kasai, Tomoharu Awano, David Declercq +2 more

For a (lambda(x); rho(x)) standard irregular LDPC code ensemble, the growth rate of the average weight distribution for small relative weight omega is given by log(lambda'(0)rho'(1))omega + O(omega2) in the limit of code length n. If lambda'(0)rho'(1) < 1, there exist exponentially few code words of small linear weight, as n tends to infinity. It is known that the condition coincides with the stability condition of density evolution over the erasure channels with the erasure probability 1. In this paper, we show that this is also the case with multi-edge type LDPC (MET-LDPC) codes. MET-LDPC codes are generalized structured LDPC codes introduced by Richardson and Urbanke. The parameter corresponding lambda'(0)rho'(1) appearing in the conditions for MET-LDPC codes is given by the spectral radius of the matrix defined by extended degree distributions.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•10 citations

Finite-length analysis of low-density parity-check codes on the binary erasure channel

Changyan Di, D. Proietti, I. Emre Telatar +2 more

In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.

IEEE Transactions on Information Theory•Jun 1, 2002•849 citations

Bounds on the maximum likelihood decoding error probability of low density parity check codes

G. Miller, D. Burshtein

We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.

IEEE International Symposium on Information Theory (ISIT)•Nov 7, 2002•6 citations
For a given channel instance and a fixed LDPC ensemble, a stability outage event is defined by the density evolution being unstable at the origin. The probability of such an event, referred to as Stability Outage Probability, is a useful lower bound for the word error rate. We formulate the stability outage probability for block fading channels and we introduce the stability diversity order. As a direct application, we show how the class of capacity-achieving ensembles on the erasure channel is bounded away from the outage limit on a block fading channel.
This thesis addresses the topic of Low-Density Parity-Check (LDPC) code analysis, both asymptotically and for finite block lengths. Since in general it is a difficult problem to analyze individual code instances, ensemble averages are studied by following Gallager's original idea and results of Luby et al. Often, one can relate the insights gained by studying ensemble averages to statements regarding individual codes by proving that most elements in the ensemble behave "close" to the average. One important such average is the average weight distribution, another is the average pseudo-codeword distribution, where pseudo-codewords play the same role under iterative decoding as codewords do for maximum likelihood decoding. One of the main contributions of this thesis is the calculation of such averages for fully irregular LDPC code ensembles. Much of classical coding theory is aimed at the construction of codes with large minimum distance. This is so since away from capacity accurate bounds on the performance of a code can be given in terms of its minimum distance (or more generally, in terms of its weight distribution). Therefore, it is of interest to investigate what role the minimum distance plays for iteratively decoded LDPC code ensembles. In particular, sequences of capacity-achieving LDPC code ensembles of increasing length when transmission takes place over the Binary Erasure Channel (BEC) are investigated. It is shown that, under certain technical conditions, the minimum distance of such ensembles grows sub-linearly in the block length, a result which is somewhat surprising from a classical point of view. Specific attention is also given to the design of LDPC code ensembles, where an inherent trade-off is observed between achieving large minimum distance (which is relevant for the so called error-floor regime) and achieving a large threshold (which in the limit of long block lengths determines the worst channel on which transmission can be accomplished reliably). Most results on iterative coding systems to date address their asymptotic performance, i.e., their performance when the block length tends to infinity. For small and moderate block lengths the behavior of a code can deviate significantly from its asymptotic limit. It is therefore of high practical value to be able to analyze the finite-length performance of LDPC code ensembles. In this thesis, an exact such analysis is presented for iteratively decoded LDPC code ensembles over the BEC. In particular, expressions for the exact average bit and block erasure probabilities are computed by solving a set of recursions. Such an analysis is the starting point for a finite-length optimization, a topic which is slated for future work. The methods used in this thesis include a combinatorial approach (familiar to the coding society) as well as the powerful techniques developed in the statistical physics community, for example, the replica method or the mean-field approximation. Although the statistical physics techniques are ideally suited for the analysis of iterative coding systems, they are to date only accessible to a relatively small community. Therefore, an overview of these techniques is first presented using a language familiar to the coding theory community. Next, in order to highlight the differences and common points between the combinatorial and the statistical physics approaches, both techniques are applied to the weight distribution problem. It turns out that for regular ensembles, both methods yield the same result, while for irregular ensembles, they do differ in general.
The density evolution equations for non-binary low-density parity-check (LDPC) ensembles when transmission takes place over the binary erasure channel are derived. Ensembles defined with respect to the general linear group over the binary field are introduced. For these ensembles the density evolution equations can be written compactly. The density evolution for the general linear group helps in understanding the density evolution for codes defined with respect to finite fields. Thresholds are computed for different alphabet sizes for various LDPC ensembles. Surprisingly, the threshold is not a monotonic function of the alphabet size. The stability condition for non-binary LDPC ensembles over any binary memoryless symmetric channel is stated. Upper bounds on the MAP thresholds for various non-binary ensembles based on EXIT curves and the area theorem are given.
For a (lambda(x); rho(x)) standard irregular LDPC code ensemble, the growth rate of the average weight distribution for small relative weight omega is given by log(lambda'(0)rho'(1))omega + O(omega2) in the limit of code length n. If lambda'(0)rho'(1) < 1, there exist exponentially few code words of small linear weight, as n tends to infinity. It is known that the condition coincides with the stability condition of density evolution over the erasure channels with the erasure probability 1. In this paper, we show that this is also the case with multi-edge type LDPC (MET-LDPC) codes. MET-LDPC codes are generalized structured LDPC codes introduced by Richardson and Urbanke. The parameter corresponding lambda'(0)rho'(1) appearing in the conditions for MET-LDPC codes is given by the spectral radius of the matrix defined by extended degree distributions.
In this paper, we are concerned with the finite-length analysis of low-density parity-check (LDPC) codes when used over the binary erasure channel (BEC). The main result is an expression for the exact average bit and block erasure probability for a given regular ensemble of LDPC codes when decoded iteratively. We also give expressions for upper bounds on the average bit and block erasure probability for regular LDPC ensembles and the standard random ensemble under maximum-likelihood (ML) decoding. Finally, we present what we consider to be the most important open problems in this area.
We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.