# Homework 4

Distributed Wednesday, October 17, 2007
Due before 10:30, Friday, October 26, 2007

Always remember to staple your work, if it is multiple pieces of paper.

If you choose, indicate on the top of your assignment roughly how much time you spent on it. This information will have no impact on your grade; it will only be used by an inexperienced course staff to gauge the volume of work to assign.

1. (25 points) Consider the following three functions. Use this template for these exercises.
• F(A,B,C,D) = Σm(2,4,5,6,8,12) + Σd(7,10,14)
• G(A,B,C,D) = Σm(0,4,5) + Σd(6,12)
• H(A,B,C,D) = Σm(0,4,6,7,8) + Σd(10,12,14)

1. Implement F, G and H on the PLA. Use as few product terms (AND gates) as you can. The number of inputs that each product term uses does not matter. (This is different from normal 2-level optimization where we care about both the number of gates and the number of inputs.) This PLA does not have optional output inverters, so you must implement the "true" versions of the functions. Remember that when you are designing for PLAs, the main thing you want to optimize is sharing of terms between functions, not the size of the rectangles in the K-maps.
2. Implement as many of F, G and H as you can on the 2-product-term-per-OR-gate PAL. Some of them may not fit, and in that case, you should just explain why the function does not fit. The number of product terms you use on the PAL does not matter, because the structure of this PAL does not allow for sharing product terms.
For both a and b, use the same PLA/PAL for all your implementations.
2. (20 points) Exercise 2.37 (a,c,e) from the textbook.
3. (55 points) Complete the Quine-McCluskey algorithm programming exercise described here.