ced in the next list. We see that the last two symbols (x3, x4) represent a probability of 0.3, which comes in second position, after X1 and before X2. Then the pair [x2, (x3, x4)] represents the same probability as X1, but we place it on top of the next list, according to the above rule. The groundwork is now complete. The code assignment simply consists in following the arrows and writing down the 0 or 1 bits encountered in the path. The codeword is the same word but with the bits written in the reverse order. For instance, we find for X4 the bit path 100, SO the codeword is 001. For x2, we find 10, SO the codeword is 01, and SO on. How efficient is Huffman coding? It is easy to calculate that in the above example, the mean codeword length L is 1.80 bit/word. The entropy H is 1.76 bit/symbol. The coding efficiency is, therefore, n = 1.76/1.8 = 97.8%, which is nearly ideal. For comparison, if we had attributed to each of the symbols the same codeword length of two bits, we would have L = 2 and n = 1.76/2 = 88%. If we used the Shannon-Fano code, it is easily verified that the mean length L** is 2.1 bit/word, and the efficiency drops to n = 1.76/2.1 = 83%. To become further convinced of the merits of Huffman coding, consider again the English-character source, for which we have already explored several coding possibilities (namely, 5-bit ASCII, Morse, and Shannon-Fano). It is a patient exercise (although not without fun, as the reader should experience) to proceed by hand through the successive steps of the Huffman algorithm on a large piece of paper or a blackboard. 2 The results are shown in Table 9.1 (codeword assignment) and Fig. 9.2 (coding tree). As the table shows, the minimum codeword length is three bits (two symbols) and the maximum is nine bits (four symbols). The mean codeword length is 4.212 bit/symbol, yielding a remarkably high efficiency of n = 4.184/4.212 = 99.33%. A comparison between Table 9.1 (Huffman code) and Table 8.5 (Shannon code, binary) only reveals apparently small differences in codewo