Problem 1. Do Exercises B-11 and B-12 on page B-79 of the text (on the CD).

Problem 2. Below is the truth table for a boolean function x with inputs a, b, c, d. Find a minimum Sum of Products boolean expression for x. Convert this expression to a Product of Sums using DeMorgan's Laws.

Problem 3. There are 16 possible two input one output boolean functions. Of these, we showed in class that the NAND function forms a basis for all boolean functions, i.e., all boolean functions can be expressed just using gates computing the NAND function. We also argued that AND and OR are not universal by themselves (without the NOT function). Which of the other 16 two input one output boolean functions are universal besides the NAND function? (Show their truth table if you don't know their name.) For each one, prove that it is universal.

Problem 4. You need to build a 6 input-64 output decoder. You go to the store where they are selling AND, OR, and NOT gates for $1 each, 2 input-4 output decoders for $2 each and 3 input-8 output decoders for $4 each. Find the cheapest way to construct your 6 input-64 output decoder from these components.

Problem 5. There are many ways of constructing a 32-bit carry select adder. For example one could construct it out of three 16 stage ripple carry adders where the 16 higher order bits are computed for both carry-in equal to 1 and carry-in equal to 0. This will have delay 32 for the ripple carry adders plus delay 2 to select the correct set of higher order bits for a total depth of 34 (basically half that of a standard 32-bit ripple carry adder). Find a minimum delay 32-bit carry select adder using multiple ripple carry adders of varying size. About how many gates are in your solution and how does it compare to a straightforward 32 stage ripple carry adder?

Report problems to dkrizanc at wesleyan dot edu