Quiz 2 Solutions

18 February 2014

You have up to 25 minutes. You may use a standard calculator if necessary, but no text book or notes.

  1. Below is a tree representing a variable-width encoding of 9 letters. Use it to:

    • decode the bits 111110100101 into a word: HINT
    • encode the word WITH as bits: 100110101111

  2. Decode the following 8×8 image indicated by the hexadecimal number along the right side, which uses 1 bit per pixel.

  3. If an image uses 5 bits for each pixel, what is the maximum number of distinct colors it can contain?

    2⁵ = 32 colors

  4. Draw a tree representing a variable-width encoding of the four letters M, I, S, and P. Use it to encode the word MISSISSIPPI. The fixed-width tree (below) uses exactly 2 bits per character, so encoding MISSISSIPPI requires 22 bits. How many bits does your tree need to encode MISSISSIPPI?

    A fixed-width encoding of four letters.

    A fixed-width encoding of four letters.

    Here is one possible solution. In this tree, M and P are extended to 3 bits each, so that S (or equivalently, I) can be just 1 bit. We can then encode MISSISSIPPI as 21 bits.