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 International Symposium on Information Theory (ISIT)

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

G. Miller, D. Burshtein

Published Nov 7, 2002• 7 citations
Publisher

Abstract

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.

DOI
10.1109/isit.2000.866588

Related papers

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

Error Exponents of LDPC Codes under Low-Complexity Decoding

Pavel S. Rybin, Kirill Andreev, Victor Zyablov

This paper deals with the specific construction of binary low-density parity-check (LDPC) codes. We derive lower bounds on the error exponents for these codes transmitted over the memoryless binary symmetric channel (BSC) for both the well-known maximum-likelihood (ML) and proposed low-complexity decoding algorithms. We prove the existence of such LDPC codes that the probability of erroneous decoding decreases exponentially with the growth of the code length while keeping coding rates below the corresponding channel capacity. We also show that an obtained error exponent lower bound under ML decoding almost coincide with the error exponents of good linear codes.

Entropy•Feb 22, 2021•5 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

Lower Bounds on the Error Rate of LDPC Code Ensembles

Ohad Barak, David Burshtein

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.

IEEE Transactions on Information Theory•Nov 1, 2007•14 citations

On the Error Exponents of Capacity Approaching Construction of LDPC code

Pavel S. Rybin, Alexey Frolov

In this paper we consider low-density parity-check (LDPC) codes with special construction. We obtain the lower-bounds on the error exponents for these codes under proposed low-complexity decoding algorithm and under a well known maximum likelihood decoding algorithm. We show that such LDPC code with special construction exists, that the error probability of the low-complexity decoding algorithm exponentially decreases with the code length for all code rates below the channel capacity. We also show that obtained lower-bound on the error exponent under the maximum likelihood decoding almost reaches the lower-bound on the error exponent of good linear codes under the maximum likelihood decoding. The error exponents are computed numerically for different code parameters.

International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)•Nov 1, 2018•1 citation

LDPC Codes Over the BEC: Bounds and Decoding Algorithms

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +2 more

The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.

IEEE Transactions on Communications•Nov 6, 2018•5 citations
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 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.
This paper deals with the specific construction of binary low-density parity-check (LDPC) codes. We derive lower bounds on the error exponents for these codes transmitted over the memoryless binary symmetric channel (BSC) for both the well-known maximum-likelihood (ML) and proposed low-complexity decoding algorithms. We prove the existence of such LDPC codes that the probability of erroneous decoding decreases exponentially with the growth of the code length while keeping coding rates below the corresponding channel capacity. We also show that an obtained error exponent lower bound under ML decoding almost coincide with the error exponents of good linear codes.
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.
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.
In this paper we consider low-density parity-check (LDPC) codes with special construction. We obtain the lower-bounds on the error exponents for these codes under proposed low-complexity decoding algorithm and under a well known maximum likelihood decoding algorithm. We show that such LDPC code with special construction exists, that the error probability of the low-complexity decoding algorithm exponentially decreases with the code length for all code rates below the channel capacity. We also show that obtained lower-bound on the error exponent under the maximum likelihood decoding almost reaches the lower-bound on the error exponent of good linear codes under the maximum likelihood decoding. The error exponents are computed numerically for different code parameters.
The performance of maximum-likelihood (ML) decoding on the binary erasure channel for finite-length low-density parity-check (LDPC) codes from two random ensembles is studied. A tightened union-type upper bound on the ML decoding error probability based on the precise coefficients of the average weight spectrum is presented. For LDPC codes from the Gallager ensemble and the Richardson-Urbanke ensemble, new upper bounds on the ML decoding performance based on computing the rank of submatrices of the code parity-check matrix are derived. A new lower bound on the ML decoding threshold followed from the latter error probability bound is obtained. An improved lower bound on the error probability for codes with a known estimate on the minimum distance is presented as well. A new low-complexity near-ML decoding algorithm for quasi-cyclic LDPC codes is proposed and simulated. Its performance is compared to the simulated belief propagation and ML decoding performance and simulated performance of the best known improved iterative decoding techniques, as well as, with the derived upper bounds on the ML decoding performance and with decoding thresholds obtained by the density evolution technique.