CSE370 Assignment 5
Distributed: 6 Feb 2008
Due: 12 Feb 2008
- Katz/Borriello, Contemporary Logic Design 2e, remainder of Chapter 4 (up to p. 213)
- Katz/Borriello, Contemporary Logic Design 2e, Chapter 5.6 (pp. 238-245)
ADDERS
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.
- In the lab’s tutorials you’ve designed a ripple carry adder. As the carry of this adder ripples through, each stage has to wait for the carry from the previous stage. This makes it very slow for higher order adders. To gain appreciation for the problem, consider a 64-bit adder. The full-adder computing the sum of the 64th bit needs to wait 63 full-adder delays for its carry input to arrive. Clearly this is not optimal. In class you’ve learned about the carry look-ahead adder, which addresses this problem by computing the carry-in for later gates in parallel with the sums. In this problem you will construct a 16-bit carry look-ahead adder (CLA), step by step. You will then consider the implications of extending this concept to 64 bits.
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[1], Cout[2] and Cout[3]) 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.
- In this problem you will consider, the carry save adder. This kind of adder is able to simultaneously add 3 numbers. In the first stage it outputs two results: The sum of the corresponding digits and the resulting carry. Thus the first stage of an n-bit carry save adder consists of n full-adders. To get your final result, you have to add the sum and the carrys together with a conventional adder. This link gives an intuitive feel for how this works. (Description of carry save adders.) You will create a component that can add 8 16-Bit numbers together (assuming that no overflows will occur). Since you might be busy enough with getting your CLA to work, we do this on pen and paper, just thinking about what you would implement.
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.
- 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.
Rationale:
- To understand carry look-ahead adders by implementing one.
- To learn about carry save adders.
- To think about new adder architectures and consider their implementation and performance issues.