corresponds to a single input symbol. This channel represents another case of the noisy typewriter (Example 3), but with Namely, outputs Z, A, B uniquely correspond to A as input, outputs C, D, E uniquely correspond to D as input, etc. Such outputs are referred to as "nonconfusable" subsets. Channel capacity and coding theorem nonoverlapping outputs. Furthermore, we can write p(y1 or p(y1|x1)p(x1) + p(y1|x2)p(x2) + p(y2|x1)p(x2) + p(y2/x2)p(x2) (13.20) Define the new output symbols Z1 = y1 or y2, Z2 = y2 or . It is easily established that the conditional probabilities satisfy p(z1/x1) = p(z2/x2) = 1/2. The corresponding transition matrix is, thus, the identity matrix. This noisy channel is, therefore, equivalent to a noiseless channel, for which C = 1 with the uniform distribution as the optimal input distribution. This conclusion can also be reached by going through the same formal calculations and capacity optimization as in Example 3. With the above examples, the maximization problem of obtaining the channel capacity and the corresponding optimal input probability distribution is seen to be relatively simple. But one should not hastily conclude that this applies to the general case! Rather, the solution of this problem, should such a solution exist and be unique, is generally complex and nontrivial. It must be found through numerical methods using nonlinear optimization algorithms. 6 Typical sequences and the typical set In this section, I introduce the two concepts of typical sequences and the typical set. This concept is central to the demonstration of Shannon's second theorem, known as the channel coding theorem, which is described in the next section. Typical sequences can be defined according to the following. Assume an originator message source Xn generating binary sequences of length k.7 Any of the 2k possible sequences generated by Xn is of the form X = X1X2X3, Xk, where Xi = 0 or 1 are the message bits. We assume that the bit events Xi are independent. The entropy of such a source is H(X) = kH(X). 8 A