(1) Consider the logic schematic diagram shown below:
(a) What are the next-state and output equations for this machine? [15]
(b) Draw a state transition graph (STG) for the machine showing all possible states and all possible transitions [15]
(2) This problem concerns a base-(-2) (base-(minus-two)) adder. In CS150 so far, we only considered number systems with positive bases (in particular, the binary, or base 2, system). For example, in a base 3 system, the number ABCD3 is equal to:
ABCD3 = A*33 + B*32 + C*31 + D*30.
So for a base (-2) system, EFGH-2 would be computed using:
EFGH-2 = E*(-2)3 + F*(-2)2 + G*(-2)1 + H*(-2)0
(a) Convert the following decimal numbers to base-(-2): 5, 6, -7, 11. Use as many bits as you need. [20]
(b) For the purpose of this problem, we define a number system as contiguous if, given any two integer values m and n which can be represented in the number system, there exists no integer value x, with m< x < n, that cannot be represented in the system. For example, a 1-bit decimal system is contiguous. It can represent the counting numbers 0-9, and there are no numbers in between 0 and 9 which cannot be represented using one decimal digit. The binary number system (base 2) is also contiguous.
(i) Is a four-bit base-(-2) system contiguous? [5]
(ii) What are the maximum and minimum values (in decimal) that can be represented by a four-bit base-(-2) system? [10]
(iii) Is an n-bit base-(-2) system contiguous, where n is any positive integer? Justify your answer. [5]
(c) Perform the following addition in base-(-2). [10]
001110-2 + 001111-2
Pay close attention to the carry-in and carry-out aspects because they are important below.
(d) Draw a truth table for a one-bit bit slice of a base-(-2) adder. Assume one bit of carry-in. You must determine the specification for the carry-out. [20]