it codes for symbols G and O are (1000111) and (1001111), respectively. So in Table 10.4, the encoder, thus, needs to output (0) (1000111) = (01000111) at stage k = 1 (new symbol G), (1001111) = (11001111) at stage k = 2 (new symbol O), (00) at stage k = 3 (old symbol O), and SO on. Since the first part of each of these codewords is a prefix code known by the decoder (from the previous stage) and the second part is a standard fixed-length code, the decoder can make sense of the codewords as an uninterrupted stream, without Table (Top) number and symbol of bits definitions information X. to For clarity, provided the by last the two encoder lines indicate at each coding whether step the k for the GOODTOSEEYOU example described in Table 10.3, with corresponding codewords required convey the information at each step, where n is the incoming fixed codeword symbols length in the message used to define string the are symbols. new or old, and the message status; (Bottom) k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 k = 9 k = 10 k = 11 k = 12 GOODTOSE GOODTOSEEY 2 + n 3 + n TOSEE GOODTOSEE 3 + n 4 + n TOSEE YO 4 + n 4 + n 10.3 Adaptive Huffman coding needing any codeword delimiters or blanks. The data shown at the bottom of Table 10.4 indicate that the total information required to encode GOODTOSEEYOU takes 32 + 8n bits, which, for n = 7, comes to 88 bits. For comparison purposes, consider the case of static Huffman coding. In this case, the encoder first reads the full message GOODTOSEEYOU and then computes the Huffman coding tree, which yields the same codeword assignment as shown in Table 10.3, except that the symbol is not used. The encoder must then define the coding tree as overhead information. From the table data, and assuming n bits to define each of the eight symbols (G, O, D, T, S, E, Y, U), the overhead size comes to 2x(2 + n) + 3x(3 + n) + 3x(4+ n) = 29 + 8n. With n = 7, the overhead size is, therefore, 85 bits. On the other hand, the GOODTOSEEYOU message payload represents 2x(2) + 3x(3) + 3x(4) = 25 bits. The t