## CSE370 Assignment 5

### Distributed: 6 Feb 2008 Due: 12 Feb 2008

1. Katz/Borriello, Contemporary Logic Design 2e, remainder of Chapter 4 (up to p. 213)
2. Katz/Borriello, Contemporary Logic Design 2e, Chapter 5.6 (pp. 238-245)

#### This assignment deals with several implementations and some students might take significantly longer to complete this than the previous assignments. Students are encouraged to start working on this early. Note that if you wait until the week this assignment is due to start it you will not get things done on time.

a)      Design and test a 1-bit CLA building block that takes 3 inputs, A, B and Cin and gives three outputs: Sum, P, and G. Sum is the usual full adder sum bit. P and G are the propagate and generate functions. They are defined as:  G = AB, P = A XOR B. You may do this either with Verilog or a schematic. However you need a schematic for submission. Name this block add1.

b)      Using the 1-bit block you just created, design and test a block which performs the above operation on 4 bit buses. Hence it has three input busses, A[3:0], B[3:0] and Cin[3:0] and generates three outputs (busses), Sum[3:0], P[3:0] and G[3:0]. (This 4-bit block is just four independent copies of the 1-bit block you created.) You must use a schematic for this. Name it add4.

c)      Design and test a 4-bit carry look-ahead component that has three inputs, P[3:0], G[3:0] and Cin, and  generates three outputs, Cout[3:0], BlockP, and BlockG. BlockP and BlockG are the block-propagate and block generate functions. Note that there is only a single carry_in bit, but your block generates 4 carry bits at the output. You must predict higher order carries (Cout, Cout and Cout) based on Cin, P and G inputs. Your lecture notes for the adder might be a good way to recall how to do this. Use a schematic for this. Name it cla4.

d)     Using the building blocks of part b (add4) and part c(cla4), design and test a 16-bit carry look-ahead adder. You must use a schematic for this. Name this cla16.

e)      What is the size (# of gates) and delay (just the total # gates on the longest path) of your 16-bit carry look-ahead adder?

f)       Could you use cla16’s and cla4’s to make a 64-bit adder? If you made a 64-bit carry look-ahead adder using these components, what would be the size and delay of that circuit?

Turn-in screenshots of your schematic for parts a,b c,d and the answers to part e,f.

a)      First describe how you would design the first stage of a 16 Bit carry save adder (CSA_1st). That means a component with the inputs A[15:0], B[15:0], C[15:0] and the outputs Sum[15:0], Carry[15:0]. (Either draw a schematic, or give a verbal description.)

b)      To help you understand how your CSA works, describe how you’d build a component that adds three 16-Bit inputs A, B, C and produces the overall sum S. You have to use one CSA_1st and as well a conventional 16-Bit CLA. (Remember that we don’t care about overflows!). Draw a schematic for this.

c)      Now come up with a design that can add 8 16-Bit numbers together, using carry save addition. You may use as many CSAs as you like, but only 1 CLA. The only restriction is that your design (which will most likely have a tree-like structure) has at most 5 levels, from the inputs to the outputs. Draw a schematic for this.

1. Let us now think about how you would come up with your own architecture to add more efficiently based on some idea. (With a little help along the way!)

a)      Strip down the add1 block made for the CLA into a block that just creates Propagate and Generate signals. i.e. it takes inputs A and B and generates outputs P & G. Call this block makepg.

b)      Also strip down add4 block into a block that creates just 4 propagates and generates i.e. it takes inputs A[3:0] and B[3:0] and generates P[3:0] and G[3:0]. Call this block make4pg.

c)      Create a block FA that takes inputs P, G and Cin and computes the sum and Carry out. i.e takes P, G and Cin Produces S and Co. Think about how sum and carry are related to P and G.

d)     Excellent! Now consider this: 16 bit adder by chaining together the FA’s you just made. i.e the Cin of the second FA in the chain would be fed by the Cout of the first. The Cin from the 3rd would be fed by the Cout from the second. In general the Cin of the Nth FA would be fed by the Cin of the (N-1)th FA. This is shown in the top half of the figure below. This concept is the same as a ripple carry. Instead, consider the architecture shown in the bottom half. a)      Use the idea shown in the bottom half of the above picture to speed up the process of addition. Create a 16-bit adder that exploits the above idea. You will need your make4pg blocks to create the P’s and G’s , a 2:1 multiplexer, and gates to generate the select input of the multiplexer and the FA block to get the sums and Carry bits. Explain how this adder speeds up the process of addition.

b)      What is the worst case delay through this adder? (i.e Identify the critical path and list the gates that are on the path. )

c)      What input sequences triggers this worst delay?

Turn-in screenshots of your schematic for parts a,b c,e and the answers to parts f,g.