Quiz 2 Solutions

30 September 2013

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

  1. How many bits per symbol would you need to encode telephone numbers from a phone keypad as shown. Use a fixed-width encoding. 4 bits, because 2⁴=16 is enough symbols (but 2³=8 is not).

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

    • decode the bits 0001101110011101 into a word: LIGHT
    • encode the word THING as bits: 0111111010011100

  3. 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 uses 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.

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

    2⁵ = 32 colors

  5. You have a friend who is always drawing in notebooks, and recently learned the Adobe Illustrator software. She’d like to begin publishing a comic strip on the web, and she is asking you for technical advice. Illustrator can export her work as JPEG, PNG, GIF, or TIFF. Which format should she use, and why?

    The best format for line drawings and cartoons is PNG. (I also accepted GIF because it’s also lossless, and the 256-color restriction is usually not an issue for cartoons. TIFF offers the same quality as PNG, but isn’t supported by as many web browsers.