ence. For a sufficiently long message sequence, it is expected that the entropy reaches the limit of that of the English-language source, which was shown in Chapter 4 (1982 poll) to be H = 4.185 bit/symbol. Such a con- vergence must be quite rapid, since a message as short as GOODTOSEEYOU has the entropy of H = 2.751 bit/symbol (Table 10.3), which represents 66% of this limit. We also observe from Fig. 10.4 that the coding efficiency rapidly converges to 100% as new symbols come in, although with a similar saw-tooth progression for entropy. With this message-sequence example, the efficiency reached at k = 12 is n = 91.72% (Table 10.3), a relatively high performance due to the optimality of the Huffman coding (the mean codeword length L always remaining within one bit of the source entropy H, as the table data also indicate). As we have seen, the encoder dynamically updates its coding tree at each step k, starting with a single -node leaf. From the receiving side, the decoder just has to perform the same operation. However, for the decoder to update its coding tree, it needs the following basic information: (a) For a new symbol: the -node's current codeword and the new symbol definition; (b) For a symbol previously observed: the symbol's current codeword. 10.3 Adaptive Huffman coding k = 1 (G) k = 2 (GO) k = 3 (GOO) D 000 k = 4 (GOOD) G 000 D 001 G 111 T 010 D 110 T 101 k = 5 k = 6 (GOODT) (GOODTO) Figure 10.3 Evolution of the adaptive Huffman coding tree with the message example GOODTOSEEYOU. The index k is the number of symbols received: (a) k = 1-4; (b) k = 5-6. Nodes are relabeled according to the sibling-property rule. The number inside each node's circle is the corresponding weight. The steady or changing codewords associated with each symbol are shown at the right. The evolution of the coding tree and codeword assignment up to k = 12 is shown in Table 10.3. Table 10.3 Evolution of coding tree according to the adaptive Huffman coding algorithm with the 12-symbol message example GOODTOSEEYOU The index is the 