Combinational & Sequential ATPG.pdf

Chapter 5
Test Generation for
Combination & Sequential
Circuits
Jin-Fu Li
Advanced Reliable Systems (ARES) Lab
Department of Electrical Engineering
National Central University
Jungli, Taiwan

Advanced Reliable Systems (ARES) Lab. Jin-Fu Li, EE, NCU 2
 Basics
 ATPG Algorithms for Combinational Circuits
 Boolean Difference
 Single-Path Sensitization
 D-Algorithm
 PODEM
 Redundancy Identification
 Problems of Sequential Circuit testing
 ATPG Approaches for Sequential Circuits
 Time-Frame Expansion
 Simulation-Based Approach
 Scan
 Summary
Outline

 Consider a 64-bit adder as shown below
Functional vs. Structural Test
A
64
B Cin0
64
Sum
Carry
64
Functional Test Structural Test
Sumi
Ai
Bi
Cini
Ai
Bi
Cin i
s/0, s/1
s/0, s/1
s/0, s/1
s/0, s/1
s/0, s/1
Cin i+1
s/0, s/1
s/0, s/1
s/0, s/1
s/0
s/0
s/0
s/1
s/1
s/1
s/0, s/1
s/1

 Functional test
 Generate complete set of tests for circuit input-
output combinations
 129 inputs & 65 outputs
 2129=680,564,733,841,876,926,926,749,214,
863,536,422,912 test patterns are required
 Using 1 GHz ATE, would take 2.15 x 1022 years
 Structural test
 64 bit slices and each slice has 27 faults (using
fault collapsing)
 At most 64x27=1728 faults, thus only 1728
test patterns are required
 Takes 0.000001728 seconds on 1 GHz ATE
Functional vs. Structural Test

 All ATPG programs need a data structure
describing the search space for test
patterns
 Binary decision tree
Circuit & Binary Decision Tree
A’
0 1
C’ C
1 0
C’ C
1 0
C’ C
0 1
C’ C
A
B’ B B’ B
D
A
B
C

 Binary decision diagram (BDD)
 Follow path from source to sink node – product
of literals along path gives Boolean value at
sink
 Rightmost path: A B’ C’ = 1
 Problem: size varies greatly
with variable order
Binary Decision Diagram
Gate level
A’
0 1
C’
C
A
B’
B
B’
B
C
C’

 Algorithm is complete if it ultimately can
search entire binary decision tree, as
needed, to generate a test
 Untestable fault – no test for it even after
entire tree searched
 Combinational circuits only – untestable
faults are redundant, showing the presence
of unnecessary hardware
Algorithm Completeness

 Exhaustive test generation
 Completely exercise the fault-free behavior
 Appropriate only when the number of PIs is
small
 Detects all the universal faults (i.e., all
combinational faults)
 Pseudoexhaustive test generation
 Test most of universal faults by applying
exhaustive test on subsets of PIs
 Pseudorandom test generation
 Generate test pattern deterministically
 Patterns have many characteristics of random
patterns but are repeatable
Algorithm Types

 Algorithmic (deterministic) test generation
 Algebraic (symbolic) techniques
 SPOOFs
 Line condition equations
 Boolean difference
 Path-oriented techniques
 Single-path sensitization
 D-algorithm
 PODEM
 FAN
 Produces higher-efficiency test patterns, but its
cost is more expensive
Algorithm Types

Boolean Difference
 Shannon’s Expansion Theorem
 An arbitrary Boolean function f(x1,x2,…,xn) can
be expanded about any variable
 For example, if we expand the function with
respect to x2, then the function can be
expressed as below
 f(x1,x2,…,xn)=x2.f(x1,1,…,xn)+x2
’.f(x1,0,…xn)
 Boolean Difference
 Let f(x)=f(x1,x2,…,xn) be the normal (fault-free)
output function realized by network N, and
fa(x1,x2,…,xn) be the faulty output function
resulting from a fault a in N.
 The test set for a fault a is Ta=f(x) fa(x)


 Example:
 Definition 1
 : f(X) with
 : f(X) with
 Definition 2
 The boolean difference of f(X) with respect to
xi is defined as
Boolean Difference
3
2
0
/ )
(
1
x
x
X
fx 
3
1
3
2
2
1
)
( x
x
x
x
x
x
X
f 


}
101
,
100
{
0
/
1

 x
T
2
1
3
2
3
1
3
2
2
1
0
/ )
(
)
(
)
( 1
x
x
x
x
x
x
x
x
x
x
X
f
X
f x 





3
2x
x
1
x 00 01 11 10
0
1
1
1
1 1
1
1 0
0
0
0
0
0 0
0
0
0
)
,
,
,
0
,
,
,
,
(
)
0
( 1
1
2
1 n
i
i
i x
x
x
x
x
f
f 
 


)
,
,
,
1
,
,
,
,
(
)
1
( 1
1
2
1 n
i
i
i x
x
x
x
x
f
f 
 


)
0
/
.,
.
(
0 i
i x
e
i
x 
)
1
/
.,
.
(
1 i
i x
e
i
x 
)
,
,
,
,
(
)
,
,
,
,
(
)
1
(
)
0
(
)
(
1
1 n
i
n
i
i
i
i
x
x
x
f
x
x
x
f
f
f
dx
X
df



 






 Let and , then
Boolean Difference
)
1
(
)
0
(
0
)
(
i
i
i
f
f
dx
X
df



1
/
i
x


)
1
(
)
0
(
1
)
(
i
i
i
f
f
dx
X
df



0
/
i
x


i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
dx
X
df
x
f
f
x
f
f
x
f
f
x
f
f
x
f
x
X
f
X
f
)
(
))
0
(
)
1
(
(
)
0
(
)
1
(
)
0
(
)
1
(
)
0
(
))
1
(
)
0
(
(
)
(
)
(









 

T
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
i
dx
X
df
x
f
f
x
f
f
x
f
f
x
f
f
x
f
x
X
f
X
f
)
(
))
1
(
)
0
(
(
)
1
(
)
0
(
)
1
(
)
0
(
)
1
(
))
1
(
)
0
(
(
)
(
)
(









 

T

 The test set for of the circuit shown
below can be derived as follows
An Example of Boolean Difference

1
/
1
x



3
x
1
x
2
x
2
1
3
2
3
2
3
2
3
2
1
3
2
3
2
1
3
2
3
2
1
1
1
]
)
)(
[(
)]
(
)
[(
))
,
,
1
(
)
,
,
0
(
(
)
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
f
x
x
f
x
dx
X
df
x












T

 Definition
 We say a test activates a fault if it
generates an error (or a fault effect) by
creating different and values at the fault
site . We say propagates the error (fault
effect) to a PO if it results in different
and values
 Definition
 A line whose value in the test changes in the
presence of the fault is said to be sensitized
to by . A path composed of sensitized lines
is called a sensitized path.
Single-Path Sensitization

t
)
(l
v )
(l
v
l t
z )
(z
v
)
(z
v

t
 t

 Fault activation or excitation
 Specify inputs so as to generate the
appropriate value at the fault site, i.e., 0 for
s/1 and 1 for s/0
 Fault propagation
 Select a path from the fault site to an output
and specify other signal values to propagate
the fault (error signal) along the path to the
output
 Line justification
 Specify input values so as to produce the signal
values specified in fault activation and fault
propagation, i.e., perform consistency check
Procedure

 Use single-path sensitization to derive a
test set for in the following circuit
 Generate a appropriate value a=0. A=B=C=1
 Choose a path via G5b=1A=D=0.
Contradiction!
 Try another path via G6c=1C=1 and E=0.
OK! Therefore, T=ABCE’
An Example
G1
D
G2
G4
G3
G5
G6
A
B
C
E
a
b
c
f1
f2
1
/
a



 A literal is defined as a single variable within a term that
may or may not be complemented
 A product term is an implicant of a function if the
function has the value 1 for all minterms of the product
term
 Any single 1 or group of 1s in the Karnaugh map of a
function F is an implicant of F
 If the removal of any literal from an implicant P results in
a product term that is not an implicant of the function,
then P is a prime implicant
 A product term is called a prime implicant of F if it cannot be
combined with another term to eliminate a variable (literal)
 If a minterm of a function is included in only one prime
implicant, that prime implicant is said to be essential
(essential prime implicant)
 A product term is an essential prime implicant of F if there is
a minterm that is only covered by that prime implicant
Definitions for Logic Manipulation

Examples
AB
CD 00 01 11 10
00
01
11
10
0 1 1
1 1
1
1 0 0
0 0
0
0
0
0 0
 Karnough map of a function F
 Each of the coverings is a prime implicant
 BC’, A’C’D, A’B’D’
 F(A,B,C,D)=BC’+A’B’D’ (minimum # of PIs)
 Prime implicant A’C’D is a non-essential prime
implicant
 A PI is essential PI if it covers a minterm that
cannot be covered by any other PIs
 BC’ and A’B’D’ are essential PIs

Definitions for ATPG Alg.
 Definitions
 The fault cone is the portion of a circuit whose
signals are reachable by a forward trace of the
circuit topology starting at the fault site
 A forward implication results when the inputs
to a logic gate are assigned to specific values
such that the output can be uniquely
determined
 Backward implication is the unique
determination of all inputs of a gate for given
output and possibly some of the inputs

 Definition
 The singular cover of a logic gate is the
minimal set of input signal assignments needed
to represent essential prime implicants of the
logic gate
 D-Algorithm
 Based on a cubical algebra called D-calculus
 D: signal value that is 1 in normal circuit and 0
in faulty case (discrepancy), i.e., D=1/0
 D’: signal value that is 0 in normal circuit and 1
in faulty case, i.e., D’=0/1
 D and D’ may be defined the other way around
D-Algorithm

 Composite logic values for D-Algorithm
 For example, D’+0=0/1+0/0=(0+0)/(1+0)
= 0/1=D’
 The unspecified value (x) can be any value
in {0, 1, D, D’}, and it sometimes is
dented as u
D-Algorithm
v/va 0/0 1/1 0/1 1/0 x/x
Symbol 0 1 D’ D X
D’
D’
0

Intersection Rules
 Let , then
 1.
 2. if then
 3. Composite logic values
 For example:
 (1X1 01) (X1X 01) = (111 01)
 (1X1 X1) (01X X1) = (D11 11)
}
,
1
,
0
{
,
,
, 2
1 x
v
v
v n 

n
i
v
v
x i
i 

 1
,

x
v
v j
i 
, 
j
i v
v 
i
v j
i 
if
D or D’ otherwise
0 1 X
0
1
X


0
D
0
D’
1
1
0
1
X


 Definition
 For a gate G realizing function f, the singular
cover of G is the set of the prime implicants of
f and f’. Each prime implicant of the singular
cover is called a singular cube or a primitive
cube
 A singular cube consists of the input subcube and the
output subcube:
where the xi’s are inputs, the yi’s are outputs, and vi
Singular Cover & Singular Cubes
),
,
,
,
(
)
,
,
,
,
( 2
1
1
1 m
n
m
n v
v
v
y
y
x
x 
 


}
,
1
,
0
{ x

a
c
b
a c
b
0 0
1
0 1
0
1 0
0
1 0
1
a c
b
X 0
1
0 1
0
1 0
X
Truth table Singular cover
Prime implicant of f
PIs of f’

 Definition
 The propagation D-cubes of a gate G are the
cubes that cause the output of G to depend
only on one or more of its specified inputs, i.e.,
cubes that propagate a fault on these inputs to
the output
 Pdc’s can be derived by inspection or from the
singular cover (or truth table) using the intersection
rules
Propagation D-Cubes (pdc)
a
c
b
a c
b
D D’
0
0 D’
D
D D’
D
Propagation D-cubes

 Definition
 The primitive D-cubes of a fault associated
with a gate G are the cubes (with inputs
completely specified) that brings the influence
of to the output of G, i.e., produce an error
signal (D or D’) at the output
 Pdcf can be derived from the singular covers of
f and f
Primitive D-Cubes for a Fault (pdcf)


a
c
b
a c
b
X D’
1
1 D’
X
a c
b
0 D
0


for
for
0
/
c

 1
/
c




Thus, pdcf of is 101D
 Let p0 and p1 be the sets of singular cubes
of f with output coordinates of 0 and 1,
respectively, and q0 and q1 be the
corresponding sets in f
 generated; generated
 For example,
Derive pdcf with Singular Covers

D
q
p 
 0
1
1
/
b


D
q
p 
 1
0
)}
;
11
(
),
;
11
{(
)},
;
1
(
),
;
101
(
),
;
1
{( 1
0
0
1 D
D
D
D
q
p
D
D
x
D
D
x
D
q
p 




a
c
b d a c
b
X X
0
0 X
X
X 0
X
d
1 1
1
1
1
1
0
a c
b
0 X
X
X 0
X
d
1 1
X
1
1
0
f 
f

 Definition
 The set of gates whose output value is
currently x but have one or more D/D’ signals
on their inputs is called the D-frontier
 Fault propagation (D-drive) consists of selecting one
gate from the D-frontier and assigning values to the
unspecified gate inputs so that the gate outputs
become D or D’
 An empty D-frontier shows that backtracking should
occur
D-Frontier
D-frontier
Multiple
sensitized paths

 Procedure D-algorithm /*generating a test
for a single stuck fault */
 1. Select a pdcf for (fault activation/excitation)
 2. Sensitize all possible paths from the fault site
to a PO (fault propagation or D-drive)
 By intersections of the pdcf with pdc’s of successive
gates
 Continued (back to step 1 if necessary) until a primary
output has D or D’
 3. Develop a consistent set of primary input
values that will account for all lines set to 0 or 1
during the D-drive. If inconsistent, seek a
different path (or even a different pdcf). (line
justification, consistency check)
D-Algorithm Procedure



 Use the D-algorithm to derive a test for for the following
circuit
Examples
0
/
6



1
2
3
4
5
7
9
8
6
G1
G2
G3
G4
G5
1 5
2
X 0
1
1 0
X
0 1
0
3 6
4
X D
0
0 D
X
3 7
5
0 1
X
X 1
0
1 0
1
2 8
6
0 D’
D
D D’
0
D D’
D
7 9
8
1 D’
D
D D’
1
D D’
D
G1 G2 G3 G4 G5
sc pdcf sc pdc pdc
1 5
2 3 6
4 7 9
8
1. Select a pdcf-
2. Pdcf- pdc-G4
3. pdc-G5 (polarity inverted)
4. Check line7=1 from sc-G3  line5=0
5. Check line5=0 from sc-G1  line1=1
X X
X 1 D
0 X X
X
X X
0 1 D
0 X X
D’
X X
0 1 D
0 1 D
D’
X 0
0 1 D
0 1 D
D’
1 0
0 1 D
0 1 D
D’








 Try it again for the fault for the following circuit
 D-algorithm is complete; it will find a test for a given fault
if such a fault exists (i.e., the fault is not redundant). Given
a fault list, the algorithm proceeds with 1 fault at a time.
Examples
1
/
d



G3
G2
G1
G4
G6
G5
d
e
f
g
h
i
a
a
c
b
d e f g h i
a c
b
D’ X X X X X
1 X
1
D’ 1 X D X X
1 X
1
D’ 1 X D X X
1 0
1
D’ 1 1 D D’ X
1 0
1
D’ 1 1 D D’ D
1 0
1
Thus 110 is a test

 Path Oriented DEcision Making
 Similar in principle to the D-algorithm but
different in approach (more efficient)
 Complete, like D-algorithm
 Treats a value to be justified for line as
an objective ( ) to be achieved via PI
assignment – direct search
 Allows assigning values only to primary
inputs (PIs)  backtracing can occur only
at the PIs, i.e., examine all possible PIs
implicitly but exhaustively, and terminate
as soon as a test is found
PODEM
l
v
l ,
l
v l

 Consider the circuit shown below and the
objective (f,1)
Backtracing
f
e
d
c
b
a
1. Assume that backtracing follows the path (f,d,b). Simulating
the assignment b=1 does not achieve the objective (f,1).
2. Executing again backtracing follows the path (f,d,c,a). Now
simulating the assignment a=0 achieves f=1.

 Backtracing maps a desired objective into a PI
assignment that is likely to contribute to
achieving the objective
 No values assigned during backtracing; values
assigned only by simulating PI assignments,
i.e., only by forward implication of PI
assignments ( values always self-consistent
& automatically justified)
 Viewed as a branch and bound search
algorithm over an n-dimensional space (n
variables)
 Five to fifteen times faster than D-algorithm
PODEM

 Procedure PODEM
 1. (Initialization) PI, PI
 2. Assign a 0 or 1 to a PI (for a given objective)
 3. Determine whether the current combination
of values on the PIs, assigned or unassigned,
constitutes a test. Stop if a test is found
 4. (Backtracing) If it is possible to generate a
test with additional assigned PIs, go to 2
 5. (Backtracing) If input pattern which has
not been examined as a possible test, go to 3,
else the fault is redundant (undetectable)
PODEM Procedure
x




 Combinational ATPG can find redundant
(unnecessary) hardware
 However, there are still circuits with
redundant hardware that are fully testable
 For example,
 Faults (a/0, a/1, b/0, b/1) can be tested by
tests (A=0, A=1)
 Therefore, these faults are not redundant
Irredundant Hardware and Tests
a b
a/0,
a/1
b/0,
b/1
A C

 Redundant hardware from testing definition
 The benefits of redundant hardware
removal
 Reduce area cost
 Improve performance
 Reduce power consumption
 Improve reliability
Redundant Hardware & Simplification
A
B
E
D
D/0
A
B
E B E

 An example of a circuit with a redundant fault q/1
Pernicious Fault Masking
Z
Y
A
B
C
d
e
f
g
h
k
j
l
m
s
p
q
r
n
q/1
0
0
0
0
0
0
0
0
0
0 0
0
0
1
conflict
Z
Y
A
B
C
d
e
f
g
h
k
j
l
m
s
p
q
r
n
f/0
D
D D D
1
1 D
0 0

 For multiple stuck-faults, if one of the multiple
faults is redundant, the presence of the redundant
fault may mask the presence of other, testable
faults
 This is a serious compromise of circuit reliability
Pernicious Fault Masking
Z
Y
A
B
C
d
e
f
g
h
k
j
l
m
s
p
q
r
n
f/0
D
D D 1
1
1 D
0 0
q/1

Problems of Sequential Ckt Testing
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

Sequential Circuit Representation
 A representation of a synchronous
sequential circuit
 The concept of time frame
Combinational Logic
state
clk
X Z
Y
y
(primary inputs) (primary outputs)
(next state)
(present state)
X(0)
y(0) Y(1)
Z(0)
X(1)
y(1) Y(2)
Z(1)
X(2)
y(2) Y(2)
Z(2)
Time frame

Time-Frame Expansion
 Iterative Array Conversion
 Sequence of inputs in time: x(1), x(2),…, x(n)
 Sequence of outputs in time: z(1), Z(2),…,z(n)
 Sequence of internal states in time: y(0),
y(1),…, y(n)
X(0)
y(0) Y(1)
Z(0)
X(1)
y(1) Y(2)
Z(1)
pFF pFF
y(2)
Time (space) frame 0 Time (space) frame 1
pseudo Flip Flop
C/L C/L

 For synchronous sequential circuit (FSMs)
 Transforming FSMs to iterative logic array (ILA)
by unrolling the Huffman model
 Applying D-alg (or PODEM, path sensitizer,
etc.) to the ILA
 Pseudo flip-flop (pFF) is a combinational circuit
mapping its excitation function onto its output
 E.g., a pseudo T-FF can be constructed by an XOR
gate as shown below
T
Y
y
T Y y
0 0
0 1
1 0
1 1
0
1
1
0

 When a single stuck-at fault is present
in the real sequential circuit, it will
appear as a multiple fault, existing in
each unfolded iteration (time frame)
Comb.
block
Fault
Time
Frame 0
Unknown
or given
Init. state
State
variables
Next
state
Time
Frame n-2
Time
Frame n-1

An Example
 Derive a test sequence for the fault a/1 of the
following circuit. Assume that the initial state
of the sequential circuit is (y1,y2)=(0,0)
x
x’
y2
y1
y1
y1’
x’
x
y2
y2
y2
y2’
y1’
x
z
G1
G2
G3
G4
G5
G6
G7
D1
D2
y1(0)=0
y2(0)=0
x (0)=1
z (0)=1
x (1)=1 x (2)=1
z (1)=1 z (2)=D
0
D’
D’
D’

An Example
 Test pattern generation with D-alg.
 t0: initial state y1=y2=0; y2=0 and a/1 a=D’
 Set x(0)=1y2(1)=D’ and z(0)=1
 z != D or D’  Continue!
 t1: set x(1)=1y1(2)=y2(2)=D’ and z(1)=1
 z !=D or D’ Continue!
 t2: on G5, let x(2)=1
 y1(2)=D’z(2)=D
 Test sequence X=111
 Termination rules
 If z=D or D’ then a test sequence is found
 If k>4n, where n is the number of FFs of the
original circuit, then the circuit is redundant

Simulation-Based Test Generation
 CONTEST
 A concurrent test generator for sequential circuits---
using concurrent fault simulator
 Pseudo code
Initialization:
{1. Start with an arbitrary vector and all FFs in unknown
state;
2. Generate new vectors to reduce cost by 1-bit changes in
the present vector
/*use only true-value simulation*/
/*cost=number of FFs in unknown state*/
3. Stop when cost drops below desired value; }
Tests for concurrent targets:
{1. Start with initialization vectors;

Simulation-Based Test Generation
2. Fault simulate vectors and remove detected faults;
3. Compute cost function for the last vector;
/* cost(undetected f.)=min dist of its effect from an o/p
*/
/* cost(vector)=sum of costs of all undetected faults*/
4. New vectors=those 1-bit changes that reduce vector
cost; }
Test for remaining undetected single faults:
{1. Revise the cost function (a dynamic testability measure);
/*cost=K x activation cost + propagation cost */
/* activation cost = dynamic controllability of faulty line
*/
/*propagation cost = min dynamic observability of faulty
line */
/* k is a large weighting factor*/
2. Generate a test for a single fault;}

 Combinational ATPG algorithms
 D-algorithm
 PODEM
 single-path sensitization
 Boolean difference
 ATPG also can aid the designer to find the
redundant hardware of the circuit
 Sequential ATPG approaches
 Time-frame expansion
 Simulation-based ATPG
 Sequential ATPG are not widely used in the IC
industry
 Low fault coverage
 Long ATPG time
Summary

Combinational & Sequential ATPG.pdf

Recommended

More Related Content

What's hot (20)

Similar to Combinational & Sequential ATPG.pdf (20)

Recently uploaded (20)

Combinational & Sequential ATPG.pdf