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

Bounds on Maximum Likelihood Decoding Performance for Linear Codes at Low Rates

Hideki Yagi, H. Vincent Poor

Published Mar 12, 2013• 2 citations
Publisher

Abstract

For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.

DOI
10.1109/tit.2013.2252394

Related papers

Performance analysis of linear codes under maximum likelihood decoding at low rates

Hideki Yagi, H. Vincent Poor

Or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. F In the analysis of the decoding error probability, it is important to characterize the error exponent, since it indicates how fast the probability of decoding error converges to zero asymptotically. Over a symmetric memoryless channel, an error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, is given. Over a general discrete memoryless channel, the same analysis shows the expected error exponent of an ensemble of coset codes generated by a given linear code.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•0 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

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

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

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

Bounds on the Error Probability of Nonbinary Linear Codes over the Q-ary Symmetric Channel

Emna Ben Yacoub, Gianluigi Liva, Enrico Paolini

The block error probability under maximum likelihood decoding of general linear block codes and code ensembles over the q-ary symmetric channel is analyzed. The analysis makes use of two types of upper bounds and it is based on the codes (code ensembles) distance spectra. The first bound generalizes Poltyrev's union bound for the binary symmetric channel. The second bound relies on typical pairs decoding. The two bounds are developed in an asymptotic setting to analyze the behavior of linear block code ensembles, in terms of error exponent and maximum-likelihood decoding threshold. A sphere-packing lower bound is also developed, to provide a reference for the finite-length performance.

Conference on Information Sciences and Systems•Mar 24, 2021•0 citations
For a given linear code (ensemble), upper bounds on the error probability under maximum likelihood decoding are investigated at low rates. A class of symmetric memoryless channels suitable for Bhattacharyya-type bounds, which are particularly of importance at low rates, is introduced. Over a symmetric channel, a lower bound on the error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, within a fixed discrepancy is given. Over a general discrete memoryless channel, the same analysis provides a lower bound on the average error exponent for an ensemble of coset codes generated by a given linear code. The bounding technique is extended to the case of generalized maximum likelihood decoding with erasure and list- decoding options.
Or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. or a given linear code, a lower bound on the error exponent under maximum likelihood decoding is investigated at low rates. F In the analysis of the decoding error probability, it is important to characterize the error exponent, since it indicates how fast the probability of decoding error converges to zero asymptotically. Over a symmetric memoryless channel, an error exponent is derived for a given linear code. A sufficient condition for achieving the expurgated exponent, which is the best among known error exponents at low rates, is given. Over a general discrete memoryless channel, the same analysis shows the expected error exponent of an ensemble of coset codes generated by a given linear code.
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.
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 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.
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.
The block error probability under maximum likelihood decoding of general linear block codes and code ensembles over the q-ary symmetric channel is analyzed. The analysis makes use of two types of upper bounds and it is based on the codes (code ensembles) distance spectra. The first bound generalizes Poltyrev's union bound for the binary symmetric channel. The second bound relies on typical pairs decoding. The two bounds are developed in an asymptotic setting to analyze the behavior of linear block code ensembles, in terms of error exponent and maximum-likelihood decoding threshold. A sphere-packing lower bound is also developed, to provide a reference for the finite-length performance.