VLSI
VLSI Testing
Testing
Test
Test pattern
pattern Generation
Generation
Virendra Singh
Indian Institute of Science
Bangalore
virendra@computer.org
E0 286: Test & Verification of SoC Design
Lecture - 7
Feb 1, 2008
E0-286@SERC
Boolean
Boolean Difference
Difference
Shannons Expansion Theorem:
F (X1, X2, , Xn) = X2 F (X1, 1, , Xn) + X2 F (X1, 0, ,
Xn)
Boolean Difference (partial derivative):
Fj = Fj (1, X1, X2, , Xn) Fj (0, X1, , Xn)
g
Fault Detection Requirements:
G (X1, X2, , Xn) = 1
Fj
g
= Fj (1, X1, X2, , Xn) Fj (0, X1, , Xn) = 1
Feb 1, 2008
E0-286@SERC
Boolean Difference
f ( x1 , , x i = 0 , , x n ) f ( x 1 , , x i = 1, , x n ) = 1
Represented by the symbol df(x)/dx
df(x)/dxi for x =0 and df(x)/dxi for x=1 are called the
residues of the function for x = xi
One of the residue is the good-circuit value and
the other is the faulty-circuit value for xi
To detect the fault, the two residues should be
complementary
Solving the equation yield the values of the
primary inputs to detect a stuck-at fault on xi
The test pattern is then: xi df(x)/dxi = 1 & xi'
df(x)/dxi = 1
Feb 1, 2008
E0-286@SERC
Fault Detection
xi df(x)/dxi = 1 for s-a-0 at xi
xi' df(x)/dxi = 1 for s-a-0 at xi
As an example, let us consider the function
and a fault at x2
f(x) = x1x2 +x3
Thus df (x)/dx2 = x3 (x1 + x3) = x3x1 = 1. Then
x1 = 1 and x3 = 0.
For the SA1 and SA0 faults on x2, the patterns are then
x1x2x3 = (100) and (110), respectively.
x1
x2
g
x3
Feb 1, 2008
E0-286@SERC
f
4
Fault Detection
x1
G2
h
x2
s-a-0 fault at h
G1
Test Vector
h(X) dF*(X,h)/dh = 1
F(X,h) = x1 + hx2
x1. x1x2 = x1x2 = 1
h(X) = x1
x1 = 1
dF*(X,h)/dh = x1 (x1 + x2)
x2 = 1
= x1x2
Feb 1, 2008
E0-286@SERC
Fault Detection
x1
G2
h
x2
G1
s-a-1 fault at h
Test Vector
h(X) dF*(X,h)/dh = 1
x1x1x2 = x1x2 = 0
It cannot satisfy required condition
Fault - Redundant
Feb 1, 2008
E0-286@SERC
Binary
Binary Decision
Decision Diagram
Diagram
A node v with label xi defines a Shanon expansion
If the OBDD rooted in v represents the function f(x1, x2, . .
. , xn) the
Two sub-OBDDs rooted in the sons represent the
functions f(x1, x2, . . , xi-1, 0, xi+1, . . ., xn), and f(x1, x2, . .
, xi-1, 1, xi+1, . . ., xn),
xi
f0
Feb 1, 2008
f1
E0-286@SERC
Decision Structures
Truth Table
x1 x2 x3
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
Decision Tree
x1
0
0
0
1
0
1
0
1
x2
x3
0
Feb 1, 2008
x2
x3
x3
1
x3
1
Vertex represents decision
Follow green (dashed) line for value 0
Follow red (solid) line for value 1
Function value determined by leaf
value.
E0-286@SERC
Variable Ordering
Assign arbitrary total ordering to variables
e.g., x1 < x2 < x3
Variables must appear in ascending order along
all paths
OK
x1
Not OK
x1
x3
x2
x3
x1
x2
x3
x1
x1
Properties
No conflicting variable assignments along path
Simplifies manipulation
Feb 1, 2008
E0-286@SERC
Reduction Rule #1
Merge equivalent leaves
x1
x1
x2
x3
0
x2
x3
Feb 1, 2008
x2
x3
1
x3
1
x3
1
E0-286@SERC
x2
x3
0
x3
x3
1
10
Reduction Rule #2
Merge isomorphic nodes
x
x1
x1
x2
x3
x2
x3
0
Feb 1, 2008
x3
x3
1
E0-286@SERC
x2
x2
x3
x3
1
11
Reduction Rule #3
Eliminate Redundant Tests
x
x1
Feb 1, 2008
x1
x2
x2
x3
x3
x2
x3
0
E0-286@SERC
1
12
Example OBDD
Initial Graph
Reduced Graph
x1
x1
x2
x3
0
x2
x3
x2
x3
1
x3
x3
1
(x1+x2) x3
Canonical representation of Boolean function
Feb 1, 2008
For given variable ordering
Two functions equivalent if and only if graphs
isomorphic
Can be tested in linear time
Desirable property: simplest form is canonical.
E0-286@SERC
13
Reduced OBDD
Def: An OBDD is called reduced if
1.
It does not contain a node v with
high
(v) = low (v)
2.
There does not exists a pair of nodes u, v such
that the sub-OBDDs rooted in u and v are
isomorphic
Feb 1, 2008
E0-286@SERC
14
Example Functions
Constants
Variable
Unique unsatisfiable function
Unique tautology
Typical Function
x1
x2
No vertex labeled x3
x4
0
Feb 1, 2008
x1
(x1 x2 ) x4
Treat variable
as function
Odd Parity
independent of x3
Many subgraphs shared
x2
x2
x3
x3
x4
x4
E0-286@SERC
Linear
representation
15
Fault Detection
Reduced Graph
x1
x2
x1
x2
x3
x3
0
(x1+x2) x3
Trace a path from the root to 0 and 1
Value of the variables other than fault should
have same value
TP for s-a-0 fault at x1 is x1x2x3 = 101
TP for s-a-1 fault at x1 is x1x2x3 = 001
Feb 1, 2008
E0-286@SERC
16
Fault Detection
(a b ) (a b ) (a b )
1 1
2 2
3 3
a1
b1
a2
a1
b1
q
a2
b2
a3
b2
b3
a3
b3
s-a-0 at a1
a1=1, b1=1, a2=0, a3=0
Feb 1, 2008
E0-286@SERC
17
Fault Detection
(a b ) (a b ) (a b )
1 1
2 2
3 3
a1
b1
a2
a1
b1
q
a2
b2
a3
b2
b3
a3
b3
s-a-0 at p
a1=1, b1=1, a2=0, a3=0
Feb 1, 2008
E0-286@SERC
18
Fault Detection
(a b ) (a b ) (a b )
1 1
2 2
3 3
a1
b1
a2
a1
b1
q
a2
b2
a3
b2
b3
a3
b3
s-a-0 at q
a2=1, b2=1, a1=0, a3=0
Feb 1, 2008
E0-286@SERC
19
Thank You
Feb 1, 2008
E0-286@SERC
20
