ECE 362 - Spring 2001. Exam1 - Solutions

Problem 1.

PART 1. There are many solutions to f1. One simple way is to start with a three consecutive 1's and then turn 90 degrees and add two more 1'a and continue this process until you close a loop. The following solution has 12 prime-implicants, all non-essential.

1	1	1	0
1	0	1	1
1	1	1	0
0	1	0	0

PART 2. A Self-dual function has the property that f2(a',b',c',d') = f2'(a,b,c,d). Using this property one can fill in the K-map such that the following pairs of minterms are complementary.
(0,15), (1,14), (2,13), (3,12), (4,11), (5,10), (6,9), (7,8).

A E D' H'

B F C' G'

D H A' E'

C G B' F'

Here is a possible solution that depends on three variables.

0 1 0 1

0 1 0 1

1 0 1 0

1 0 1 0

Problem 2.

List of all prime implicants = b'c, cd, abc', abd, ab'd'
List of essential prime implicants = b'c
Minimal SOP = b'c + abd
Minimal POS = (a + c)(b + c)(b' + d)

Problem 3.

Reed-Muller Canonical Form = XOR (1, a, ab, bc, abc, bcd, abcd)

Problem 4.

Reduced BDD has 7 nodes.

Problem 5.

Essential Multiple-Output Prime Implicants:
f1: None
f2: ac'd, a'd'
Minimal Cost Sum-of-Products
f1 = a'b'c' + ac'd + a'b'cd
f2 = ac'd + a'd' + a'b'cd
Notice that the functions f1 and f2 share the common prime implicants: ac'd and a'b'cd
Circuit has a total of 6 NAND gates.

Problem 6.

Theorem: Product of two complete sums is also complete sum after "multiplying out" and removing every term that is covered by some other term.
So all we need to do is multiply out the Product-of-Sums and remove any covered terms at each stage of multiplication.
f(a,b,c,d)
= (a'+c+d)(a'+b+c)(a+c'+d)(a+b'+c')
= (a'+a'b+a'c+bc+c+a'd+bd+cd)(a+ab+ac'+bc'+c'+ad+b'd+c'd)
= (a'+c+bd)(a+c'+b'd)
= a'c'+a'b'd+ac+b'cd+abd+bc'd

Problem 7.

Unchecked rows are: (0): [0,0,0,0], (7,15):[ -,1,1,1], (9,11,13,15): [1, -, -, 1], (10,11,14,15): [1, -. 1, -]
Prime Implicants are: a'b'c'd', bcd, ad, ac

Problem 8.

Minimal cost OR-AND expression = (b + c)(c' + d)(b + d)
Last term (b + d) is required to prevent Static-0 logic hazards. There are no Static-1 hazards in a two-level OR-AND circuit since no terms of the type (x + x') can exist.

Problem 9.

There is no need for any Boolean Algebraic equations. Simply put the needed logic values on the fault-site and the needed values for Path Sensitization. After that, back-trace the circuit and assign values as needed to satisfy already labeled values.
Fault Excitation of line D stuck-at 0 requires that we put logic 1 on that line. Backtracing that logic value will force you to assign A3=0 and B3=0. "Forcing" a value means there are no choices.
Next, path sensitization requires that all other inputs of the large NOR gate should be set to logic 0. Backward tracing of these 0 values can be done with many choices on the inputs. One of the simplest choice that generates all these 0's is; A2=1 and B2=1.
So the test vector is: A3=0, B3=0, A2=1, B2=1 and all others Don't Care. Of course, there are many other test vectors as well.

Problem 10(a)

A systematic method of proof is: first learn some simple facts from the Given facts. Then take one side of the equation LHS = RHS and transform that side using the learned facts such that it is equal to the other side. (LHS stands for Left Hand Side and RHS for Right Hand Side)
In our case, given facts are: x + y = z, and x'y = 0. We can learn from x'y = 0 by taking the complement: x + y' = 1.
The equation that needs to proven is:   x = y + z Here the LHS = x and the RHS = y + z
Proof:
RHS
= y + z
= y + (x + y)          {substitute x+y for z from the given fact, idea here is to get rid of z and then y}
= x + y                  {using simple Boolean properties}
= (x + y)1              {ANDing with 1 }
= (x + y)(x + y')     {substitute x+y' for 1 from the derived fact}
= x + xy' + xy
= x
= LHS                 Q.E.D.
Alternately, you can learn lots of random facts and play with those facts to obtain the desired equation. For example:
Facts: x+y = z, x'y = 0, x+y' = 1
(x+y)1 = z
(x+y)(x+y') = z
x = z this is a new fact!
Switch x and z in the given fact x + y = z and we get yet another fact: z + y = x. Bingo! That is what we were looking for.

Problem 10(b)

Given facts: x + y = z, and xy = 0. Derived facts: x'y' = z', and x' + y' =1
Need to prove LHS = RHS: namely: x = yz' + y'z
RHS
= yz' + y'z
= y(x + y)' + y'(x + y)   {substitute x+y for z from the given fact, idea here is to get rid of z and then y}
= yx'y' + xy' + yy'
= xy'
= xy' + 0
= xy' + xy             {substitute xy for 0}
= x
= LHS                Q.E.D.

Alternately, learn lots of facts.
x + y = z, so x'y' = z', AND both sides with y, then y(x'y') = yz', so 0 = yz'. That is an useful fact since now all we need to prove is that x = y'z.
x + y = z, AND both sides with y', we get y'(x + y) = y'z, that give us xy' = y'z.
xy' = y'z can be rewritten as xy' + 0 = y'z, and from the known fact 0 = xy we can rewrite this is xy' + xy = y'z, which simplifies to x = y'z.
The two facts: yz' = 0 and x = y'z gives us the desired relation namely: x = yz' + y'z.

Clearly in both of the above cases, the systematic transformation of LHS or RHS into the other side is cleaner than using random facts.