hannel at an information (or code) rate R < C per unit time, i.e., R payload bits are generated per second, but the rate is strictly less than C bits per second. Thus nR payload bits are generated in the duration of each message sequence of length n bits. To encode the payload information into message sequences, the originator chooses to use only the sequences belonging to the typical set of X. Therefore, 2nR coded message sequences (or codewords) are randomly chosen from the set of 2nH(X) typical sequences, and with a uniform probability. Accordingly, the probability that a given typical sequence Xi will be selected for transmitting the coded message is: p(xi) (13.28) C.E. Shannon, A mathematical theory of communication. Bell Syst. Tech. J., 27 (1948), 379-423,623-56, http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf 13.3 Shannon's channel coding theorem Source X Source Y 2nH(X|Y) 2nH(X) most likely 2nH(Y) typical origins for each yj typical inputs outputs most likely outcomes for each X Figure 13.5 Noisy communication channel relating input source X (sequences x) and output source Y (sequences y), showing the numbers of most likely inputs X (typical set of X), of most likely outputs y (typical set of Y), of most likely origins for given output Yj, and of most likely outcomes for given input Xi. Assume next that a particular output sequence yj is received. What is the no-error probability, p, that yj exclusively corresponds to the message xi? As we have seen, for any given output message yj there exist a = 2nH(X|Y) most likely origins Xi. On the other hand, the probability that the originator message is not Xi is p= 1 - p(xi). Thus, we obtain from Eq. (13.28) the no-error probability: 1-p1-2 = (13.29) Since we assumed R < C = H(X) - H(X)Y), we have R - H(X) < - -((((Y) or R - H(X) = - -((((()(Y) - E where E is a positive nonzero number (E > 0). Replacing this relation into Eq. (13.29) yields (13.30) We now take the limit of the probability p for large sequence lengths N. We substitute U = 2nH(Y|X) an