Midterm 1
Thurs, Oct. 18, 2018, 9:45AM to 11:00AM.
1. Number Systems and the Complement Method for Negative Numbers [40 points]
(a) Number Systems
i. In what base is the following operation performed:
ABC + CBA = 1443
[15 points]
ii. Show how to represent the numbers (A3 − 1) and (A3 + 1) as base eleven numbers. [5 points]
iii. Show how to represent (b n − 1) and (b n + 1) as a base b numbers, where b can be any integer larger than 1 and n any integer larger than 0. [5 points]
(b) Complement Method
In class, we learned how to compute the two’s complement of a number in base 2. Consider now a generalization of that concept to other bases. Consider base b. With n digits, represent the negative of a number v as b n − v. (Call this “b’s complement.”)
i. First list all numbers in base 4 with two digits.[1 point]
ii. Next assign positive and negative numbers (in base 10) to the numbers that you just listed in base 4. What range of values can you represent? [2 points
iii. For base 10, with 10’s complement, what range of numbers can you represent with 4 digits? [2 points]
iv. For base b, what range of numbers can you represent with n digits? [5 points]
v. Show how to perform. the operation 498−499 in 10’s complement arithmetic. [5 points]
2. From Truth Tables to Gates [35 points]
Consider a circuit that accepts as inputs four bits a, b, c, d. Suppose it computes the function f = XNOR(a, XNOR(b, XNOR(c, d))).
(a) Truth Table Design
Fill in the following truth table. [5 points]
(b) From Truth Tables to Gates
i. Draw a minimal 2-level circuit consisting of all NAND gates that implements the function. [10 points]
ii. Draw a minimal 2-level circuit consisting of all NOR gates that implements the function. [10 points]
iii. Express the function in XNF (that is to say, as the XOR of AND terms, with no negations). [10 points]
3. Circuits for XOR [25 points]
Draw a circuit to compute the XOR function of 26 variables with only OR gates and inverters. Use as few OR gates as possible. (Note that you can define smaller circuits, put these in “boxes”, and use these boxes to build larger circuits. However, you must specify everything in the smallest box.)