Problem Set 1

| categories: Problem Sets

Due Wednesday 14 September before the beginning of class

Some of the problems are probably too long to be done the night before the due date, so plan accordingly. Late homework will not be accepted. Feel free to get help from others, but the work you hand in should be your own. You may not use solutions to a previous year’s homework to aid you in completing this assignment.

Turn in your work by uploading a simple text file (txt not doc) to Blackboard. List your answers one per line. For example:

1a 5
1b 8

Problem 1: Information Encoding (18 points)

In lecture we learned that information resolves uncertainty, and that information is measured in units of bits. In order to uniquely identify one of N equally likely alternatives, log2N bits of information must be communicated. Use this information to solve the problems below:

  1. How many bits are necessary to encode an integer in the range of 0 to 31 (inclusive)?
  2. How many bits are necessary to encode an integer in the range of 0 to 200 (inclusive)?
  3. How many bits are necessary to encode an integer in the range of -256 to 255 (inclusive)?
  4. Consider a standard card deck (4 distinct suits; values 2-10, J, Q, K, A). How many bits are necessary to encode a card’s suit (ignoring value)?
  5. How many bits are necessary to encode a card’s value (ignoring suit)?
  6. Suppose we create a deck of cards that consists only of the number cards (2-9) and only has two suits. What is the smallest number of bits necessary to uniquely encode the new deck?

Problem 2: Two's Complement Representation (24 points)

Most computers choose a particular word length (measured in bits) for representing integers and provide hardware that performs operations on word-size operands. Many current generation processors have word lengths of 64 bits. Restricting the size of the operands and the result to a single word means that the arithmetic operations are actually performing arithmetic modulo 264.

Almost all modern computers use a 2’s complement representation for integers since the 2’s complement addition operation is the same for both positive and negative numbers. In 2’s complement notation, one negates a number by complementing each bit in its representation (i.e., changing 0’s to 1’s and vice versa) and adding 1. By convention, we write 2’s complement integers with the most-significant bit (MSB) on the left and the least-significant bit (LSB) on the right. Also by convention, if the MSB is 1, the number is negative; otherwise it’s non-negative. Use an 8-bit 2’s-complement representation to answer the following questions:

  1. What is the binary representation for 0?
  2. What is the binary representation for the most positive number that can be represented?
  3. What is the binary representation for the most negative number that can be represented?
  4. What is the decimal value for the most positive number?
  5. What is the decimal value for the most negative number?
  6. What is the result of negating the most negative number?

Problem 3: Hexadecimal Representation (12 points)

Since writing a long string of binary digits gets tedious, it’s often convenient to use hexadecimal notation where a single digit in the range 0—9 or A—F is used to represent adjacent groups of 4 bits (starting from the left). Give the corresponding 8-digit hexadecimal encoding for each of the numbers below.

  1. 1023 (decimal)
  2. -128 (decimal)
  3. 1111 0001 0000 0011 1111 0111 1010 1001 (binary)
  4. 1010 0101 1100 1000 0000 0101 0011 1111 (binary)

Problem 4: Binary Arithmetic (25 points)

Calculate the following using 8-bit 2’s-complement arithmetic (which is just a fancy way of saying to do ordinary addition in base 2 keeping only 8 bits of your answer). Remember that subtraction can be performed by negating the second operand to form its 2’s complement, and then adding it to the first operand. Give your answers in binary.

  1. 14 + 36
  2. 55 - 20
  3. 20 - 55
  4. 120 + 110
  5. Explain what happened when you retained only the lower 8 bits of the result in part d.

Problem 5: Fixed-Point Binary (20 points)

Using a 16-bit fixed-point binary representation, where the leftmost 8 bits are the integer part (i.e., before the binary point), and the rightmost 8 bits are the fractional part, convert the following numbers.

  1. Convert 11.25 decimal to binary.
  2. Convert -15.0625 decimal to binary.
  3. Convert 01111100.10101000 binary to decimal.
  4. Convert 11111101.10010000 binary to decimal.