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)

- 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 64
^{th}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 C_{in} 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 C_{in}[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 C_{in},
and generates three outputs, C_{out}[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 (C_{out}[1], C_{out}[2] and C_{out}[3]) based
on C_{in}, 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 C_{in }and computes the sum and Carry out.
i.e takes P, G and C_{in }Produces S and C_{o. }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 C_{in} of the second FA in the
chain would be fed by the C_{out} of the first. The C_{in} from
the 3^{rd} would be fed by the C_{out} from the second. In
general the C_{in} of the N^{th} FA would be fed by the C_{in}
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. *

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