CSE370 Assignment 3 Sample Solutions

1. Consider the following three-input logic function f(X,Y,Z) = (X+Y)(X'+Y'+Z)(X+Y'+Z')(Y+Z')

a) Convert the function into S-O-P form using DML. [5 pts]

	The first step is to invert the function:
                         
					f' = (x+y'+z)(x'+y+z)(x'+y'+z')


	Then, using DeMorgan's, we find the SOP form:

	
					f = x'yz' + xy'z' + xyz

b) Find both the minimal S-O-P and P-O-S form of this function. [SoP: 2 pts; PoS: 3 pts]

	S-O-P:  f = x'yz' + xy'z' + xyz (no simplification)

	
	P-O-S:  f = (x+y)(y+z')(x+z')(x'+y'+z)


	Clock here for the K-Maps

c) Using DesignWorks implement the above function in the form you obtained in (a) and in the minimal P-O-S form. Generate two timing diagrams, one for each form, for all input (X,Y,Z) transitions when exactly two inputs are changed quazi-simultaneously. Assume that all gates have zero delay. [schematics: 5 pts; test vector+timing: 5 pts]

	Here is the circuit and the test vector for DesignWorks.
	The pairs of lines with delay 1 between them simulate the 
	"quasi-simultaneous" change of two inputs.

2) Consider the problem 2.18 (a-f) from Katz (page 106)

a) Find the minimal S-O-P form for the inverted function [2.18a: 2 pts; 2.18b-f each: 3 pts]

	
	a) Minimized f' = X'Y' + XY

	b) Minimized f' =  x'z+  yz 
						
	c) Minimized f' =  vw'y + vwy'z + v'w'y'z' 

	d) Minimized f' = a + d

	e) Minimized f' = AB' + C

	f) Minimized f' = A'D + A'E + BE' + BD + AB'D'

b) Implement all resulting minimal forms using NAND gates with invertible inputs. [6*2 pts]

	Click here for K-maps  and implementations of the above functions

3) Create a four-input function that has at least 3 different minimal P-O-S forms. [10 pts]

	Click here for a sample solution

4) Consider a 4-input 4-output function that outputs the succeeding number of a 4-bit Gray code.

        
        Click here for the K-maps and implementations

a)Find a minimal S-O-P form of each of the outputs using Karnaugh-maps. [4*3 pts]

	1 = MSB -> 4 = LSB
	F(1) = AD + AC + BC'D'
	F(2) = BC' + BD + A'CD'
               F(3) = A'B'D + ABD + CD'
	F(4) = A'B'C' + ABC' + A'BC + AB'C

b) Can you reduce the number of gates on any of the four functions if XOR gates are allowed in the implementation? [4*2 pts]

	An XOR Gate can be used in the fourth function to further simplify it to
	F(4) = (a XOR (B XOR C))
	The third function can be simplified, but gates are not reduced.

c)For each function (output) replace at most one TRUE output with a FALSE output to achieve maximal reduction of the number of used gates (AND,OR,NOT) in the minimal S-O-P form. [4*2 pts]

	Bit shown on K-Maps.  Here are minimal functions
	F(1) = AD + AC + AB
	F(2) = BC' + BD + A'B
	F(3) = A'B'D + ABD + CD' (same)
	F(4) = A'B'C' + ABC' + A'BC + AB'C (same)

5) Consider the four output functions from the previous problem. Assume that the output for inputs (3,7,9,12) is "don't care".

a) Find the minimal P-O-S form of each output using Karnaugh maps. [4*2 pts]

		
	1 = MSB -> 4 = LSB
	F(1) = (A+D')(A+C')(B+C)
	F(2) = (B + C)(A'+ B)(A'+ D)
	F(3) = (C + D)(A'+B+ D')(A + B'+ C)
	F(4) = (A'+B'+ C')(A + B + C')(A'+ B + C)(A + B'+ C)

b) Implement each output using NOR gates with invertible inputs. [4*3 pts]

c) Denote the prime implicants of each function. [4*1 pts]

	Click here for the K-maps and implementations...