CSE370 Assignment 5

Distributed: 25 April 2007
Due: 2 May 2007


Reading:

  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)

Exercises:

  1. CLD-II, Chapter 4, problem 4.25 parts a, b.
  2. In the lab’s tutorials you’ve designed a ripple carry adder, which is effective but slow because of the long carry chain. 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, step by step.

a)      Design and test a 1-bit adder that has 3 inputs, A, B, Cin and three outputs: Sum, P, and G. P and G are the propagate and generate functions accordingly, and are defined as: G = AB, P = A XOR B. You may do this either with Verilog or a schematic.

b)      Using your 1-bit adder, design and test a 4-bit adder component which has three input busses, A[3:0], B[3:0], Cin[3:0] and three output busses, Sum[3:0], P[3:0] and G[3:0]. (This 4-bit adder is just four independent copies of the 1-bit adder.) You must use a schematic for this.

c)      Design and test a 4-bit carry look-ahead component that has three inputs, P[3:0], G[3:0], Cin, and three outputs, Cout[3:0], BlockP, and BlockG. BlockP and BlockG are the block propagate and block generate functions. You must use a schematic for this.

d)      Using the 4-bit adder component and 4-bit carry look-ahead components, design and test a 16-bit carry look-ahead adder. You must use a schematic for this.

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

f)        If you continued and made a 64-bit carry look-ahead adder using these components, what would be the size and delay of that circuit?

Turn-in your implementations/console outputs for part c,d and the answers to part e,f.

  1. In this problem you will get to know another type of adder, the carry save adder. This kind of adder is able to simultaneously add 3 numbers, but for speed reasons outputs two results. The sum of the corresponding digits and the resulting carry. Thus a 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.
    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 a 16 Bit carry save adder. 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 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 safe 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 as well a schematic for this. If you need some hints, try to look at this description of carry safe adders.)

Rationale:

  • To practice implementing large functions by decomposition.
  • To understand carry look-ahead adders by implementing one.
  • To learn about carry safe adders.
Comments to: cse370-webmaster@cs.washington.edu