Transistors, Gates, and Boolean Logic

1. (10 points) Consider the truth table for the following three-input, two-output function:

A B C -> D E
0 0 0 -> 1 0
0 0 1 -> 0 0
0 1 0 -> 1 1
0 1 1 -> 0 1
1 0 0 -> 1 1
1 0 1 -> 0 1
1 1 0 -> 1 0
1 1 1 -> 1 0

How many terms must a PLA support in order to implement these two functions? Use Boolean algebra to simplify the two-level logic formulas for the functions D and E to their simplest form. Show the steps and the rules invoked.

2. (10 points) Draw the CMOS transistor diagrams for the D and E functions from problem 1. Assume you are given the inputs A, A', B, B', C, and C'. Hint: remember, the function of a gate is the NOT of the function implemented by the nMOS network.

Computer Arithmetic

3. (15 points) Consider a 64-bit adder. Compute the number of gate levels for the 0th, 5th, 16th, 55th, and 63rd sum bits for the following adder designs:

• Ripple-carry
• Carry-select with four sub-adders
• Carry-select with eight sub-adders
• Two-level carry-lookahead with 8-input blocks at each level
• Three-level carry-lookahead with 4-input blocks at each level

4. (15 points) Given the multiplicand -55 and the multiplier 93, trace the following multiplication algorithms:

• Adder-only
• Booth's
• Modified bit-pair Booth's.

5. (10 points) Divide the binary representation of 104 by 6 using the division algorithm shown in class. Assume that the divisor (S), dividend (D), quotient (Q), and remainder (R) are all 8 bits wide. At each step, show the quotient and remainder and label the action taken by the divider (e.g., Q = Q - S).

R372 Assembly Programming

(30 points) If you noticed, the R372 is conspicuously missing one of the arithmetic instructions: divide. The primary reason for this is that (as you have seen in class), the divide circuit is cumbersome to implement in hardware. The multiply circuit is somewhat simpler to implement, but is a sequential circuit. Since our first R372 processor implementation will be "single-cycle", it will not be able to support multiplication.

For this exercise, you will implement multiplication and division in software as R372 assembly routines using the single-cycle R372 operations, i.e., all operations other than multiplication.

The multiply routine should have the following interface. It should be called MULS. For the input arguments, the multiplicand should be in R3 and the multiplier should be in R4. For the return value, R2 should contain the lower 16 bits of the product. You can ignore overflow.

The divide routine should have the following interface. It should be called DIVS. For the input arguments, R3 should contain the dividend and R4 should contain the divisor. For the return value, R2 should contain the quotient. You can ignore the remainder.

Both multiplier and divider should work with negative numbers. You can use any multiplication or division algorithm you want (hint: it's easier to use conventional software ones than ones that correspond directly to the hardware algorithms learned in class), but you are not allowed to call MULS from within DIVS.

As for program linkage, you may assume that the stack pointer is in R1. Also, the only register either MULS or DIVS can externally modify is the return value register R2.