The input to the LZW decoding algorithm for the example in Example 8.12 is

The starting dictionary, to be consistent with the coding itself, contains 512 locationsw with the first 256 corresponding to gray level values 0 through 255. The decoding algorithm begins by getting the first encoded value, outputting the corresponding value from the dictionary, and setting the }recognized sequence} to the first value. For each additional encoded value, we (1) output the dictionary entry for the pixel value(s), (2) add a new dictionary entry whose content is the }recognized sequence} plus the first element of the encoded value being processed, and (3) set the }recognized sequence} to the encoded value being processed. For the encoded output in Example 8.12, the sequence of operations is as shown in Table P8.16.

Note, for example, in row 5 of the table that the new dictionary entry for location 259 is 126-39, the concatenation of the currently recognized sequence, 126, and the first element of the encoded value being processedwthe 39 from the 39-39 entry in dictionary location 256. The output is then read from the third column of the table to yield

where it is assumed that the decoder knows or is given the size of the image that was recieved. Note that the dictionary is generated as the decoding is carried out.