s 29 = 512 terminal nodes, and 210 - 1 = 1023 nodes in total. Our coding tree, thus, represents a trimmed version of the complete order-9 tree. One says that the first is "embedded" into the second. Note that the symbol/codeword assignment we have derived here is not unique. For instance, the codewords of letters E and T can be swapped, and any codeword of length l can be swapped within the group of Optimal coding and compression 00000 D 000010 G 0010 o 00110 L 000011 Y 0001 A 001110 P 001111 B 0100 I 0101 N 011 E 1100000 K 1000 S 110000100 J 1001 H 110000101 X 1010 R 10110 C 110000110 Q 10111 U 110000111 Z 110001 V 11001 M 11010 W 11011 F 111 T Figure 9.2 Coding tree for A-Z English-character source and binary codeword assignment (see also Table 8.5). The convention is that branches pointing upwards are labeled 0 and branches pointing downwards are labeled 1. m symbols assigned the same length (representing m! possible substitutions, for instance 7! = 5040 for symbol groups numbering m = 7). Additionally, all bits can be logically inverted, which generates a duplicated set of codewords. From the coding tree in Fig. 9.2, one calculates that the number of possible sym- bol/codeword assignments yielding the same coding efficiency is, in fact: N=2x(2! x7!x7!x5!xl!x4!)= 292 626 432 000 = 2.92 1011 , (9.1) which represents no less than some 300 billion possibilities! The two previous examples illustrate that Huffman coding is an optimal code that brings coding efficiency relatively close to the 100% limit. However, such a conclu- sion appears to be in contradiction with a key result obtained in Chapter 8 concern- ing the Shannon-Fano code. Indeed, we have seen that any codeword-length assign- ment i(x) = [-logq(x)] that is different from that of the Shannon-Fano code, namely, *(x) = bgp(x)], results in a "penalty" for the mean codeword length, L(X). Such a penalty is equal to the Kullback-Leibler (KL) distance D = D(pllq), or, after Eq. (8.17), L(X) [HM(X) + D, HM(x) + D + 1]. Yet, we should not conclude from this res