A Simple Derivation of the Coding and Some Applications ROBERT G. GALLAGER, MEMBER, IEEE Theorem Abstracl-Upper bounds are derived on the probability of error that can be achieved by using block codes on general time-discrete memoryless channels. Both amplitude-discrete and amplitude- continuous channels are treated, both with and without input constraints. The major advantages of the present approach are the simplicity of the derivations and the relative simplicity of the results; on the other hand, the exponential behavior of the bounds with block length is the best known for all transmission rates between 0 and capacity. The results are applied to a number of special channels, including the binary symmetric channel and the additive Gaussian noise channel. I. INTR~DTJOTI~N T HE CODING THEOREM, discovered by Shannon [l] in 1948, states that for a broad class of com- - munication channel models there is a maximum rate, capacity, at which information can be transmitted over the channel, and that for rates below capacity, informa- tion can be transmitted with arbitrarily low probability of error. For discrete memoryless channels, the strongest known form of the theorem was stated by Fano [2] in 1961. In this result, the minimum probability of error P, for codes of block length N is bounded for any rate below capacity’ between the limits e -.\‘LEL(R)+O(.&-)I 5 p, 5 2e-.\‘E(R, (1) In this expression, E,(R) and E(R) are positive functions of the channel transition probabilities and of the rate R; O(N) is a function going to 0 with increasing N. For a range of rates immediately beneath channel capacity, EL(R) = E(R). The function E(R), especially in the range in which E(R) = E,(R), appears to yield a fundamental charac- terization of a channel for coding purposes. It brings out clearly and simply the relationships between error prob- ability, data rate, constraint length, and channel be- havior. Recent advances in coding theory have yielded a number of effective and economically feasible coding techniques, and (1) provides a theoretical framework within which to discuss intelligently the relative merits Manuscript received March 11, 1964. This work was supported in part by the U. S. Army, Navy, and Air Force under Contract DA36-039-AMC-03200(E); and in part by the National Science Foundation (Grant GP-2495), the National Institutes of Health (Grant MH-04737-04), and the National Aeronautics and Space Administration (Grants NsG-334 and NsG-496). The author is with the Dept. of Electrical Engineering and the Research Lab. of Electronics, Massachusetts Institute of Tech- nology, Cambridge, Mass. 1 This paper deals only with error probabilities at rates below capacity. For the strongest known results at, rates above capacit,y, see Gallager [3], Section 6. of these techniques. Even more important, the function E(R) provides a more meaningful comparison between different channels than can be made on the basis of capacity or SIVR. For example, if one is to use coding on a physical communication link, one of the first questions to be answered involves the type of digital modulation systems to use. Considering the modulation system as part of the channel, one can compare modulation sys- tems for coding applications on the basis of their E(R) curves. For an example of such a comparison, see Wozencraft and Kennedy [4]. In Section II of this paper, a simple proof is given that P, < edNEcR). In Section III, we establish a number of properties of E(R) and show explicitly how the func- tion E(R) can be calculated. This calculation is just slightly more complicated than the calculation of channel capacity. In Section IV, we give a number of applica- tions of the theory developed in Sections II and III. First, as an example, we derive E(R) for a binary sym- metric channel; then we derive a universal E(R) curve for very noisy channels; and finally, we relate E(R) for a set of parallel channels to the E(R) curves of the indi- vidual channels. In Section B, we derive an improved upper bound to P, for low rates; this yields a larger value of E(R) than was derived in Section II. There is some reason to suspect that the combination of these two bounds produces the true exponential behavior with block length of the best codes. In Section VI, these results are extended to chan- nels with constraints on the input and to channels with continuous input and output alphabets. Finally, the re- sults are applied to the additive Gaussian noise channel as an example. II. DERIVATION OFTHE CODING THEOREM Let XN be the set of all sequences of length N that can be transmitted on a given channel, and let Y, be the set of all sequences of length N that can be received. We assume that both Xjv and Y, are finite sets. Let Pr (y / x), for y E YN and x e X,, be the conditional probability of receiving sequence y, given that x was transmitted. We assume that we have a code consisting of ii/r code words; that is, a mapping of the integers from 1 to M into a set of code words x1, . . . , xlc,,where x, E X,; 1 5 m 5 M. We assume that maximum likelihood de- coding is performed at the receiver; that is, the decoder decodes the output sequence y into the integer m if Pr(y Ixm) > Pr(ym Ix) for all m’ z m, 1 < m’ 2 M (2) 34 IEEE TRANSACTIONS ON INFORMATION THEORY January For purposes of overbounding the probability of decoding error, we regard any situation in which no m satisfies (2) as a decoding error. Also, of course, a decoding error is made if the decoded integer is different from the input integer. Now let P,, be the probability of decoding error when x, is transmitted. A decoding error will be made if a y is received such