Path Sensitization
Path Sensitization
Path Sensitization
Pseudo-Exhaustive Method
Partition large circuit into fanin cones
Backtrace from each PO to PIs influencing it
Test fanin cones in parallel
Reduced #of tests from 2
8
= 256 to 2
5
x 2 = 64
Incomplete fault coverage
Pseudo-Exhaustive Pattern Generation
Random-Pattern Generation
Random-Pattern Generation
Flow chart for
method
Use to get
tests for 60-
80% of faults,
then switch to
deterministic
ATPG for rest
Random Pattern Testing
Bottom:
Random-
Pattern
Resistant
circuit
Path Sensitization Method
Path Sensitization Method
1 Fault Sensitization (activation)
2 Fault Propagation
3 Line J ustification
Path Sensitization Method
Fault l s-a-v
Activation
set l to v
Propagation
find a path from l to a primary output that keeps
faulty value
J ustification
set the primary inputs to activate the fault
Composite Logic Values
consider line value for original AND faulty
circuit
v/v
f
= original/faulty
Symbols D and D (Roth, 1966)
D = 1/0
D = 0/1
0 = 0/0
1 = 1/1
Operations on Composite Values
D + 0 = 0/1 + 0/0 = 0/1 = D
V/V
f
0/0 0
1/1 1
1/0 D
0/1 D
AND 0 1 D D X
0 0 0 0 0 0
1 0 1 D D X
D 0 D D 0 X
D 0 D 0 D X
X 0 X X X x
Path Sensitization Method
Path Sensitization Method
1
Propagation
D
Path Sensitization Method
Path Sensitization Method
Propagation: try path f h k L
1
D
D
D
D
0
1
1
Path Sensitization Method
Path Sensitization Method
Propagation: try path f h k L
1
D
D
D
D
0
1
1
Path Sensitization Method
Path Sensitization Method
J ustification: Try path f h k L blocked
at j, since there is no way to justify the 1 on i
1
0
D
D
1
1
1
D
D
D
Path Sensitization Method
Path Sensitization Method
J ustification: Try path f h k L blocked
at j, since there is no way to justify the 1 on i
1
D
D
D
1
1
D
D
1
1
1
Path Sensitization Method
Path Sensitization Method
Backtracking!
1
D
D
D
1
1
D
D
1
1
1
X
X
X
X
X
X
X
X
Try other propagation: path g i j k L
0
D
D
D
1
D
D
1
1
Path Sensitization Method
D
Try other propagation: path g i j k L
0
D
D
D
1
D
D
1
1
Path Sensitization Method
D
Try other propagation: path g i j k L
0
D
D
D
1
D
D
1
0
1
Path Sensitization Method
D
Major Combinational Automatic
Test-Pattern Generation Algorithms
D-Algorithm (Roth) -- 1966
PODEM (Goel) -- 1981
FAN (Fujiwara and Shimono) --1983
Sequential Circuit ATPG
Time-Frame Expansion
Problem of sequential circuit ATPG
Time-frame expansion
Example of Sequential Circuit
CB
MB
Sequential Circuits
A sequential circuit has memory in addition to
combinational logic.
Test for a fault in a sequential circuit is a
sequence of vectors, which
Initializes the circuit to a known state
Activates the fault, and
Propagates the fault effect to a primary output
Methods of sequential circuit ATPG
Time-frame expansion methods
Simulation-based methods
Extended D-Algorithm
1. Pick up a target fault f.
2. Create a copy of a combinational logic, set it
time-frame 0.
3. Generate a test for f using D-algorithm for time-
frame 0.
4. When the fault effect is propagate to the DFFs,
continue fault propagation in the next time-frame.
5. When there are values required in the DFFs,
continue the justification in the previous time-frame.
Example for Extended D- Algorithm
st_1
Example: Step 1
Example: Step 2
Example: Step 3
Summary
Summary
Hierarchical ATPG -- 9 Times speedup (Min)
Handles adders, comparators, MUXes
Advances over D-algorithm
Results of 40 years research mature methods:
Path sensitization
Simulation-based
Boolean satisfiability and neural networks
Genetic algorithms