Computer Science 150 Homework Assignment 9 Solutions
Spring 1997

Due: Thursday, May 1st, 5:00 pm


(1) Consider the following four-inputcircuit:


(i) How many conventional stuck-at-0 and stuck-at-1faults are there in this circuit?[10]

14 stuck-at-0s and 14 stuck-at-1s
(ii) How many essential faults are therein the circuit after fault implication and fault equivalences are considered?List all of them by name.[20]

1. SA0:A <=> SA0:G1.p
2. SA1:A <=> SA1:G1.p
3. SA0:B <=> SA0:G1.q
4. SA1:B <=> SA1:G1.q
5. SA0:C <=> SA0:G2.p
6. SA1:C <=> SA1:G2.p
7. SA0:D <=> SA0:G2.q
8. SA1:D <=> SA1:G2.q
9. SA0:G1.r <=> SA0:G3.p
10. SA1:G1.r <=> SA1:G3.p
11. SA0:G2.r <=> SA0:G3.q
12. SA1:G2.r <=> SA1:G3.q
13. SA0:G3.r <=> SA0:Z
14. SA1:G3.r <=> SA1:Z

(iii) List the minimum set of test patternsneeded to test for all essential single stuck-at-1 and stuck-at-0 faultsin the network.[10]

Here is one set of test of patterns (given as ABCD):
0000 (satisfies essential faults 2,4,6,8,10,12,14 listed in part ii)
1111 (satisfies 1,3,5,7,10,12,14)
0101 (satisfies 2,3,6,7,9,11,14)
0001 (satisfies 2,4,6,7,10,11,13)

(iv) What patterns would you apply to determinespecifically that the particular stuck-at fault was actually the outputG2.r stuck-at-1 (or the input G3.q stuck-at-1)? (i.e. fault diagnosis)[10]

(test patterns are in the form ABCD) 1. 0000 will show a SA1 at any node in the network
2. 1111 will check for a SA1 at G1.r, G2.r, and G3.r
3. 0001 will identify SA1:G1.r
4. 0101 will detect SA1:G3.r
If tests 1 and 2 show a fault and tests 3 and 4 don't show faults, there's a SA1 fault at G2.r or G3.q

(2) (i) Find a hazard-free implementationof the following function using only 3-input nor gates. Use the minimumnumber of gates+gate inputs and assume complements are available. [20]

f(A,B,C,D) = Sum-of-Minterms(0,2,6,7,8,10,13)


(ii) Explain how a hazard in the next-state logic of a Mealy clocked synchronous machine can affect the performance of the machine adversely. Consider all cases and recommend ways of avoiding such adverse outcomes (other than simply eliminating the hazard by adding additional gates!)[15]

If an input to the combinational logic changes near the clock edges, then we may get a glitch at the clock edge => setup/hold time violation. Therefore, we must ensure that the clock is slow enough so that the feedack loop (which contain the state bits) does not cause the above to occur. Also, we must ensure that none of the primary inputs change near the clock edge. One way to do this is to synchronize the inputs by putting flip-flops between the primary inputs and combinational next-state logic.
(iii) What are the adverse effects which might result when one eliminates the hazard by adding additional gates?[15]

1. Added area / gates / cost
2. Possbibly more delay due to added fanout
3. Possibly creates dynamic stuck-at-faults
4. More load capacitance => More delay, power consumption