New Upper Bounds on Error Exponents

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 straight-line bound by Shannon-Gallager-Berlekamp (1967) and the McEliece-Omura (1977) minimum distance bound. For the probability of undetected error the new bounds are better than the recent bound by Abdel-Ghaffar (1997) and the minimum distance and straight-line bounds by Levenshtein (1978, 1989). We further extend the range of rates where the undetected error exponent is known to be exact. Keywords: Error exponents, Undetected error, Maximum likelihood decoding, Distance distribution, Krawtchouk polynomials. Submitted to IEEE Transactions on Information Theory 1 Introduction A classical problem of the information theory is to estimate probabilities of undetected and decoding errors when a block code is used for information transmission over a binary symmetric channel (BSC). We will study here exponential bounds ..