Required reading (material covered at the last lecture)

Written Assignment 3

due Monday, February 26, 2007, 7:20 PM

Problem 10 (6 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. draw 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

Problem 11 (4 points) (based on Parhami, Chapter 5, Problem 5.14, Design of fast counters)

Design in detail on paper the fast three-stage up counter shown conceptually in Parhami Fig. 5.12, including the control circuits 1 and 2. Assume the use of ripple-carry incrementers based on half-adders.

Draw a schematic of this adder composed of medium level components (such as full adders, half adders, multiplexers, registers, etc.), and the detailed schematic of each medium-level combinational component implemented using only two-input, three-input, and four-input NAND gates.

Determine optimal lengths for the three counter segments that minimize the clock period of the counter in each of the following three cases:

a. An overall counter length of 16 bits
b. An overall counter length of 256 bits.

Derive the formula for the minimum clock period and the area of the counter.

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. 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.

Specify clearly any additional assumptions you have used.