20 points total

Part I  (8 points)

1. (1 point) Match the following 5-bit representations of -12 with the names of these representations:

A. 11100
B. 10100
C. 00100
D. 10011

a. biased with B=24
b. one's complement
c. two's complement
d. signed-magnitude

2. (1 point) Arrange the following signals in the order they are generated within the 64-bit 3-level carry lookahead adder, starting from a signal that is generated first. Assume that the adder is built of AND, OR, and XOR gates, and that delays of all these gates are equal.

A. c53
B. c8
C. g[36, 39]
D. c48
E. s15

3. (1 point) Arrange the following numbers in the ascending order:

A. (3A)16
B. (152.26)-10
C. (2 -2 3 -3)4
D. (111.33)1/10
E. (1 0 -1 1 -1)3

4. (1 points) Arrange the following 16-bit adders in the order of increasing worst case delay. Assume that all adders are built of AND, OR, and XOR gates, and that the delays of all these gates are equal. Every adder accepts carry-in and produces carry-out.

2. Kogge-Stone Parallel Prefix Network adder
3. Brent-Kung Parallel Prefix Network adder

5. (1 point) Determine all outputs of an 8-bit carry-save adder fed with the following three numbers:

0111 1101

1101 0110

0110 1110

6. (1 point) Using dot notation, show addition of eight 5-bit numbers in the Dadda's tree.

7. (2 points) Multiply the following two 8-bit unsigned numbers using sequential shift-and-add multiplier with right shifts. Show all intermediate operands and partial products in the binary notation.

a = 9710
x = 10810

Part II (12 points)

1. (3 points) Design a 16-bit adder using the following components: 16-input Kogge-Stone parallel prefix network (Parhami, Fig. 6.10) built of NAND gates, supplemented with additional NAND gates. Estimate the delay and area of this adder expressed in the number of gate levels and the number of NAND gates respectively.

2. (3 points) Draw a detailed block diagram for a 4-bit signed sequential shift-and-add multiplier with right shifts, capable of computing p =  a · x + y, where a, x, and y are all 4-bit signed number. Assume that you can use only D-flip flops, full adders, 2-to-1 multiplexers, and AND, OR, and XOR gates. Mark the critical path in your circuit, and write a formula for the minimum latency of this multiplier.

3. (3 points) Design a minimum-area 10-bit counter that counts in steps of 5 starting from 0 to 1000, and then resets itself and starts counting again. Assume that you can use the following components in your design: half-adders shown in Parhami, Fig. 5.1, full-adders shown in Parhami, Fig. 5.2a, and additional NAND gates.

4. (3 points) Show all intermediate operands and partial products in the multiplication of the following two unsigned 8-bit numbers using a sequential shift-and-add multiplier with a carry save adder shown in Parhami, Fig. 10.8:

a = 10110
x = 17210