made far more difficult (without considering complex spelling and pronunciation rules). Optimal coding and compression 0.025 0.020 0.015 0.010 0.005 0.000 Figure 9.5 Two-dimensional histogram of the 26 X 26 = 676 English-letter digrams. Each row, corresponds to the distribution of counts c(y|x), where x is the first letter of the digram. The front row corresponds to the distribution c(A|x). The most frequent English digram, TH, corresponding to c(H|T) is highlighted. and the longest codewords to the less frequently used ones. A two-dimensional histogram obtained by counting the frequency of English digrams xy out of a 10 000-letter text is shown in Fig. 9.5. Each of these counts is noted c(y/x), see note. 12 We can view these digrams as forming an extended language source X(2), with virtually independent super-alphabet symbols of probability p(xy) = c(y|x)/10000. 13 We can then rearrange them in order of decreasing frequency, as shown in Fig. 9.6 for the leading group (c(y|x) > 100). 14 From the figure, we observe that the three most frequent digrams are TH, HE, and AN. It immediately comes to the mind that one could readily change these Plotted after analyzing raw data from: H. Fouché-Gaines, Cryptanalysis, a Study of Ciphers and Their Solutions (New York: Dover Publications, 1956). 12 The conversion of the histogram data c(y|x) into conditional probabilities p(y|x) is given by the property N c(y|x)p(x) p(y) III Ex p(y|x)p(x), which gives p(y|x) = Nc(y|x) = 13 For simplicity, the 27th "space" character was omitted in this count, as reflecting a tradition of old cryptography; single letters are, therefore, not included, but this does not change the generality of the analysis, since they can be coded as digrams with "space" as a second character. It is no surprise that we find TH, HE, AN, and IN as the most frequent digrams in English, suggesting an inflation of words and word prefixes, such as THE, THEN, THERE, HE, HERE, AN, AND, IN, and SO on. 9.3 Block codes Digram Figure 9.6 Arranging the leading English-lette