K.T.
Tim Cheng
06_seq_tg, v1.0
Outline Test Pattern Generation for
Sequential Ckts
Time-frame expansion & Extended D-Algorithm
Nine-valued test generation
Potential detection
Issues of sequential ATPG
Test sequence compaction
K.T. Tim Cheng
06_seq_tg, v1.0
Sequential Test Generation: Taxonomy
sequential
synchronous
(or almost synchronous)
state
transition
level
RTL/
gate
level
asynchronous
simulation
based
approach
gate
level
known
initial
state
unknown
initial
state
simulation
based
approach
K.T. Tim Cheng
time-frame
expansion
based approach
06_seq_tg, v1.0
Test Generation Using
Time-Frame-Expansion Model
Extended D Algorithm
Select a target fault f
Create a copy of a combinational logic, set it to time-frame 0
Generate a test for f for time-frame 0 using a combinational
algorithm
If the fault effect is propagated to the flip-flops, continue
fault propagation in the next time-frame
If there are values required in the flip-flops, continue the
justification in the previous time-frame
K.T. Tim Cheng
06_seq_tg, v1.0
An Example
IN
OUT
s.a.1
y1
y2
Y2
Y1
FF1
FF2
K.T. Tim Cheng
06_seq_tg, v1.0
Example: Step 1
IN 0
1
OUT0
X
D
s.a.1
Time Frame 0
K.T. Tim Cheng
06_seq_tg, v1.0
Example: Step 2
IN 0
IN1
OUT0
D s.a.1
Time Frame 0
K.T. Tim Cheng
OUT1
s.a.1
Time Frame 1
06_seq_tg, v1.0
Example: Step 3
IN-1
IN0
OUT-1
Time Frame -1
K.T. Tim Cheng
06_seq_tg, v1.0
IN
OUT0
D s.a.1
Time Frame 0
D D
OUT1
s.a.1
Time Frame 1
An Example that Extended
D-Algorithm Fails
s.a.1
a
0
b
0
FF
F F
fa u ltfre e
fa u lty
fa u ltfre e
fa u lty
K.T. Tim Cheng
06_seq_tg, v1.0
Test Generation using Extended
D-Algorithm (Five-Valued Logic)
a
b
s.a.1
....
0
0
s.a.1
a
D 1
b
1
D
Conflict
1
0
D
D
0
0
No Test
K.T. Tim Cheng
06_seq_tg, v1.0
10
Nine-Valued D-Algorithm
(Muth, IEEE TC, June 1976)
Extended D-Algorithm is not complete
If nine-value, instead of five-value, is used, it will
be a complete algorithm
Ordered pairs of states of the fault-free and faulty
circuits (0/0, 0/1, 0/X, 1/0, 1/1, 1/X, X/0, X/1, X/X)
A superset of the five values (0=0/0, 1=1/1, X=X/X,
D=1/0, D=0/1) used in the D-Algorithm
Take into account the possible repeated effects of the
fault in the iterative array model
K.T. Tim Cheng
11
06_seq_tg, v1.0
Nine-Value Test Generation
s.a.1
a
0/1
1/X
b
1/X
0/1
s.a.1 No Conflict
....
a
0/1
b
1/X
0/X
1/0
0/1
0/X
0/0
1/X
0/X
K.T. Tim Cheng
06_seq_tg, v1.0
V1
V2
1
12
General Issues of Sequential ATPG
May not be able to handle highly sequential ckts
Consider the SA-0 fault at the most significant bit of a 20bit counter....
Timing may not be accurately modeled in ATPG
The sequence generated may cause races and hazards
The sequence must be verified by a simulator
There exist some potentially detected faults
Limitation of 3-valued logic
Tools must guarantee that there is no hazard on
asynchronous preset and clear
Tools must guarantee that test sequence will not
cause bus contention
K.T. Tim Cheng
13
06_seq_tg, v1.0
Test Generation for an Asynchronous Circuit
A
s.a.1
Z
Faulty function
K.T. Tim Cheng
06_seq_tg, v1.0
14
Time-Frame Expansion for Asyn.
Test Generation
A
C
1
A
X s.a.1
B
C
0/1
1
Z
X s.a.1
B
Z
1/0
previous time frame
current time frame
Test needs to be verified by a fault simulator with proper timing model !!
K.T. Tim Cheng
06_seq_tg, v1.0
15
General Issues of Sequential ATPG
May not be able to handle highly sequential ckts
Consider the SA-0 fault at the most significant bit of a 20bit counter....
Timing may not be accurately modeled in ATPG
The sequence generated may cause races and hazards
The sequence must be verified by a simulator
There exist some potentially detected faults
Limitation of 3-valued logic
Tools must guarantee that there is no hazard on
asynchronous preset and clear
Tools must guarantee that test sequence will not
cause bus contention
K.T. Tim Cheng
06_seq_tg, v1.0
16
Potentially Detectable Faults
Faults that are detectable for some initial power-up states &
undetectable for other initial power-up states.
Fault-free STG
0/0
1/0
00
x/0
x/0
s.a.0
0/1
01
{011} initializes the circuit to state 11
10
The response at Z to {0110}: xxx1
11
1/1
Y1 = xy1y2+y1y2+y1y2+xy1y2
Y2 = y1y2+y1y2
x/0
00
Z = y1y2
x/0
01
Faulty STG
{011} cannot initialize the circuit
The response at Z to {0110}:
10
x/0
0/1 11
1/1
If power-up state is 00: 0000
If power-up state is 01,10 or 11: xxx1
The fault is detectable if the power-up state of the faulty circuit is 00,
otherwise, it is undetectable => It is potentially detectable.
K.T. Tim Cheng
17
06_seq_tg, v1.0
An Irredundant, But ATPG
Untestable Fault
1
MUX
0
A
C
s.a.1
V1
Initial
state =
X/0
1/0
V2
0/0
Sequence A
K.T. Tim Cheng
DFF
06_seq_tg, v1.0
Initial
state =
X/1
1/1
0/1
18
Limitation of Three-Valued Logic
1
X
X
FF
Output
X
Regardless of the value in FF, output should be 1
But three-value logic would report unknown (x) at output
K.T. Tim Cheng
06_seq_tg, v1.0
19
General Issues of Sequential ATPG
May not be able to handle highly sequential ckts
Consider the SA-0 fault at the most significant bit of a 20bit counter....
Timing may not be accurately modeled in ATPG
The sequence generated may cause races and hazards
The sequence must be verified by a simulator
There exist some potentially detected faults
Limitation of 3-valued logic
Tools must guarantee that there is no hazard on
asynchronous preset and clear
Tools must guarantee that test sequence will not
cause bus contention
K.T. Tim Cheng
06_seq_tg, v1.0
20
10
Hazards on Asynchronous Preset and Clear
may have hazards
01
00
10
preset
DFF
w/ asyn.
preset/clear
clear
XX
00
(stable 0)
K.T. Tim Cheng
00
(stable 0)
Hazard-free
06_seq_tg, v1.0
21
General Issues of Sequential ATPG
May not be able to handle highly sequential ckts
Consider the SA-0 fault at the most significant bit of a 20bit counter....
Timing may not be accurately modeled in ATPG
The sequence generated may cause races and hazards
The sequence must be verified by a simulator
There exist some potentially detected faults
Limitation of 3-valued logic
Tools must guarantee that there is no hazard on
asynchronous preset and clear
Tools must guarantee that test sequence will not
cause bus contention
K.T. Tim Cheng
06_seq_tg, v1.0
22
11
ATPG Must Avoid Bus Contention
Add virtual logic in ATPG to ensure consistent data
when 1 tri-state drivers are on
enable_i = 1 for at least one value of i
For all i where enable_i = 1, data_is identical
enable_1
data_1
BUS FLOAT?
Weak pullup
or
Bus holder
enable_2
data_2
enable_3
data_3
enable_4
data_4
K.T. Tim Cheng
06_seq_tg, v1.0
23
Test Compaction of Sequences
Static compaction
ATPG should leave unassigned inputs as X
Two patterns compatible if no conflicting values for any PI
Combine two tests ta and tb into one test tab = ta tb using
D-intersection
Detects union of faults detected by ta & tb
Dynamic compaction
Process every partially-done ATPG vector immediately
Assign 0 or 1 to PIs to test additional faults
Ack: Bushnell and Agrawal, Essential of Electronic Testing, 2000
K.T. Tim Cheng
06_seq_tg, v1.0
24
12
Sequence Compaction Example
t1 = 0 1 X;
t2 = 0 X 1
t3 = 0 X 0;
t4 = X 0 1
Combine t1 and t3, then t2 and t4
Obtain: t13 = 0 1 0; t24 = 0 0 1
Test Length shortened from 4 to 2
K.T. Tim Cheng
25
06_seq_tg, v1.0
Sequential Test Generation: Taxonomy
sequential
synchronous
(or almost synchronous)
state
transition
level
RTL/
gate
level
asynchronous
asynchronous
simulation
based
gate
level
known
initial
state
unknown
initial
state
simulation
based
K.T. Tim Cheng
06_seq_tg, v1.0
time-frame
expansion
26
13
ATPG Using Mixed RTL/Gate Models
Advantages:
Handle larger circuits
Speed up test generation
Work better for data-dominated circuits
Disadvantages:
Not appropriate for control-dominated circuits
RTL description must be supplied by the user
References:
SCIRTSS: Hill and Huey, IEEE TC, May 1977
RTL D-Algorithm: Breuer & Friedman, IEEE TC, March 1980
Elektra: Ghosh et al, 27th DAC, June 1990.
K.T. Tim Cheng
06_seq_tg, v1.0
27
SCIRTSS & Electra
Assumption:
Both gate-level and RTL-level models are available
Data and control are separated in RTL model
Algorithm:
1. Generate a combinational test vector V = (I, S)
using the gate model
2. Find a fault-free justification sequence using RTL
description
3. Find a propagation sequence using RTL description
K.T. Tim Cheng
06_seq_tg, v1.0
28
14
Summary - ATPG
Commercial ATPG tools can handle >10M gates for
combinational and full-scan circuits
Sequential ATPG tools are also commercially
available but cannot handle large ckts without
design-for-testability (DfT)
Sequential ckts have potentially detectable faults
Undetectability does not imply redundancy for
sequential ckts
K.T. Tim Cheng
06_seq_tg, v1.0
29
15
