  This paper presents an achievability bound that evaluates the exact
probability of error of an ensemble of random codes that are decoded by a
minimum distance decoder. Compared to the state-of-the-art which demands
exponential computation time, this bound is evaluated in polynomial time. This
improvement in complexity is also attainable for the original random coding
bound that utilizes an information density decoder. The general bound is
particularized for the binary symmetric channel, the binary erasure channel,
and the Gaussian channel.
