15110 Fall 2011 [Cortina/von Ronne]

Written Homework 6 - due THURSDAY, October 20 in LAB

Reading Assignment

Read sections 7.1-7.6 in chapter 7 of the textbook Explorations in Computing and chapter 3 of Blown To Bits.

Instructions

Type or neatly write the answers to the following problems.
Please STAPLE your homework before you hand it in.
On the first page of your homework, include your name, andrew ID, lab section (A-N), and the assignment number.
You must hand in your homework at the start of class on the given due date.

Exercises

(2 pts) The 8-bit value 11100111 might be an unsigned integer, signed integer, or ASCII character transmitted with even parity.
1. What is its value if it is interpreted as an unsigned integer? Show your work.
2. What is its value if it is interpreted as a signed integer? Show your work.
3. What is its value if it is interpreted as an ASCII value transmitted with even parity? (Note: The parity bit is the leftmost bit.)
4. If the binary value above represented a character and was transmitted and then received as 11110101, would the receiver be able to detect the error? Why or why not?
(1 pt) Another way to represent unsigned integers is to use a representation called Binary Coded Decimal (BCD). In this representation, each decimal digit of an integer is represented using 4 bits as follows:
```
0     1     2     3     4     5     6     7     8     9
0000  0001  0010  0011  0100  0101  0110  0111  1000  1001
```
1. Show how to represent the integer 15110 using BCD.
2. If we represent an integer using BCD with 16 bits, what are the minimum and maximum values that can be stored using this representation?
(1 pt) Show how to represent the binary floating point value +111.010101 X 2²⁴ using the IEEE-754 standard for single-precision floating point values (using 32 bits). Show your work.
(2 pts) The Rotokas language is spoken in central Bougainville in Papua New Guinea. The Rotokas alphabet consists of 12 letters. The relative frequency of each letter based on a set of Rotokas text is given below:
```
A   0.218
E   0.088
G   0.013
I   0.111
K   0.022
O   0.130
P   0.055
R   0.118
S   0.018
T   0.031
U   0.072
V   0.124
```
1. Using RubyLabs, build a Huffman tree using these frequencies. Draw the resulting tree.
2. Using RubyLabs and the tree from part (a), write the Huffman code assigned to each letter.
3. Encode the Rotokas word EKARAU (meaning: sugar cane) using Huffman codes.
4. If we encoded the Rotokas word EKARAU using a fixed width code, what is the minimum size of the encoded word in bits? How does this compare to the Huffman encoding?
(1 pt)
1. An image has pixels that use only 128 colors. What is the minimum number of bits needed to represent each pixel? Explain your answer.
2. Pixels can be represented by specifying the amount of red (R), green (G), and blue (B) to combine to obtain the color on a computer screen. Each of these values can range from 0 to 255, inclusive. The color sienna has an R value of 160, a G value of 82, and a B value of 45. How would this color be represented in a computer in hexadecimal? (Hint: Convert the values to binary first.)
(1 pt)
1. If a musical recording is sampled in stereo at a rate of 44,100 samples per second and each sample is 16 bits, exactly how many bytes are required to store 1 minute of this music? Show your work.
2. A CD can typically store 700MB of data. If we represent audio files using the MP3 compression standard using a bit rate of 160 Kbps (kilobits per second), how many whole songs can we store in MP3 format on the CD if each song is exactly 4 minutes long? You may assume the CD has no other information stored (e.g. index information, titles, etc.).
(2 pts) Based on Chapter 3 of Blown To Bits, answer the following questions about data representation.
1. Bob highlights a sensitive message in a Word document and changes its color to white to match the background of the document so others won't see it. If he sends this document to Alice, does she have the sensitive information? Why or why not?
2. What is spatial coherence and temporal coherence with respect to images? How does each concept allow us to transmit images using fewer bits?
3. Steganography is the hiding of information within other information. Using one of the examples given in the chapter as a guide, find the hidden message in the following announcement:
  
  Important Liability Information: Keep employees productive! Reduce injuries now. Carefully inspect packages, listing each sender on formatted cards. On Mondays, please unload trucks inside North garages.