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 Convention of Electrical and Electronics Engineers in Israel

New lower bounds on the error probability of a given block code

A. Cohen, Neri Merhav

Published Jun 26, 2003• 2 citations
Publisher

Abstract

A novel technique for deriving lower bounds on the error probability when communicating one of M signals over a communication channel is proposed. At the basis of the technique stands an improvement on a recent lower bound on the probability of a union of events by de Caen (1997). The new bound includes a function which can be optimized in order to achieve the tightest results. By applying this bound to the problem of lower bounding the error probability, while suggesting an appropriate optimization function, in the spirit of the relevant channel model and type of the code, new bounds on the error probability can be derived. In this paper we apply the new bound to the problem of lower bounding the error probability of binary linear codes over the binary symmetric channel (BSC). The resulting bound improves on the latest bound appearing in the current literature, by Keren and Litsyn (2000).

DOI
10.1109/eeei.2002.1178366

Related papers

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

Analysis of Lower Bound for the Error Probability of Linear Block Codes over the BSC Channel

Xu Ba

A lower bound on the error rate of linear binary block codes(under maximum likelihood decoding) over BSC channels is proposed.According to the principle of the maximum likelihood(ML) decoding algorithm,the decoding error probability is firstly converted into the joint probability of the error events,and the judge rule of the redundant error events is deduced based on the optimization rule of the improved Dawson-Sankoff bound.Moreover,the calculation expression about lower bound of the error probability solely depends on the Hamming weight enumerator function of the code and the crossover probability of the channel.The simulation results applying to various LDPC codes show that the new lower bound outperforms those generic lower bounds and the sphere packing bound.Its computational complexity is also lower.

Journal of National University of Defense Technology•Jan 1, 2011•0 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

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

Analytical Bounds on Maximum-Likelihood Decoded Linear Codes with Applications to Turbo-Like Codes: An Overview

Igal Sason, Shlomo Shitz Shamai

Upper and lower bounds on the error probability of linear codes under maximum-likelihood (ML) decoding are shortly surveyed and applied to ensembles of codes on graphs. For upper bounds, focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, sphere-packing bounds, and information-theoretic bounds on the bit error probability of codes defined on graphs. A comprehensive overview is provided in a monograph by the authors which is currently in preparation.

arXiv:cs/0512074•Dec 18, 2005•1 citation

On the Probability of Undetected Error for Linear Block Codes

Jack K. Wolf, Arnold M. Michelson, Allen H. Levesque

The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.

IRE Transactions on Communications Systems•Feb 1, 1982•137 citations
A novel technique for deriving lower bounds on the error probability when communicating one of M signals over a communication channel is proposed. At the basis of the technique stands an improvement on a recent lower bound on the probability of a union of events by de Caen (1997). The new bound includes a function which can be optimized in order to achieve the tightest results. By applying this bound to the problem of lower bounding the error probability, while suggesting an appropriate optimization function, in the spirit of the relevant channel model and type of the code, new bounds on the error probability can be derived. In this paper we apply the new bound to the problem of lower bounding the error probability of binary linear codes over the binary symmetric channel (BSC). The resulting bound improves on the latest bound appearing in the current literature, by Keren and Litsyn (2000).
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.
A lower bound on the error rate of linear binary block codes(under maximum likelihood decoding) over BSC channels is proposed.According to the principle of the maximum likelihood(ML) decoding algorithm,the decoding error probability is firstly converted into the joint probability of the error events,and the judge rule of the redundant error events is deduced based on the optimization rule of the improved Dawson-Sankoff bound.Moreover,the calculation expression about lower bound of the error probability solely depends on the Hamming weight enumerator function of the code and the crossover probability of the channel.The simulation results applying to various LDPC codes show that the new lower bound outperforms those generic lower bounds and the sphere packing bound.Its computational complexity is also lower.
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.>
Upper and lower bounds on the error probability of linear codes under maximum-likelihood (ML) decoding are shortly surveyed and applied to ensembles of codes on graphs. For upper bounds, focus is put on Gallager bounding techniques and their relation to a variety of other reported bounds. Within the class of lower bounds, we address de Caen's based bounds and their improvements, sphere-packing bounds, and information-theoretic bounds on the bit error probability of codes defined on graphs. A comprehensive overview is provided in a monograph by the authors which is currently in preparation.
The problem of computing the probability of undetected error is considered for linear block codes used for error detection. The recent literature is first reviewed and several results are extended. It is pointed out that an exact calculation can be based on either the weight distribution of a code or its dual. Using the dual code formulation, the probability of undetected error for the ensemble of all nonbinary linear block codes is derived as well as a theorem that shows why the probability of undetected error may not be a monotonic function of channel error rate for some poor codes. Several bounds on the undetected error probability are then presented. We conclude with detailed examples of binary and nonbinary codes for which exact results can be obtained. An efficient technique for measuring an unknown weight distribution is suggested and exact results are compared with experimental results.