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
|