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

New upper bounds on error exponents

Simon N. Litsyn

Published Mar 1, 1999• 65 citations
Publisher

Abstract

We derive new upper bounds on the error exponents for the maximum-likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the best earlier known bounds by Shannon-Gallager-Berlekamp (1967) and McEliece-Omura (1977). For the probability of undetected error the new bounds are better than the bounds by Levenshtein (1978, 1989) and the bound by Abdel-Ghaffar (see ibid., vol.43, p.1489-502, 1997). Moreover, we further extend the range of rates where the undetected error exponent is known to be exact. The new bounds are based on an analysis of possible distance distributions of the codes along with some inequalities relating the distance distributions to the error probabilities.

DOI
10.1109/18.748991

Related papers

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

Hideki Yagi, H. Vincent Poor

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.

IEEE Transactions on Information Theory•Mar 12, 2013•2 citations

Bounds on the decoding error probability of binary linear codes via their spectra

Gregory Poltyrev

Bounds on the error probability of maximum likelihood decoding of a binary linear code are considered. The bounds derived use the weight spectrum of the code and they are tighter than the conventional union bound in the case of large noise in the channel. The bounds derived are applied to a code with an average spectrum, and the result is compared to the random coding exponent. The author shows that the bound considered for the binary symmetrical channel case coincides asymptotically with the random coding bound. For the case of AWGN channel the author shows that Berlekamp's (1980) tangential bound can be improved, but even this improved bound does not coincide with the random coding bound, although it can be very close to it.>

IEEE Transactions on Information Theory•Jul 1, 1994•230 citations

On the asymptotic accuracy of the union bound

Alexander Barg

A new lower bound on the error probability of maximum likelihood decoding of a binary code on a binary symmetric channel was proved in Barg and McGregor (2004, cs.IT/0407011). It was observed in that paper that this bound leads to a new region of code rates in which the random coding exponent is asymptotically tight, giving a new region in which the reliability of the BSC is known exactly. The present paper explains the relation of these results to the union bound on the error probability.

arXiv:cs/0412111•Dec 24, 2004•3 citations

Lower Bounds on the Error Probability of Block Codes Based on Improvements on de Caen's Inequality

A. Cohen, Neri Merhav

New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.

IEEE Transactions on Information Theory•Feb 1, 2004•41 citations

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

Improvement of Gallager Upper Bound and its Variations for Discrete Channels

Kostis Xenoulis, N. Kalouptsidis

A new tight upper bound on the maximum-likelihood (ML) word and bit-error decoding probabilities for specific codes over discrete channels is presented. It constitutes an enhanced version of the Gallager upper bound and its variations resulting from the Duman-Salehi second bounding technique. An efficient technique is developed that, in the case of symmetric channels, overcomes the difficulties associated with the direct computation of the proposed bound. Surprisingly, apart from the distance and input-output weight enumerating functions (IOWEFs), the bound depends also on the coset weight distribution of the code.

IEEE Transactions on Information Theory•Aug 24, 2009•1 citation
We derive new upper bounds on the error exponents for the maximum-likelihood decoding and error detecting in the binary symmetric channels. This is an improvement on the best earlier known bounds by Shannon-Gallager-Berlekamp (1967) and McEliece-Omura (1977). For the probability of undetected error the new bounds are better than the bounds by Levenshtein (1978, 1989) and the bound by Abdel-Ghaffar (see ibid., vol.43, p.1489-502, 1997). Moreover, we further extend the range of rates where the undetected error exponent is known to be exact. The new bounds are based on an analysis of possible distance distributions of the codes along with some inequalities relating the distance distributions to the error probabilities.
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.
Bounds on the error probability of maximum likelihood decoding of a binary linear code are considered. The bounds derived use the weight spectrum of the code and they are tighter than the conventional union bound in the case of large noise in the channel. The bounds derived are applied to a code with an average spectrum, and the result is compared to the random coding exponent. The author shows that the bound considered for the binary symmetrical channel case coincides asymptotically with the random coding bound. For the case of AWGN channel the author shows that Berlekamp's (1980) tangential bound can be improved, but even this improved bound does not coincide with the random coding bound, although it can be very close to it.>
New lower bounds on the error probability of block codes with maximum-likelihood decoding are proposed. The bounds are obtained by applying a new lower bound on the probability of a union of events, derived by improving on de Caen's lower bound. The new bound includes an arbitrary function to be optimized in order to achieve the tightest results. Since the optimal choice of this function is known, but leads to a trivial and useless identity, we find several useful approximations for it, each resulting in a new lower bound. For the additive white Gaussian noise (AWGN) channel and the binary-symmetric channel (BSC), the optimal choice of the optimization function is stated and several approximations are proposed. When the bounds are further specialized to linear codes, the only knowledge on the code used is its weight enumeration. The results are shown to be tighter than the latest bounds in the current literature, such as those by Seguin (1998) and by Keren and Litsyn (2001). Moreover, for the BSC, the new bounds widen the range of rates for which the union bound analysis applies, thus improving on the bound to the error exponent compared with the de Caen-based bounds.
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.
A new tight upper bound on the maximum-likelihood (ML) word and bit-error decoding probabilities for specific codes over discrete channels is presented. It constitutes an enhanced version of the Gallager upper bound and its variations resulting from the Duman-Salehi second bounding technique. An efficient technique is developed that, in the case of symmetric channels, overcomes the difficulties associated with the direct computation of the proposed bound. Surprisingly, apart from the distance and input-output weight enumerating functions (IOWEFs), the bound depends also on the coset weight distribution of the code.