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 1
Boolean
Boolean Difference
Difference
Shannon’s Expansion Theorem:
F (X1, X2, …, Xn) = X•2 F (X1, 1, …, Xn) + X•2 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 = Fj (1, X1, X2, …, Xn) ⊕ Fj (0, X1, …, Xn) = 1
∂g
Feb 1, 2008 E0-286@SERC 2
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 3
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) = x3’x1 = 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
g
x2
f
x3
Feb 1, 2008 E0-286@SERC 4
Fault Detection
x1 F
G2
h
s-a-0 fault at h
x2 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 5
Fault Detection
x1 F
G2
h
x2 G1 s-a-1 fault at h
Test Vector
h(X)’ dF*(X,h)/dh = 1
x’1x1x2 = x1x2 = 0
It cannot satisfy required condition
Fault - Redundant
Feb 1, 2008 E0-286@SERC 6
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 f1
Feb 1, 2008 E0-286@SERC 7
Decision Structures
Truth Table Decision Tree
x1 x2 x3 f
x1
0 0 0 0
0 0 1 0
0 1 0 0 x2 x2
0 1 1 1
1 0 0 0
1 0 1 1 x3 x3 x3 x3
1 1 0 0
1 1 1 1
0 0 0 1 0 1 0 1
¾ Vertex represents decision
¾ Follow green (dashed) line for value 0
¾ Follow red (solid) line for value 1
¾ Function value determined by leaf
value.
Feb 1, 2008 E0-286@SERC 8
Variable Ordering
Assign arbitrary total ordering to variables
¾ e.g., x1 < x2 < x3
Variables must appear in ascending order along
all paths
OK Not OK
x1 x1 x3 x1
x2 x2
x3 x3 x1 x1
Properties
No conflicting variable assignments along path
Simplifies manipulation
Feb 1, 2008 E0-286@SERC 9
Reduction Rule #1
Merge equivalent leaves
a a a
x1 x1
x2 x2 x2 x2
x3 x3 x3 x3 x3 x3 x3 x3
0 0 0 1 0 1 0 1 0 1
Feb 1, 2008 E0-286@SERC 10
Reduction Rule #2
Merge isomorphic nodes
x x x x x x
y z y z y z
x1 x1
x2 x2 x2 x2
x3 x3 x3 x3 x3 x3
0 1 0 1
Feb 1, 2008 E0-286@SERC 11
Reduction Rule #3
Eliminate Redundant Tests
y y
x1 x1
x2 x2 x2
x3 x3 x3
0 1 0 1
Feb 1, 2008 E0-286@SERC 12
Example OBDD
Initial Graph Reduced Graph
x1 x1
(x1+x2)· x3
x2 x2 x2
x3 x3 x3 x3 x3
0 0 0 1 0 1 0 1 0 1
Canonical representation of Boolean function
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.
Feb 1, 2008 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
0 Unique unsatisfiable function x
Treat variable
1 Unique tautology as function
0 1
Typical Function Odd Parity
x1 x1
(x1 ∨ x2 ) ∧ x4
x2 No vertex labeled x3 x2 x2 Linear
independent of x3 representation
x3 x3
Many subgraphs shared
x4 x4 x4
0 1 0 1
Feb 1, 2008 E0-286@SERC 15
Fault Detection
Reduced Graph
x1 g x1
x2 (x1+x2)· x3
x2
f
x3 x3
0 1
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
a1 p
b1 b1
a2 q f a2
b2
b2
a3 r
b3 a3
b3
s-a-0 at a1 0 1
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
a1 p
b1
b1
a2 q f a2
b2
b2
a3 r
b3 a3
b3
s-a-0 at p
0 1
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
a1 p
b1
b1
a2 q f a2
b2
b2
a3 r
b3 a3
b3
s-a-0 at q
0 1
a2=1, b2=1, a1=0, a3=0
Feb 1, 2008 E0-286@SERC 19
Thank You
Feb 1, 2008 E0-286@SERC 20
