CSE370 Assignment 4

Distributed: 26 January 2005
Due: 1 February 2005


Reading:
  1. Katz/Borriello, Contemporary Logic Design 2e, Sections 3.3 through 3.6 (pp. 114-147)
  2. Katz/Borriello, Contemporary Logic Design 2e, Chapter 4, up through Section 4.2.1 (pp. 155-168)

Exercises:

  1. CLD-II, Chapter 3, problem 3.8, parts a and c.
  2. CLD-II, Chapter 3, problem 3.17, all parts.
  3. CLD-II, Chapter 3, problem 3.22, all parts.
  4. CLD-II, Chapter 4, problem 4.2 part b
  5. CLD-II, Chapter 4, problem 4.7 part b
  6. CLD-II, Chapter 4, problem 4.10
  7. CLD-II, Chapter 4, problem 4.14
  8. For the following problems, you may print the ROM, PLA and PAL worksheets or the worksheet which has all three on one page. Implement the following three functions using a ROM, PLA and PAL. For the PLA, try to minimize the number of AND gates you use.

    f1(a,b,c,d) = ∑ m(8, 4, 12, 14, 13) + d(10, 6)

    f2(a,b,c,d) = ∑ m(10, 12, 14) + d(6)

    f3(a,b,c,d) = ∑ m(10, 4, 11, 13, 15) + d(9, 7)

  9. (NOTE: REQUIRES ACTIVE-HDL) In this problem we are going to design a comparator that compares two 32-bit numbers. This is a function with 64 inputs - the truth table for this function would be truly enormous! We are going to use a "divide-and-conquer" approach. We will first solve a small version of the problem and then use this solution to solve a larger version. We can repeat this process to solve very large problems.  (Link to test fixtures)

    a) Extrapolate from what you know about small comparators to estimate the number of gates it would take to implement a 32-bit comparator.

    b) First design a 2-bit comparator:  This comparator compares two 2-bit numbers, A and B, on the input and produces two outputs, A=B and A<B.  (A and B are unsigned numbers throughout this exercise.)  Find the minimal 2-level circuit implementation for these two functions.  Make a component for this comparator using Active-HDL.  Use the text fixture compare2_tf.v to test your component.  Print your schematic and console output from the simulation.

    c) Now design an 8-bit comparator using four of your 2-bit comparators.  Use the test fixture compare8_tf.v to test your component.  Print your schematic and console output from the simulation.

    d) Now design a 32-bit comparator using four of your 8-bit comparators.  (Don't despair!  How can you use the circuit you just designed?  Feel free to cut and paste circuits between schematics, changing what you need to change.) Use the test fixture compare32_tf.v to test your component.  Print your schematic and console output from the simulation.

    e) Calculate the worst-case delay of your 32-bit comparator.  Don't look at the simulator waveforms!  Explain why not.  What would be the size and delay of a 512-bit comparator?

Rationale:

Comments to: cse370-webmaster@cs.washington.edu