eword size. As we have seen, the LZ algorithm imposes the constraint that the first two codewords in the sequence be of the form 000 00 or 000 01, namely a 0 or 1 bit preceded by a prefix of size L2 - 1 bits. This information automatically provides the codeword length L2. The decoder then registers successive codewords up to rank 2L2-1 which represent the LZ code alphabet, and puts them into a dictionary along with their corresponding source-message contents. For instance, the codeword 10001 at line 10 of the decoder's memory (pointer = 10) means 1 preceded by the message contents of line 10002 = 810 (pointer = 8). According to the same rule, this content has been established to be 0101, SO the content of line 10 is 0101 + 1 = 01011. The whole process is strictly equivalent to reconstructing the equivalent of Table 10.5 from top to bottom, but starting from each new codeword received up to 2L2-1 It is a remarkable feature that the decoder is able to interpret the LZ code without any dictionary being ever transmitted. 10.4 Lempel-Ziv coding 0101101101001000101010010101101001001011101001010 01110010111010101110001001010101110001011101010111 00010110101110101011101001001011101010111010100101 1011100010111010111000100101010111000101110101011 01-12-013-104-115-0106-01007-01018-01001g-0101110-01 01011112-010010113-010111014-0101110115-0101110016 (b) 0100101-01011100-01011101-01011100-01011-01011101- 10111-010010-01011101-01011101-0100101-01011100 010111-01011100-0100101-01011100-01011101-01011- 00000000010001100100001010011001100011010111110001 100101010110111 100011101 1110010111 11110011101 100011110110101 1001011101 1110110111 1110010101 11100 10111111001110110001 Figure 10.5 Coding a message bit sequence with the Lempel-Ziv (LZ) algorithm: (a) Input message (200 bits including 95 Os and 105 1s); (b) Parsing of message (a) into distinct phrases, as shown in alternative black and gray colors; the first 16 phrases generate the LZ codewords (see correspondence in Table 10.6); the 16 subscripts correspond to pointer add