 sequence is received. There is a possibility of transmission error if at least one other input sequence Xk#i can result in the same output sequence y. The error probability Pe of the event x # Xi occurring satisfies: (13.36) < p(x1 Xi) p(x2 # Specifying the right-hand side, we obtain: (13.37) This result is justified as follows: (a) there exist 2nR - 1 sequences Xk#i in the codeword set that are different from Xi, and (b) the fraction of input sequences, which output in y is 2nH(X|Y) /2nH(X) It follows from Eq. (13.37) that p < 2"R2" (13.38) =2nR9n[H(X|Y)-H(X) = n(C-R) which shows that since R < C the probability of error can be made arbitrarily small with code sequences of suitably long lengths n, which is another statement of the The formal demonstration from the original Shannon paper, completed with the three above approaches, establishes the existence of codes yielding error-free transmission, with arbitrary accuracy, under the sufficient condition R < C. What about the proof of the converse? Such a proof would establish that error-free transmission codes make R < C a necessary condition. The converse proof can be derived in two ways. The first and easier way, which is not complete, consists of assuming an absolute "zero error" code, and showing that this assumption leads to the necessary condition R V C. Recall that the originator source has 2nR possible message codewords of n-bit length. With a zero-error code, any output bit yi of a received sequence must correspond exclusively to an input message codeword bit Xi. This means that the knowledge of yi is equivalent to that of Xi, leading to the conditional probability p(xilyi) = 1, and to the conditional channel entropy H(X|Y) = 0. As we have seen, the entropy of the n-bit message codeword source, Xn, is H(X") = nH(X). We can also assume that the message codewords are chosen at random, with a uniform probability distribution p = 2-nR which leads to H(X") = nR and, thus, H(X) = R. We now substitute the 13.3 Shannon's channel coding theorem above results int