In LZW coding, the message “AACCCBCCDDAB” is given.

a. Encode the message. (See Figure 28.2.)

Figure 28.2

b. Find the compression ratio if we use 8 bits to represent a character and four bits to represent a digit (hexadecimal).

Message| BABAABB Notes: LZW Encoding Dictionary In each iteration, we show char A whether an if-clause or an B 1 B B else-clause is executed. Loop Only the else-clause generates a new entry in the dictionary and code. Pres char Pres + char Dictionary else A 2 BA else A AA 3 AA A Legend: char: Next character S: String else A AB AB if B BA PreS: Previous S C: Codeword else BA B BAB 5 BAB B else B BB 6. BB if BB BB else BB A BBA BBA 6. if A AA AA else AA B AAB 8 AAB B if B BB BB else BB B BBB 9 BBB 6 B if B B BB BB BB A BBA else| BBA A BBAA 10 Code 1002163670 ---------------------------- --------------