ECE 741: Sequential Machines

Homework #4 - Spring 2003Assignment

Solve the following problems, showing all your work for full credit. Your assignment must demonstrate individual work. No copying of assignments is allowed.

1. You are given a netlist below with gates numbered for convenience.
   1. Draw the connectivity graph with edge weights and nodes labeled as on the figure.
   2. Find the connectivity matrix C.
   3. Assuming the 2-way partition A={1,2,3,4,5} B={6,7,8,9,10}, find the cost T for this partition.
   4. Using the node weights given below, find the total sizes of partitions A and B. Assuming a maximum partition size of P = 48, is this partition admissible?
   5. Now, swap node 2 with nodes 7 & 8 (A={1,3,4,5,7,8} B={2,6,9,10}). Find the gain g for this swap. Show your work.
   6. Is the new partition admissible? Show your work.
   7. Find a new partition that has a lower cost than both of the previous partitions that is admissible with P = 45. Show your work.
   
   

   Gate	Weight (Size)
   AND	5
   OR	5
   XOR	8
   MUX	7
   Flip-Flop	19

   
2. Apply the Forward-Propogation algorithm to find the delays in the following graph. Assume that inputs a, b, and c arrive at time 0, while input d arrives at time 0.1.
   1. Draw the delay graph.
   2. Find the maximum delay at each node
   3. Find the critical path.
   
   
3. Find all the false paths for the netlist below according to the static sensitization condition.
   1. For each true path, provide a vector that statically sensitizes the path.
   2. For each flase path, show that no vector exists to statically sensitize the path.
   
   

Submission

You should turn in your completed assignment on paper in class on the specified due date.