the second number is the differing bit (referred to as extension character). The LZ codeword is given by concatenating the pointer and the extension character, with the pointer expressed in binary. The first two phrases, which are made of a single bit, are concatenated with pointer k = 0, which corresponds to the empty phrase. From these rules, we obtain from our example: Phrase: 01 10 11 010 0100 0101 101 100; Pointer (decimal): 12345678910; (Prefix pointer, bit), decimal: (2, 0) (2, 1) (6, 0) (6, 1) (4, 1) (4, 0). Integer, arithmetic, and adaptive coding Table 10.5 Lempel-Ziv (LZ) codeword dictionary generated from the message example 0101101101001000101101100. The last bit of the LZ codewords is highlighted for reading clarity. Pointer Phrase (Prefix pointer, bit) Codeword (0, 0) 00000 (0, 1) 00001 (1, 1) 00011 (2, 0) 00100 (2, 1) 00101 (3, 0) 00110 (6, 0) 01100 (6, 1) 01101 (4, 1) 01001 (4, 0) 01000 The sequence is, thus, coded into the following decimal representation: (0, 0) (0,1) (1, 1) (2, 0) (2, 1) (3, 0) (6, 0) (6, 1) (4, 1) (4, 0), which must be converted into a string of binary codewords, as listed in Table 10.5. The set of LZ codewords is referred to as a dictionary. Given the fixed codeword length L2, which is the number of pointer or address bits plus one, the maximum dictionary size is, therefore, 2L(2)-1. In this example, we allot four bits to the pointer, which limits the dictionary size to 24 = 16 codewords of length L2 = 5 bits. Based on Table 10.5, the initial 25-bit message is thus converted into the following coded string (underscores being introduced for reading clarity): which is 50 bits long. The LZ code, thus, realizes a twofold expansion of the source message, which is a characteristic feature of the initialization stage. As the message length increases, the bit phrases become more redundant, and the benefits of LZ coding for data compression begin to appear, as discussed later. Decoding an LZ sequence is straightforward. A nice feature is that the decoder does not need to know the cod