f of the channel coding theorem This appendix provides the converse proof of the CCT.¹ The converse proof must show that to achieve transmission with arbitrary level accuracy (or error probability), the condition R < C must be fulfilled. The demonstration seeks to establish two properties, which I shall name A and B. Property A To begin with, we must establish the following property, referred to as Fano's inequality, according to which: H(X"|Y")1+penR, where Pe is the error probability of the code (pe = 1 - p), i.e., the probability that the code will output a codeword that is different from the input message codeword. To demonstrate Fano's inequality, we define W = 1...2nR as the integer that labels the 2nR possible codewords in the input-message codebook. We can view the code as generating an output integer label W', to which the label W of the input message codeword may or may not correspond. We can, thus, write Pe = p(W # W). We then define a binary random variable E, which tells whether or not a codeword error occurred: E = 1, if W' # W, and E = 0, if W' = W. Thus, we have p(E = 1) = Pe and p(E = 0) = 1 - Pe. We can then introduce the conditional entropy H(E, W|Y"), which is the average information we have on E, W, given the knowledge of the output codeword source, Yn. Referring back to the chain rule in Eqs. (5.22) and (5.23), we can expand H(E, W|Y") in two different ways: H(E, W|Yn) = H(E|Y") + H(W|E, Yn) = H(W|Y")+H(EW Yn). Since E is given by the combined knowledge of label W and output source Yn, we have H(E\W, Yn) = 0. We also have H(E|Y") = H(E), since the only knowledge of Yn does not condition the knowledge of E. Substituting these results into Eq. (L2), we 1 Inspired from M. Cover and J.A. Thomas, Elements of Information Theory (New York: John Wiley & Sons, 1991), pp. 203-9. Appendix L obtain H(WY")=H(E)+H(WE,Y"). We shall now find an upper bound for H(W|Y"). First, we can decompose the second term in the right-hand side in Eq. (L3) as follows: H(WE,Y = p(E = 0)H(W|Y", E 0) + p(E = 1)H(WYY, = pe)H