Dept. of Electrical Engineering and Computer Sciences
David E. Culler
Homework 1: Due Friday 9/7 @ 2 pm in box near 125 Cory
1. Katz and Boriello problems: 1.1, 1.2, 1.3, 1.4 1.18, 1.19, 1.20,
2. Katz and Boriello problems: 2.2, 2.4 (but only using NAND gates).
3. Draw a gate-level schematic for the following logical expression using the two obvious logic gates: NOR( NAND(A,B),C).
· How many transistors are used when this is implemented as a CMOS NAND and NOR gate?
· Draw a CMOS transistor level circuit that combines these two and reduces the number of transistors required.
4. The theorems of Boolean Algebra all have a graphical analog in gate level schematics. Here’s a couple of examples
We can state the theorems in terms of local graph transformations. The theorem says that you can replace the thing you see on one side with the thing on the other and the meaning is the same.
Draw the graphical version of the Associative Law, Distributive Law, and Simplification (K&B 2.2.2).
Now we can optimize circuits (which is really theorem proving) by pushing bubbles around, transforming gates, a rewriting parts of the graph. Give a “bubble pushing proof” of the validity of the following circuit optimization from the canonical Sum of Products form to NAND gates.
State the corresponding rule for Product of Sums form.