HW3

CS 370 – Spring 2005
Introduction to Digital Design
Instructor: Carl Ebeling

Homework Set 3

DISTRIBUTED: April 14
DUE: April 22, Start of class

Collaboration Policy:
Unless otherwise noted, you may collaborate with other CSE370 students on the homework assignments. Do not look at homework or exam solutions from previous years. You must spend at least 15 minutes working on a problem before seeking assistance. Collaboration means that you may discuss the problems and make notes during the discussion, but you may not look at other student’s work when writing up your homework. Your homework represents your own work—the homework must show that you understand the material and have worked as an individual on every problem. You may not divide up the task of doing the problem sets in the interpretation of collaboration. You may discuss lecture material with anyone.

Late Homework Policy:
The weekly assignments are due at the beginning of class. Assignments handed in during or immediately after class will incur a 10% penalty. We will penalize your assignment 10% per day for each additional day late.

Please show all of your work. Your solutions must be legible…we will not spend time trying to decipher poorly written assignments.

For the following problems, you may print the ROM, PLA and PAL worksheets or the worksheet which has all three on one page or use the ones handed out in class.

1. (15 points) Textbook Problem 3.3 a, b, c; Problem 3.4 a, b, c

2. (15 points) Implement the three functions from problem 1 using a ROM, PLA and PAL. Relabel the variables for the first function to A,B,C,D and implement all three functions first using one ROM, then one PLA and finally one PAL worksheet. Try to minimize the number of AND gates you use in the PLA.

3. (25 points) Implement the following three functions using a ROM, PLA and PAL. Again 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)

Complete the Active-HDL Tutorial #2 , making sure you understand everything that it covers. If you run into problems, send us email or try to find us.

4. (50 points) 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 ...\courses\cse370\05sp\hw3\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 ...\courses\cse370\05sp\hw3\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 ...\courses\cse370\05sp\hw3\compare32_tf.v to test your component. Print your schematic and console output from the simulation.

d) 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?

5. (25 points) Design a circuit that counts the number of leading 0’s in an 8-bit number. For example, 00010100 has 3 leading zeros while 00000100 has 5 leading zeros. You may assume that there is at least one 1 in the number and so there can be at most 7 leading 0’s. Thus this circuit has 8 inputs and 3 outputs.

a) Design a minimal 2-level circuit. Do not try to draw an 8-input K-map!

b) How does the size of the minimal circuit scale with the number of inputs, N?

[Extra Credit] c) Design a circuit that scales better based on breaking the problem into smaller pieces.

You do not have to make an Active-HDL design for this, but your circuit should be easy to read and check for correctness. Your design should be accompanied by an explanation and examples that show how it works.