Computer Science 150 Homework Assignment 8
Spring 1997 Solutions



(1) Consider the following combinational circuit:   
(a) [10] Using the definitions presented in class, what is the total number of possible (physical) stuck-at-0 (SA0) faults in this network? How many stuck-at-1 faults? 
There are 4 primary inputs, 2 primary outputs, and 3 inputs and outputs for each of the 5 gates.  Thus, there are 4 + 2 + 15 = 21 possible SA0 and 21 possible SA1 faults.

(b) [20] Use fault-folding techniques to eliminate equivalent or implied faults and list all essential faults in the network (use "gateName:inputName" or "gateName:outputName" to refer to specific gate inputs or outputs, and name the input and output pins directly e.g. A2:b, O2:z, I2, X2). 
To find the essential faults, we need to find out which faults are equivalent and which are implied so that we can just for a fewer number of faults, because testing for some faults will also test for those that it implies and those that are equivalent.
For all nodes (inputs and outputs) that are connected by a wire, their faults are equivalent.  The SA0s of AND gates for all its inputs and outputs are equivalent because they are all tested by setting both of its inputs to 1s.  The same is true for SA1s of OR gate inputs and outputs since it's tested by setting both inputs to 0s.
Testing of SA1s of AND gate outputs is implied by testing for any SA1 of it's input, because the output of the AND gates has to be 0 to propogate the fault.  By the same reasoning, SA0s of OR gates is true.
In this circuit, the inputs of the fan-outs are implied by any of the nodes it fans out to (in some cases they may be equivalent).

essential SA0s:
1. O1:a => (O1:z by fan-out <=> X1 by same wire, A1:z <=> A1:a <=> A1:b by SA0s of an AND gate) => I1, I2 by fan-out
2. O1:b => (O1:z by fan-out <=> X1 by same wire), (A2:z by same wire <=> A2:a <=> A2:b by SA0s of an AND gate) => I3 by same wire, I1 by fan-out
3. O2:a => (O1:z by fan-out <=> X2 by same wire, A1:z <=> A1:a <=> A2:b by SA0s of an AND gate) => I1, I2 by fan-out
4. O2:b => (O2:z by SA0 of an OR gate <=> X2 by same wire, A3:z <=> A3:a <=> A3:b by SA0s of an AND gate) => I4 by same wire, I2 by fan-out

Notice that testing for SA0s at an input of an OR gate in this circuit can imply faults all the way to both the primary inputs and outputs beacause SA0 implications can go forward through OR gates (and AND gates) and backwards through AND gates and fan-outs.

essential SA1s:
1. A1:a => A1:z by SA1 of ANDs, I1 by fan-out
2. A1:b => A1:z by SA1 of ANDs, I2 by fan-out
3. A2:a => I1 by fan-out, A2:z by SA1 of ANDs <=> O1:a by same wire <=> O1:b <=> O1:z by SA1 of ORs <=> X1 by same wire <=> A2:z by same wire
4. (I3 <=> A2:b by same wire)  => (A2:z by SA1 of ANDs <=> O1:b by same wire <=> O1:a <=> O1:z by SA1 of ORs <=> X1 by same wire) =>A1:z by fan-out
5. (I4 <=> A3:a by same wire) => (A3:z by SA1 of ANDs <=> O2:b by same wire <=> O2:a <=> O2:z by SA1 of ORs <=> X2 by same wire) => A1:z by fan-out
6. A3:b => I2 by fan-out, (A3:z by SA1 of ANDs <=> O2:b by same wire <=> O2:a <=> O2:z by SA1 of ORs <=> X2 by same wire) => A1:z by fan-out

The SA1 fault implications can go forward through AND gates and OR gates and backward through fan-outs (and OR gates), so testing the inputs of the AND gates were enough to test for all SA1s.

All possible implications and equivalences are stated here and some faults are implied more than once.  Fault folding reduced the number of faults to test for from 42 total possible faults to 10 essential faults that cover all possible single stuck-at faults.

(c) [20] Identify a list of input "cubes" that could be used to test the network for all essential stuck-at faults. 
essential SA0s:
1. O1:a {1,1,0,*} to set O1:a high to excite the fault and O1:b low to propagate the fault
2. O1:b {1,0,1,*} to set O1:b high to excite the fault and O1:a low to propagate the fault
3. O2:a {1,1,*,0} to set O2:a high to excite the fault and O2:b low to propagate the fault
4. O2:b {0,1,*,1} to set O2:b high to excite the fault and O2:a low to propagate the fault

essential SA1s:
1. A1:a {0,1,*,*} to set A1:a low to excite the fault, A1:b high to propagate the fault through A1, and either O1:b low or O2:b low to propagate the fault through O1 or O2
2. A1:b {1,0,0,*} or {1,0,*,0} to set A1:b low to excite the fault, A1:a high to propagate the fault through A1, and either O1:b low or O2:b low to propagate the fault through O1 or O2
3. A2:a {0,*,1,*} to set A2:a low to excite the fault, A2:b high to propagate the fault through A2 and O1:a low to propagate the fault through O1
4. I3 {1,0,0,*} to set I3 low to excite the fault, A2:a high to propagate the fault through A2, and O1:a low to propagate the fault through O1
5. I4 {0,1,*,0} to set I4 low to excite the fault, A3:b high to propagate the fault through A3, and O2:a low to propagate the fault through O2
6. A3:b {*,0,*,1} to set A3:b low to excite the fault, A3:a high to propagate the fault through A3, and O2:a low to propagate the fault through O2

(d) [20] List the minimum set of test vectors (i.e. reduce cubes to specific 1/0 vectors) needed to test the circuit (i.e. manufacturing test, not diagnostic test) for all possible stuck-at faults. 
1. 1100
2. 1001
3. 0111
4. 0110
5. 1011 

(e) [10] Can you find a set of vectors that would be able to identify the specific fault causing a problem (i.e. fault diagnosis) for all stuck-at faults? Explain how you go about it. Which faults can you not identify uniquely? 
No, there is no way to tell the difference between equivalent faults, though it is possible to check for some implied-stuck at faults by using more test vectors to distinguish between the different faults if they don't overlap with other stuck-at faults. 

(2) [20] An asynchronous circuit has two inputs and two outputs. All possible input sequences and the required output sequence are tabulated below: 

Input sequence: 00, 10, 11, 01, 00 
Output sequence: 00, 00, 10, 00, 00 

Input sequence: 00, 01, 11, 10, 00 
Output sequence: 00, 00, 01, 00, 00 

Input sequence: 00, 10, 00, 01, 00 
Output sequence: 00, 00, 00, 00, 00 

Input sequence: 00, 01, 00, 10, 00 
Output sequence: 00, 00, 00, 00, 00 

Derive a minimum-row flow table for the network 

Here's a primitve flow table:
STATE 
NS 
OUT 
00  01  11  10  00  01  11  10 
S1  S1  S2  --  S3  00  00  --  00 
S2  S1  S2  S4  --  00  00  0-  -- 
S3  S1  --  S5  S3  00  --  -0  00 
S4  --  --  S4  S3  --  --  01  0- 
S5  --  S2  S5  --  --  -0  10  -- 

And the merged flow table by combining {S1, S2, S4} and {S3, S5}:
STATE 
NS
OUT
00  01  11  10  00  01  11  10 
S1  S1  S1  S1  S3  00  00  01  00 
S3  S1  S1  S3  S3  00  00  10  00