Behrooz Parhami, Computer Arithmetic: Algorithms and Hardware Design
Chapter 5, Basic Addition and Counting, Sections 5.1-5.5,
pp. 75-85.
Problem 1: 13 points
Design on paper and analyze:
k-bit ripple-carry adder
k-bit bit-serial adder
k-bit digit-serial adder with the digit size d (a digit serial adder is an adder that in each clock cycle processes d-bits of operands X and Y, and generates the corresponding d bits of the sum S)
using the following assumptions:
each adder is
composed of two-input, three-input, and four-input NAND gates only
optimized for minimum latency.
For each adder:
a. draw a schematic of this adder composed of medium level components (such as full adders, half adders, multiplexers, D flip-flops, etc.), and the detailed schematic of each medium-level combinational component, implemented using NAND gates only.
b. mark the critical path within each medium-level component and for the entire circuit. Assume that all inputs to the adders, including all control signals are registered. Take the register delay and register setup time into account for all adders including a ripple-carry adder.
c. determine the area and latency of each medium-level component expressed in terms of the delay and area of a single two-input NAND gate. Assume that the delay of a NAND gate is independent of the number of inputs, and its area is proportional to the number of inputs. Do not include the areas of the surrounding input and output registers in your computations.
d. derive the general formulas for the latency and area of all adders, in terms of the parameters k and d, in units of the delay and area of a single two-input NAND gate. Assume that the D flip-flop is composed of 6 two-input NAND gates, has a clock-to-output delay of two NAND gate delays, and the setup time equal to one delay of a NAND gate.
e. derive expressions for the following ratios as a function of k and d:
R1. area of a ripple-carry adder / area of a bit-serial adder
R2. latency of a bit-serial adder / latency of a ripple-carry adder
R3. area of a digit-serial adder / area of a bit-serial adder
R4. latency of a bit-serial adder / latency of a digit-serial adder
R5. area of a ripple-carry adder / area of a digit-serial adder
R6. latency of a digit-serial adder / latency of a ripple-carry adder
f. graph functions derived in e. for the following values of parameters k and d:
R1 and R2: k = 4, 8, 16, 32, 64, 128
R3 and R4: k = 128, d=1, 2, 4, 8, 16, 32, 64
R5 and R6: d=4, k=8, 16, 32, 64, 128