CSE370 Assignment 3

Distributed: 11 October 2000 Due: 16 October 2000

1. Katz, Chapter 2 revised - handout.
2. (Optional) Katz, Chapter 2 (pp. 40-85 and 92-102).
3. (Optional) Katz, Chapter 3 (pp. 110-122).

Exercises:

1. Given f = (a + b' + c')(a' + c')(a + c + d)(a + b + c + d')

2. (a) Express f in canonical product-of-sums form (use M notation).
(b) Express f in canonical sum-of-products form (use m notation).
(c) Express f' in canonical product-of-sums form (use M notation).
(d) Express f' in canonical sum-of-products form (use m notation).
3. Using Boolean algebra, determine a minimized expression of the following functions (make sure to list which don't cares you use to do your minimization and which you do not):

4. (a) F(A,B,C,D) = Sm(1,2,11,13,14,15) + d(0,3,6,10) minimized as a sum-of-products expression.
(b) G(A,B,C,D) = PM(2,5,6,8,9,10) * D(4,11,12) minimized as a product-of-sums expression.
(c) F', the complement of the function in part (a) minimized as a sum-of-products expression.
5. A cable has four wires (A, B, C, D) placed in the order given. Each of the wires can carry a 1 or a 0. Write a logic function F(A, B, C, D) whose output is 1 if and only if a single pair of adjacent wires are both 0. Consider D to be adjacent to both C and A for symmetry.

6. (a) Express the function as a minterm expansion.
(b) Do the same for ANY adjacent pair of wires are both 0.
7. A combinational logic block has three inputs (A0, A1, A2) and two outputs (Y1, Y0). The output variables represent a binary number where Y1 is the most significant bit. The binary number Y1 Y0 corresponds to the highest index of the inputs that are set to 1. For example, if A0=1, A1=0, and A2=1, then Y1 and Y0 should represent the index 2 (Y1=1, Y0=0); if A0=1, A1=1, and A2=0, then Y1=0 and Y0=1 because the highest index for an input that is true is 1. Note that you can assume at least one wire will be set to 1 at all times. Express the two functions for Y1 and Y0 in canonical sum-of-products form.
8. Draw a schematic diagram for (A' + B' + C')(A' + B')(A' + C'), mapped into a NAND-only network (turn in a DesignWorks schematic).
9. Draw a schematic diagram for (A + B)(B'+C)(A'+C'), mapped into a NOR-only network (turn in a DesignWorks schematic).
10. Reverse engineer the circuit shown in the schematic below in order to derive a two-level realization.

11. (a) Find the Boolean expression that describes the circuit.
(b) Construct the truth table for the function.
(c) Write the function in canonical sum-of-products form (little m notation).
(d) Simplify the function above using the axioms/theorems of Boolean algebra (show each step).
(e) Draw schematic diagrams for the original (diagram above), canonical (part (c)) and minimized (part (d)) forms of Z in DesignWorks, connect all their respective inputs to the same set of switches, and verify that they have the exact same behavior for all combinations of inputs.
(f) [Extra credit] Construct a small circuit whose output is true if all three outputs for part (f) are identical.  This can be used in verification.  If its output is true for all input combinations then the three circuits are identical.  Turn in the DesignWorks schematic showing all three circuits and your "verifier".

Rationale:

• To practice and gain facility with two-level canonical forms.
• To practice basic combinational logic design.

Comments to: cse370-webmaster@cs.washington.edu (Last Update: 10/12/00 )