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