we have learnt earlier, variable-length codes are in the general case more efficient than fixed-length ones. The most frequent source symbols are assigned the shortest codewords, and the reverse for the less frequent ones. The coding-tree method makes it possible to find some heuristic codeword assignment, according to the above rule. Despite the lack of further guidance, the result proved effective, considering that we obtained n = 96.23% with a ternary coding of the English-character source (see Fig. 8.3, Table 8.3). But we have no clue as to whether other coding trees with greater coding efficiencies may ever exist, unless we try out all the possibilities, which is impractical. The Huffman coding algorithm provides a near-final answer to the above code- optimality issue. The coding algorithm consists in four steps (here in binary imple- mentation, which is easy to generalize to the M-ary case1): (i) List the symbols in decreasing order of frequency/probability; (ii) Attribute a 0 and a 1 bit to the last two symbols of the list; (iii) Add up their probabilities, make of the pair a single symbol, and reorder the list (in the event of equal probabilities, always move the pair to the highest position); (iv) Restart from step one, until there is only one symbol pair left. In ternary coding, for instance, the symbols must be grouped together by three; in quaternary coding, they should be grouped by four, and SO on. If there are not enough symbols to complete the M groups, dummy symbols having zero probabilities can be introduced at the end of the list to complete the tree. Optimal coding and compression Symbol Probability Figure 9.1 Implementation of Huffman coding for the source x = {X1,X2,X3,X4} with associated probability distribution p(x) = {0.5, 0.2, 0.2, 0.1}. An example of Huffman-coding implementation is provided in Fig. 9.1. The source is X = {x1, X2, X3, x4}, with respective probabilities p(x) = {0.5, 0.2, 0.2, 0.1}. The figure shows how the above-described pairs are formed and their probability sums repla