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

arXiv:cs/0607004 · IEEE Transactions on Information Theory

On the Error Exponents of Improved Tangential Sphere Bounds

Moshe Twitto, Igal Sason

Published Mar 1, 2007• 13 citations
arXivHTMLPDF

Abstract

The performance of maximum-likelihood (ML) decoded binary linear block codes over the additive white Gaussian noise (AWGN) channel is addressed via the tangential sphere bound (TSB) and two of its recent improved versions. The correspondence is focused on the derivation of the error exponents of these bounds. Although it was shown that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this correspondence that their error exponents coincide. For an arbitrary ensemble of binary linear block codes, the common value of these error exponents is explicitly expressed in terms of the asymptotic growth rate of the average distance spectrum

DOI
10.1109/tit.2006.890725

Related papers

On the Error Exponents of Improved Tangential-Sphere Bounds

Moshe Twitto, Igal Sason

The performance of maximum-likelihood (ML) decoded binary linear block codes over the AWGN channel is addressed via the tangential-sphere bound (TSB) and two of its recent improved versions. Although it was exemplified that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this paper that their error exponents coincide. For an arbitrary ensemble of binary linear block codes, the common value of these error exponents is explicitly expressed in terms of the asymptotic growth rate of the average distance spectrum.

IEEE Convention of Electrical and Electronics Engineers in Israel•Nov 1, 2006•0 citations

A New Upper Bound on the ML DecodingError Probability of Linear Binary Block Codes in AWGN Interference

Shahram Yousefi, Amir Keyvan Khandani

Performance evaluation of maximum-likelihood (ML) soft-decision-decoded binary block codes is usually carried out using bounding techniques. Many tight upper bounds on the error probability of binary codes are based on the so-called Gallager's first bounding technique (GFBT). The tangential sphere bound (TSB) of Poltyrev which has been believed for many years to offer the tightest bound developed for binary block codes is an example. Within the framework of the TSB and GFBT, we apply a new method referred to as the "added-hyper-plane" (AHP) technique, to the decomposition of the error probability. This results in a bound developed upon the application of two stages of the GFBT with two different Gallager regions culminating in a tightened upper bound beyond the TSB. The proposed bound is simple and only requires the spectrum of the binary code.

IEEE Transactions on Information Theory•Nov 30, 2004•44 citations

Tangential Sphere Bounds on the Ensemble Performance of ML Decoded Gallager Codes via Their Exact Ensemble Distance Spectrum

Sheng Tong

An efficient numerical approach to the exact ensemble distance spectrum of Gallager codes has been developed by evaluating powers of polynomials. With the exact ensemble distance spectrum of Gallager codes, tangential sphere upper bounds on their maximum likelihood (ML) decoding performance over binary input AWGN channels are investigated. Numerical results indicate improved bounds have been obtained, better than Sason and Shamai's results (which are based on Gallager's upper bound on the ensemble distance spectrum), especially in the error floor region. Furthermore, some critical properties of Gallager codes, including typical minimum distance and the performance tradeoff in the waterfall and error floor regions, have been considered.

International Conference on Communications•Jan 1, 2008•8 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•231 citations

On Approximation, Bounding & Exact Calculation of Block Error Probability for Random Codes

Ralf R. Müller

This paper presents a method to calculate the exact block error probability of random codes under maximum-likelihood decoding. The proposed method is applicable to a variety of channels. Particular focus is on both spherical and Gaussian random codes in additive white Gaussian noise as well as binary random codes on the binary symmetric channel. While for spherical random codes Shannon, in 1959, argued with solid angles in $N$-dimensional space, we project the problem into two dimensions and apply standard trigonometry. This simplifies the derivation and also allows for the analysis of Gaussian random codes which turn out to perform better for short blocklengths and high rates. For spherical random codes, we show how to efficiently evaluate the error probability with high precision. The difference to Shannon's sphere packing bound turns out to be small, as the Voronoi regions harden doubly-exponential in the blocklength. We show that, whenever the code contains more than three codewords, the sphere packing bound can be tightened by a new bound, that requires exactly the same effort to compute. Furthermore, we propose a very tight approximation to simplify computation of both exact error probability and the two bounds. For the binary symmetric channel, we derive an upper and a lower bound on the block error probability. The two only differ from the exact error probability, as for discrete alphabets there is a small, but nonzero probability to guess for the correct codeword, if several codewords have equal distance to the received word.

arXiv:2003.06807•Mar 15, 2020•2 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•40 citations
The performance of maximum-likelihood (ML) decoded binary linear block codes over the additive white Gaussian noise (AWGN) channel is addressed via the tangential sphere bound (TSB) and two of its recent improved versions. The correspondence is focused on the derivation of the error exponents of these bounds. Although it was shown that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this correspondence that their error exponents coincide. For an arbitrary ensemble of binary linear block codes, the common value of these error exponents is explicitly expressed in terms of the asymptotic growth rate of the average distance spectrum
The performance of maximum-likelihood (ML) decoded binary linear block codes over the AWGN channel is addressed via the tangential-sphere bound (TSB) and two of its recent improved versions. Although it was exemplified that some recent improvements of the TSB tighten this bound for finite-length codes, it is demonstrated in this paper that their error exponents coincide. For an arbitrary ensemble of binary linear block codes, the common value of these error exponents is explicitly expressed in terms of the asymptotic growth rate of the average distance spectrum.
Performance evaluation of maximum-likelihood (ML) soft-decision-decoded binary block codes is usually carried out using bounding techniques. Many tight upper bounds on the error probability of binary codes are based on the so-called Gallager's first bounding technique (GFBT). The tangential sphere bound (TSB) of Poltyrev which has been believed for many years to offer the tightest bound developed for binary block codes is an example. Within the framework of the TSB and GFBT, we apply a new method referred to as the "added-hyper-plane" (AHP) technique, to the decomposition of the error probability. This results in a bound developed upon the application of two stages of the GFBT with two different Gallager regions culminating in a tightened upper bound beyond the TSB. The proposed bound is simple and only requires the spectrum of the binary code.
An efficient numerical approach to the exact ensemble distance spectrum of Gallager codes has been developed by evaluating powers of polynomials. With the exact ensemble distance spectrum of Gallager codes, tangential sphere upper bounds on their maximum likelihood (ML) decoding performance over binary input AWGN channels are investigated. Numerical results indicate improved bounds have been obtained, better than Sason and Shamai's results (which are based on Gallager's upper bound on the ensemble distance spectrum), especially in the error floor region. Furthermore, some critical properties of Gallager codes, including typical minimum distance and the performance tradeoff in the waterfall and error floor regions, have been considered.
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.>
This paper presents a method to calculate the exact block error probability of random codes under maximum-likelihood decoding. The proposed method is applicable to a variety of channels. Particular focus is on both spherical and Gaussian random codes in additive white Gaussian noise as well as binary random codes on the binary symmetric channel. While for spherical random codes Shannon, in 1959, argued with solid angles in NNN-dimensional space, we project the problem into two dimensions and apply standard trigonometry. This simplifies the derivation and also allows for the analysis of Gaussian random codes which turn out to perform better for short blocklengths and high rates. For spherical random codes, we show how to efficiently evaluate the error probability with high precision. The difference to Shannon's sphere packing bound turns out to be small, as the Voronoi regions harden doubly-exponential in the blocklength. We show that, whenever the code contains more than three codewords, the sphere packing bound can be tightened by a new bound, that requires exactly the same effort to compute. Furthermore, we propose a very tight approximation to simplify computation of both exact error probability and the two bounds. For the binary symmetric channel, we derive an upper and a lower bound on the block error probability. The two only differ from the exact error probability, as for discrete alphabets there is a small, but nonzero probability to guess for the correct codeword, if several codewords have equal distance to the received word.
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.