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


  1. 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
    
  2. Use DeMorgan's law to complement:
    ABC+B(C'+D')
    
  3. Simplify the following using the theorems of Boolean algebra:
    f(X,Y,Z) = (X+Y)(X'+Y+Z)(X'+Y+Z')
    
  4. Rewrite the following in Product of Sums form, not necessarily minimized:
    f(A,B,C,D) = AB + CD + AC' + A'D
    
  5. 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?

  6. Find a three-variable function that is its own dual. (This highlights the fact that duality and complementation are very different.)

  7. 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.

  8. 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