ain: (13.41) which, after straightforward computation, yields p(13) 2 1.8 x 10-18. Because of the rapid decay of other higher-order probabilities, it is reasonable to assume, without any tedious proof, that p(e > 12) < 1.0 x 10-18, corresponding to an average single- bit error within one billion billion bits, which means that this RS code, with rate R = 0.905 < 0.9985 = C, is pretty much adequate for any realistic applications. Yet there surely exist better codes with rates close to the capacity limit, as we know with error-correction capabilities arbitrarily close to the BER = 0 absolute limit. To conclude this chapter, the CCT is a powerful theorem according to which we know the existence of coding schemes enabling one to send messages through a noisy chan- nel with arbitrarily small transmission errors. But it is important to note that the CCT does not provide any indication or clue as to how such codes may look like or should even be designed! The example code that we have used as a proof of the CCT con- sists in randomly choosing 2nR codewords from the input typical set of size 2nH(X) As we have seen, such a code is asymptotically optimal with increasing code lengths n, since it provides exponentially decreasing transmission errors. However, the code is impractical, since the corresponding look-up table (yj Xi), which must be used by the decoder, increases in size exponentially. The task of information theorists is, therefore, to find more practical coding schemes. Since the inception of the CCT, sev- eral families of codes capable of yielding suitably low transmission errors have been developed, but their asymptotic rates (R = (log M)/n) still do not approach the capacity limit (C). 13.4 Exercises Exercises 13.1 (M): Consider the binary erasure channel with input and output PDF, p(X) = [p(x1), p(x2)], P(Y)=(p(y1),p(o),p(y2)], and the transition matrix, Demonstrate the following three relations: H(Y)=f(e)+(1-e)f(q), H(Y|X) = f(e), H(X;Y)=H(Y)-H(YX)=(1- -E)f(q), where q = p(x1) and the function f(u) is define