Upper and Lower Bounds for the Probability of Error in Decoding for Discrete Channels

The lower bound for the probability of error for discrete channels with memory is determined. It is shown that the Gallager upper boundary and the lower boundary obtained in the paper are asymptotically exact for channels with Markov noise with transmission rates close to the channel capacity. For certain models of binary channels which are additive $\operatorname{mod}2$, upper bounds for the probability of error are determined.