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:2003.06807

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

Ralf R. Müller

Published Mar 15, 2020• 2 citations
arXivHTMLPDF

Abstract

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.

Related papers

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 average block error probability of some random code ensembles under maximum-likelihood decoding. Deviating from Shannon's 1959 solid angle argument, we project the problem into two dimensions and apply standard trigonometry. This enables us to also analyze Gaussian random codes in additive white Gaussian noise and binary random codes for the binary symmetric channel. We find that the Voronoi regions harden doubly-exponential in the blocklength and utilize that to propose the new median bound that outperforms Shannon's 1959 sphere packing bound for the uniform spherical ensemble, whenever the code contains more than three codewords. Furthermore, we propose a very tight approximation to simplify computation of both exact error probability and the two bounds.

Globecom•Dec 1, 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

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

New upper bounds on error exponents

Simon N. Litsyn

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.

IEEE Transactions on Information Theory•Mar 1, 1999•61 citations

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 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

arXiv:cs/0607004•IEEE Transactions on Information Theory•Mar 1, 2007•13 citations

An Algorithm for Calculating the Exact Bit Error Probability of a Binary Linear Code Over the Binary Symmetric Channel

Tadashi Wadayama

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.

IEEE Transactions on Information Theory•Feb 1, 2004•4 citations
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.
This paper presents a method to calculate the exact average block error probability of some random code ensembles under maximum-likelihood decoding. Deviating from Shannon's 1959 solid angle argument, we project the problem into two dimensions and apply standard trigonometry. This enables us to also analyze Gaussian random codes in additive white Gaussian noise and binary random codes for the binary symmetric channel. We find that the Voronoi regions harden doubly-exponential in the blocklength and utilize that to propose the new median bound that outperforms Shannon's 1959 sphere packing bound for the uniform spherical ensemble, whenever the code contains more than three codewords. Furthermore, we propose a very tight approximation to simplify computation of both exact error probability and the two bounds.
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.
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.
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.
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
An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.