babilities. As seen in the figure, there exist two neighboring sets, A and B, with probabilities close to the typical set, namely -logp(xA) = 6.509 and -logp(xB) = 4.509, respectively. The two sets correspond to sequences similar to the O sequences with one 1 bit either in excess (A) or in default (B). Their log prob- abilities, therefore, differ by +1 with respect to that of the 0 sequence. In particular, 9 For simplicity, we shall assume that kq is an integer number. Channel capacity and coding theorem Sequence X Typical set 000000 000000000000000 000000000000000 cococo H(X6)=5.509 = Sequence X Figure 13.4 Illustration of a tentative definition of the typical set for a binary sequence with length k=6 and probability of 1 symbol q = 1/3 (source entropy kH(X) = 5.509 bit: (a) probabilities (- log2 p(x)) of each sequence x as ordered from x = 000000 to x = 111111; (b) same as (a) with sequences ordered in increasing order of probability. The typical set corresponds to sequences having kq = 2 bits equal to 1, with uniform probability - -log2p(x) = kH(X) = 5.509. The two neighboring sets, A and B, with similar probabilities are indicated. we have og (p(x Aor B) kH(X) (13.24) 0.16. Because the absolute differences defined by Eq. (13.24) are small, we can now extend our definition of the typical set to include the sequences from the sets A and B, which are roughly similar to O sequences within one extra or missing 1 bit. We can state that: The sequences from A and B have roughly kq 1 bits and k(1 - q) 0 bits; The corresponding probabilities are roughly equal to 2-H(X*) According to this extended definition of the typical set, the total number of typical sequences is now N = 15 + 6 + 20 = 41. We notice that N 2 2H(X) = 45.5, which leads to a third statement: The number of typical sequences is roughly given by 2H(X*). 13.3 Shannon's channel coding theorem The typical set can be extended even further by including sequences differing from the O sequences by a small number U of extra or missing 1 bits. Their log probabilit