igures that the optimal input probability distribution is typically nonuniform.2 The 3D curve shows that the optimal 2 Yet for each value of the parameter b, there exist two uniform distribution solutions, except at the point a = b = 0.5, where the solution is unique (q = 1/2). Channel capacity and coding theorem Distribution q=p(x))=1-p(x) Figure 13.2 3D representation of the data shown in Fig. 3.1.. distribution has a saddle point at a =b==///2, which, as we have seen earlier, is one case of a useless channel (a + b = 1). Figure 13.3 shows the corresponding 3D surface plot of the channel capacity C, as defined in Eqs. (13.7) and (13.8). It can be observed from the figure that the channel- capacity surface is symmetrically folded about the a+b = 1 axis, along which C = 0 (useless channel). The two maxima C = 1 located in the back and front of the figure correspond to the cases a =====and a=b=1, which define the transition matrices: or (ii). (13.11) respectively. These two matrices define the two possible noiseless channels, for which there exists a one-to-one correspondence between the input and output symbols with 100% certainty. 3 Since there is no reason to have a one-to-one correspondence between the symbols or indices, we can also have p(yj|xi) = 1 for i # j and p(yj|xi) = 0 for i = j. Thus, a perfect binary symmetric channel can equivalently have either of the transition matrixes (see definition in text): P(Y)X) Since in the binary system, bit parity (which of the 1 or 0 received bits represents the actual 0 in a given code) is a matter of convention, the noiseless channel can be seen as having an identity transition matrix. 13.1 Channel capacity Channel capacity C a+b=1 Parameter Figure 13.3 Binary channel capacity C as a function of the two transition-matrix parameters a and b. The diagonal line a+b=1 corresponds to the useless-channel capacity C = 0. The diagonal line a = b corresponds to the binary symmetric-channel capacity C = 1 - f(a). The other diagonal line in Fig. 13.3 represents the channel capa