Solutions for HW4:

Problem 1a

Y1 = Q1' Q2 X'
Y2 = X + Q1' Q2
Z  = Q1 Q2 X

Problem 1b

Problem 2a

  5 =   101
  6 = 11010
 -7 =  1001
 11 = 11111

Problem 2b

A four-bit base (-2) system is contiguous:

  5 = 0101
  4 = 0100
  3 = 0111
  2 = 0110
  1 = 0001
  0 = 0000
 -1 = 0011
 -2 = 0010
 -3 = 1101
 -4 = 1100
 -5 = 1111
 -6 = 1110
 -7 = 1001
 -8 = 1000
 -9 = 1011
-10 = 1010
The maximum and minimum values are 5 and -10, respectively.

Any n-bit base (-2) system is contiguous. Proof by induction: Suppose an (n-1)-bit base (-2) system is contiguous. Note that such a system covers 2^n consecutive integers. Adding another bit covers twice as many integers; if x is covered by the (n-1)-bit system, then both x and x+((-2)^n) are covered by the new system. These integers are unique, since the (n-1) bit system only covers 2^n consecutive integers, so the new integers covered do not overlap with the existing integers. Also, the new system is contiguous, since adding (-2)^n is equivalent to shifting the covered integers by (-2)^n on a number line.

The base case for the induction is trivial; consider a 1-bit base (-2) system.

Problem 2c

    111    <- carry 1
     011   <- carry 2
    001110    (-6)
  + 001111    (-5)
  --------
    110101    (-11)

Problem 2d

    A B CIN | COUT1 COUT2 S
    --------+--------------
    0 0  0  |   0     0   0
    0 0  1  |   0     0   1
    0 1  0  |   0     0   1
    0 1  1  |   1     1   0
    1 0  0  |   0     0   1
    1 0  1  |   1     1   0
    1 1  0  |   1     1   0
    1 1  1  |   1     1   1