Distance distribution of binary codes and the error probability of decoding

Abstract

We address the problem of bounding below the probability of error under maximum likelihood decoding of a binary code with a known distance distribution used on a binary symmetric channel. An improved upper bound is given for the maximum attainable exponent of this probability (the reliability function of the channel). In particular, we prove that the ``random coding exponent'' is the true value of the channel reliability for code rate $R$ in some interval immediately below the critical rate of the channel. An analogous result is obtained for the Gaussian channel.

16 pages, 3 figures. Submitted to IEEE Transactions on Information Theory. The revision was done for a final journal version (it may still be different from the published version)