IEEE the 8th Asian Test Symposium (ATS'99), pp. 192-199, Nov. 1999.
PI1 PI2
PI3 C1 PO
C2
C3 C4
C5
C6
C7 FF2 FF1
FF3 FF4
FF5 FF6
FF7
FF8
PI1 PI2
PI3
PO C1
C2
C3 C4
C5
C6
C7
C2 PI3
PI1
PI2 C1
0 1 2 3 4
T(t, i) = T (t, i)1 for 0 t < min{l , k}, k + l t < l 1 2 1 T(t, i) = T (t, i) T (t-k, i)1 c 2 for k t < min{l , k+l }1 2
T(t, i) = X for l t < k1
T(t, i) = T (t-k, i)2 for max{l ,k} t < k+ l 1 2
<=
<= <=
<=
<=
b b b X X b X X X b b X X X X
T T
Skew 2
c
b b b X X b b b b b b b X X X b b X X X X
T’
b b b X X b X X X b b X X X X
0 1
2
5
3
4 6
7
C3
C1 C2
Extract_max_clique(G) /* G = (V, E, t) */ {
C = { v s.t. t(v) == 0}; v=Best_vertex(S,C) ; }
return C ; }
Candidates (C) {
/* S is a set of vertices s.t. any vertex in C is compatible with them */ return S;
}
Best_vertex(S, C) /* heuristics */ {
V2 = { v | |nbr(v)| is maximum in V1}; V3 = {v | t(v) is minimum in V2}; return (one vertex selected from V3); }
while((S = Candidates(C)) ! = φ ){ C = C {v};
S = { v | v V - C u C, ∃ (u, v) E};
V1 = { v | Σ w(u, v) is minimum in S, u C};
6
5
4 3
2 1 0
0 1
1 1
1 1
2
2 5
5 5
c
c
Skew 6
c Skew 4
10
Eeffective length b b b
X X b X X X b b X X X X
b b b X X b X X X b b X X X X
Skew 2
b b b X X b X X X b b X X X X
b b b X X b X X X b b X X X X
b b b X X b b b b b b b b b b b b b b b b b b b X X X b b X X X X
Test_generation_acyclic(S) {
Generate a time expansion model corresponding to S. Generate a template for a test sequence compaction.
(compacted N primitive templates)
} n = 0. {
Select a fault f from undetected fault set F.
Generate a test pattern for f in the time expansion model. Perform fault simulation for the time expansion model with the test pattern.
Remove detected faults from F.
Transform the test pattern into a test sequence with a test sequence compaction using the template.
n++; if (n= = N) {
Extract test patterns by a reverse transformation. Perform fault simulation for the time expansion model with the test patterns.
Remove detected faults from F. n = 0;
} }
for (undetedcted fault f F)
Time 0 1 2 4 3 5 6 7 8 9 10
PI1 PI2 PI3 Simulation
OK 0
X 0 1 0 0 1 1
1 X 1 1 0 1 1
0 1 0 1 0 1 0 1 X X 0
X X 1
X X X
OK OK OK Effective
length
Effective length of primitive template -1 0
Time 0 1 2
4 3
5 6 7 8 9 10
PI1 PI2 PI3 Simulation
OK 0
1
0 1
0 0 1 1
1 0
1 1
0 0 1 1
0
0 1
0 1 0 1 0
X 0
1
X 1
0
X 1
OK
OK
OK Effective
length
Extraction boundary 1
Extract 101100
