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 Transactions on Information Theory

Lower Bounds on the Error Rate of LDPC Code Ensembles

Ohad Barak, David Burshtein

Published Nov 1, 2007• 14 citations
Publisher

Abstract

The ensemble of regular low-definition parity-check (LDPC) codes is considered. Using concentration results on the weight distribution, lower bounds on the error rate of a random code in the ensemble are derived. These bounds hold with some confidence level. Combining these results with known lower bounds on the error exponent, confidence intervals on the error exponent, under maximum-likelihood (ML) decoding, are obtained. Over a large range of channel parameter and transmission rate values, when the graph connectivity is sufficiently large, the upper bound of the interval approaches the lower bound, and the probability that the error exponent is within the interval can be arbitrarily close to one. In fact, in this case the true error exponent approaches the maximum between the random coding and the expurgated random coding exponents, with probability that approaches one.

DOI
10.1109/tit.2007.907448

Related papers

Upper Bounds on the Error Exponents of LDPC Code Ensembles

David Burshtein, Ohad Barak

We consider the ensemble of regular LDPC codes and use recent concentration results on the distance spectrum to derive upper bounds on the error exponent of a randomly chosen code from the ensemble. These bounds hold with some confidence level that approaches one as the connectivity of the graph increases. We show that the bounds can be used to obtain the true error exponent over some range of channel parameter values, with the above confidence level

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•5 citations

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

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information Theory•Jan 1, 2001•157 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•7 citations

Lower bounds on the spectrum and error rate LDPC code ensembles

Ohad Barak, David Burshtein

We consider the ensemble of regular LDPC codes and obtain an expression for the second moment of the distance spectrum. We show how this expression can be used to derive a lower bound on the probability that the growth rate of a randomly chosen code from the ensemble is equal to the growth rate of the average distance spectrum, when the block length is sufficiently large. In particular, when the connectivity of the code is sufficiently large, the distance spectrum of a code in the ensemble is concentrated. We then derive a lower bound on the probability (confidence level) that the minimum distance and error rate, respectively, of a randomly chosen code from the ensemble are upper and lower bounded by some values (which depend on the confidence level)

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•8 citations

Upper Bound on Error Exponent of Regular LDPC Codes Transmitted Over the BEC

Idan Goldenberg, David Burshtein

The error performance of the ensemble of typical low-definition parity-check (LDPC ) codes transmitted over the binary erasure channel (BEC) is analyzed. In the past, lower bounds on the error exponents were derived. In this paper, a probabilistic upper bound on this error exponent is derived. This bound holds with some confidence level.

IEEE Transactions on Information Theory•May 19, 2009•4 citations

Performance of Standard Irregular LDPC Codes under Maximum Likelihood Decoding

Ryoji Ikegaya, K. KASAI, T. SHIBUYA +1 more

In this paper, we derive an upper bound for the average block error probability of a standard irregular low-density parity-check (LDPC) code ensemble under the maximum-likelihood (ML) decoding. Moreover, we show that the upper bound asymptotically decreases polynomially with the code length. Furthermore, when we consider several regular LDPC code ensembles as special cases of standard irregular ones over an additive white Gaussian noise channel, we numerically show that the signal-to-noise ratio (SNR) thresholds at which the proposed bound converges to zero as the code length tends to infinity are smaller than those for a bound provided by Miller et al. We also give an example of a standard irregular LDPC code ensemble which has a lower SNR threshold than a given regular LDPC code ensemble.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jul 1, 2007•4 citations
The ensemble of regular low-definition parity-check (LDPC) codes is considered. Using concentration results on the weight distribution, lower bounds on the error rate of a random code in the ensemble are derived. These bounds hold with some confidence level. Combining these results with known lower bounds on the error exponent, confidence intervals on the error exponent, under maximum-likelihood (ML) decoding, are obtained. Over a large range of channel parameter and transmission rate values, when the graph connectivity is sufficiently large, the upper bound of the interval approaches the lower bound, and the probability that the error exponent is within the interval can be arbitrarily close to one. In fact, in this case the true error exponent approaches the maximum between the random coding and the expurgated random coding exponents, with probability that approaches one.
We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.
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.
We consider the ensemble of regular LDPC codes and obtain an expression for the second moment of the distance spectrum. We show how this expression can be used to derive a lower bound on the probability that the growth rate of a randomly chosen code from the ensemble is equal to the growth rate of the average distance spectrum, when the block length is sufficiently large. In particular, when the connectivity of the code is sufficiently large, the distance spectrum of a code in the ensemble is concentrated. We then derive a lower bound on the probability (confidence level) that the minimum distance and error rate, respectively, of a randomly chosen code from the ensemble are upper and lower bounded by some values (which depend on the confidence level)
In this paper, we derive an upper bound for the average block error probability of a standard irregular low-density parity-check (LDPC) code ensemble under the maximum-likelihood (ML) decoding. Moreover, we show that the upper bound asymptotically decreases polynomially with the code length. Furthermore, when we consider several regular LDPC code ensembles as special cases of standard irregular ones over an additive white Gaussian noise channel, we numerically show that the signal-to-noise ratio (SNR) thresholds at which the proposed bound converges to zero as the code length tends to infinity are smaller than those for a bound provided by Miller et al. We also give an example of a standard irregular LDPC code ensemble which has a lower SNR threshold than a given regular LDPC code ensemble.