Devise an algorithm for decoding the LZW encoded output of Example 8.7. Since the dictiona...

Devise an algorithm for decoding the LZW encoded output of Example 8.7. Since the dictionary that was used during the encoding is not available, the code book must be reproduced as the output is decoded.

EXAMPLE 8.7: LZW coding.

Consider the following 4 × 4 8-bit image of a vertical edge:

Table 8.7 details the steps involved in coding its 16 pixels.A 512-word dictionary with the following starting content is assumed:

Dictionary Location

Entry

Locations 256 through 511 initially are unused.

The image is encoded by processing its pixels in a left-to-right, top-to-bottom manner. Each successive intensity value is concatenated with a variable— column 1 of Table 8.7—called the “currently recognized sequence.” As can be seen, this variable is initially null or empty.The dictionary is searched for each concatenated sequence and if found, as was the case in the first row of the table, is replaced by the newly concatenated and recognized (i.e., located in the dictionary) sequence. This was done in column 1 of row 2. No output codes are generated, nor is the dictionary altered. If the concatenated sequence is not found, however, the address of the currently recognized sequence is output as the next encoded value, the concatenated but unrecognized sequence is added to the dictionary, and the currently recognized sequence is initialized to the current pixel value. This occurred in row 2 of the table.The last two columns detail the intensity sequences that are added to the dictionary when scanning the entire 4 × 4 image. Nine additional code words are defined. At the conclusion of coding, the dictionary contains 265 code words and the LZW algorithm has successfully identified several repeating intensity sequences—leveraging them to reduce the original 128-bit image to 90 bits (i.e., 10 9-bit codes).The encoded output is obtained by reading the third column from top to bottom. The resulting compression ratio is 1.42:1.

TABLE 8.7 LZW coding example.