Date: Mon, 02 Dec 1996 15:11:05 GMT
Server: NCSA/1.4.2
Content-type: text/html
CSE567 Homework Assignment #1
CSE 567: Principles of Digital Systems Design
Carl Ebeling, Fall 1996
Homework 1
Distributed: Monday Oct. 7 - Due Friday Oct. 11, in class
- Prove the following simplification theorems using only axioms and
theorems T1-6 and T9-10 from the notes:
a. (A+B)(A+B') = A
b. (A+B)(A'+B) = AB+A'B
- Use DeMorgan's law to complement:
ABC+B(C'+D')
- Simplify the following using the theorems of Boolean algebra:
f(X,Y,Z) = (X+Y)(X'+Y+Z)(X'+Y+Z')
- Rewrite the following in Product of Sums form, not necessarily
minimized:
f(A,B,C,D) = AB + CD + AC' + A'D
- Implement the logic function
f(A,B,C,D,E) = ABCDE
using 2-input NAND gates only. Try to minimize worst-case delay.
What is the worst-case delay of your circuit assuming each NAND gate
has a delay of 2 ns?
- Find a three-variable function that is its own dual. (This
highlights the fact that duality and complementation are very
different.)
- A 2-bit comparator compares two 2-bit numbers A and B and
generates two results, A>B and A=B.
a. Implement a 2-bit comparator.
b. Use the 2-bit comparator that you designed in part (a) to construct
at 4-bit comparator.
c. Extend the method you used for part (b) to describe how to
implement an n-bit comparator for arbitrary n. Assuming that each
logic gate has a delay of 1 (unit-delay model), what is the delay of
your n-bit comparator as a function of n?
d. (Extra credit) If your answer for part (c) was not O(logn) then
find a solution that is.
- Consider a three-out-of-five majority gate called M5, whose
output is 1 if at least three of its five inputs are 1.
a. Show how to implement a 2-input AND gate using M5 with the inputs
connected appropriately.
b. Show how to impement a 3-input OR gate using M5.
c. Can you use M5 to implement an inverter?
ebeling@cs.washington.edu