Lecture OnTest Generation : Lecture OnTest Generation TRAILOKYA NATH SASAMAL
M-TECH(DTI)
09305ENO22
Slide 2: Fault Diagnosis
Fault Detection Fault Location To determine whether circuit
is fault-free or not Identifying faulty component
/module/ subsystem Complete test set – all possible input combinations Objective : minimize the length of test sequence Done by applying test vectors & observing o/p Detects every faults of ckt
Fault simulation : Fault simulation If x stuck-at faults
Apply all test pattern
Test coverage tc=f/x
f:detected fault
0≤ tc ≤1 Determine which faults detected by a set of patterns To fault free ckt To each x copies of ckt containing only one stuck-at fault
Slide 4: Test Generation PATH SENSITIZATION
BOOLEAN DIFFERENCE METHOD
D-ALGORITHM
PODEM
STATE TABLE VERIFICATION APPROACH Assumptions: 1.Fault is permanent
2.circuit is non-redundant Function realized by ckt is not same as function realize by the ckt with fault Combinational ckt Sequential ckt
Slide 5: Path Sensitization Sensitized path : Terminology : Primary input : Line not fed by other line in circuit Primary output : Line accessible to exterior of circuit Any change in value along the
path would propagate to o/p Steps : 1. Select a path from faulty line to primary o/p 2. Assign faulty line 0(1) if fault is s-a-1(s-a-0) 3. Sensitize the path 4. Trace back to circuit i/p if consistent i/p combination (a test ) exist then terminate process else(a contradiction) select another path starts at faulty line
Contradiction Case: : Contradiction Case: x1 x2 x3 x4 a b z1 z2 A B C E D g i k j c d e f l m h=1 S-a-0 Gate B o/p S-a-0 fault h=1 need c=d=0
Two path hjl & hkm
For hjl
g=0 need a=b=1
But b=c=X2, b≠c contradiction
So hjl not sensitizable & not detected at Z1
But detected at Z2 by sensitizing path hkm
x2=x3=0,x4=0 or 1,x1= 0 or 1 contradiction
Slide 7: Example : 2.set x3=0 4.Backward trace For G4=1
x1= G1=1 i.e., x2=0 For G8=1, G6 = 0. For G6=0, x2=0 & x3=0 or 1 I/p combination may not unique to propagating a fault to o/p
Therefore the test x1x2x3x4x5=10001 by sensitizing path G5G7G9
Or _1001(independent to x1) by sensitizing path G5G8G9 Test generation for x3 s-a-1 a 1.Path – x3-G5-a-G7-G9-z 3.path sensitization X4=0,x5=G4=G8=1 0
Slide 8: Contradiction during back tracing For s-a-0 fault G2=1 ; x2=x3=0.
put x4=0 .. G4=G5=G7=0 For G7=0,
G3=1 & x3=0. For G3=1,x2=x4=0 Now G5=0, x1 => 1 G4=0 & x2=0,
G1=1 & x1=x3=0. i.e. contradiction in X1 Sensitization of both paths G2G6G8 & G2G5G8 simultaneously
x1=x4=0, & G4=G7=0 Test set =0000 multiple paths sensitized simultaneously
Boolean Difference : Boolean Difference if for all i/p combination F(x1,….., xi,…..xn) = F(x1,….., x’i,…..xn)
i.e. dF(x)/dxi=0 =>F(x) independent of xi
Xi not affect final output.
if for at least one i/p combination
F(x1,….., xi,…..xn) ≠ F(x1,….., x’i,…..xn)
i.e. dF(x)/dxi=1 => F(x) dependent of xi Boolean difference of F(X) w.r.t. xi dF(x)
dx i = F(X) + F(X ) F(X) = F(x1,x2,……..xi,…..xn) & F(X ’) = F(x1,x2,…..xi’,…xn)
Slide 10: 1.dF(x)/dxi = dF(x)/dxi
2.dF(x)/dx’i = dF(x)/dxi
3.d/dxi dF(x)/dxj = d/dxj (dF(x)/dxi)
4.d[F(x)G(x)]/dxi=F(x) dG(x)/dxi G(x) dF(x)/dxi dF(x)/dxi dG(x)/dxi
5.d[F(x)+G(x)]/dxi= F’(x) dG(x)/dxi G’(x) dF(x) /dxi (+) dF(x)/dxi dG(x)/dxi
6.d[F(x) G(x)] /dxi = dF(x) /dxi dG(x) /dxi Properties of Boolean difference
Slide 11: Rules for deriving test sets
test set for s-a-0 => xi .dF(x)/dxi
fault undetectable if xi .dF(x)/dxi = 0
test set for s-a-1 => xi’. dF(x)/dxi
fault undetectable if xi’. dF(x)/dxi =0
: F=f(x1,……..,xn,h) where h=f(x1,……..,xn)
F=(x3x4+(x2x4)’) +h, [ where h=x1x2]
dF/dh =(x3x4+(x2x4)’)’ dh/dh (+) 0 (+) 0
=(x3’+x4’)x2x4
=x2x3’x4
Test sets for s-a-0(h0) are given by
h. dF/dh =x1x2.x2 x3’x4 = x1x2. x3’x4
(1101,1001,0101,0001,0000,0100,1000,1100)
Test sets for s-a-1(h1) are given by
h’. dF/dh = (x1x2)’x2x3’x4= x’1x2.x3’X4
(0101,0001,0100,0000) Example : generating test for line h
Slide 13: Example(Test for all single node faults)
F=x1’x2x3’+x1’ x2’ x3
dF/dx1=x2x3’+x2’ x3
dF/d x2=x1’ x3’+x1’ x3
dF/dx3 =x1’ x2+x1’ x2’
Test inputs to check input line faults
x1 (s-a-0)= x1 (x2x3’+x2’ x3) i.e.110 or 101
x1 (s-a-1)= x1’(x2x3’+x2’ x3) i.e. 010 or 001
x2 (s-a-0)= x2 (x1’ x3’+x1’ x3 i.e. 010 or 011
x2 (s-a-1)=x2’(x1’ x3’+ x’1x3) i.e. 000 or 001
x3 (s-a-0)=x3 (x1’ x2 +x1’ x2’) i.e. 011 or 010
x3 (s-a-1)=x3’(x’1x2 +x1’ x2’) i.e. 001 or 000
110,010,001 is complete test set for detecting primary input faults
For internal faults partial Boolean difference is used
if z=f(y) & y=f(x)
dz/dx=dz/dy .dy/dx [dz/dx partial Boolean difference of z with respect to x]
Slide 14: dF/dx2= dF/dp.dp/dn.dn/dl.dl/dx2
dF/dp=d (x1’.p’) /dp=x1’
dp/dn=d(m’.n’)/dn=m’=x2+l=x2+x2’x3’
dn/dl=d(l’ x3’)/dl=x3’
dl/dx2=d(x2’ x3’)/dx2=x3’
dF/dx2 =x1’.(x2+x2’ x3’). x3’. x3’
= x1’ x3’
Test for path x2-l-n-p-F are
x1’x2x3’(010) & x1’ x2’ x3’(000)
path x3-n-p-F
dF/dx3=dF/dp.dp/dn.dn/dx3
= x1’m’ l’
= x1’ x2
The test sets x1’x2x3’ or x1’ x2 x3 (010 or 011) Test for path x2-l-n-p-F:partial Boolean difference
D-Algorithm : D-Algorithm Algorithm will generate a test for a fault if it exists .
D notation allows quickly write fault:
D on a node shows good and faulty
circuits have different values at that point.
Notation :
D - “1” in the good circuit “0” in the faulty
D’ - “0” in the good circuit “1” in the faulty (Dbar) NOR: 0 0 D o/p S-a-0
x 1 D’ o/p S-a-1
1 x D’ S-a-1
Slide 16: 1.Singular Cover
Singular cover of a logic gate is compact version of truth table. X 0 or 1 Truth table nor gate singular cover singular cover for a network is set of singular covers of each of its gate 1 1 0 Terminology : each row
singular cube
Slide 17: Intersection rules for deriving propagation D cube from
singular cover
0 ∩ 0 = 0 ∩ x = x ∩ 0 = 0
1 ∩ 1 = 1 ∩ x = x ∩ 1 = 1
x ∩ x = x
1 ∩ 0 = D
0 ∩ 1= D
To construct propagation D cube ,intersect cubes with different output values in a gate’s singular covers a b c
C1 1 1 0
C2 x 0 1
C3 0 x 1 a b c
c1 ∩ c2 1 D D’
c1 ∩ c3 D 1 D’ 2. Propagation D Cubes Symbol D = 0 or 1, consistent throughout ckt causes o/p of gate depend only on one or more
of its i/p i.e. to propagate a fault on these i/p to o/p Derived from singular cover Nand gate
Slide 18: 3. Primitive D Cubes of a Fault : Input sequence /sequences that brings the influence of the fault to the gate output Primitive D cubes for s-a-0 at line c a b c
0 0 D Primitive D cubes for s-a-1 at line c c a a b c
1 x D’
x 1 D’ b D=1 fault Free
=0 fault presence
D’ =0 fault free
=1 Fault presence
Slide 19: Rules for Finding Primitive D-Cubes a0 & a1=>singular cube sets for output 0&1
b0& b1 =>corresponding sets in faulty circuit Intersect members of a1 with b0 & b1
with a0 Example : 3 i/p Nand Gate singular cover for nand gate singular cover for faulty gate
(b at s-a-1) a b c d
C1g 0 x x 1
C2g x 0 x 1
C3g x x 0 1
C4g 1 1 1 0 a1 a0 a b c d
C1f 0 x x 1
C2f x x 0 1
C3f 1 x 1 0 b1 b0
Slide 20: C1g 0 x x 1
C2g x 0 x 1
C3g x x 0 1 C3f 1 x 1 0 INTERSECTION c1g ∩ c3f = D’ x 1 D’ c2g ∩ c3f = 1 0 1 D c3g ∩ c3f = 1 x D’ D a1 b0 c4g ∩ c1f =D 1 1 D’ c4g ∩ c2f =1 1 D D’ Primitive D Cube of b s-a-1 fault is 1 0 1 D C1f 0 x x 1
C2f x x 0 1 C4g 1 1 1 0 INTERSECTION a0 b1
Slide 21: 4. D Intersection 3 S-a-0 fault at 2
D cube of fault
1 2 4
0 1 D 3 4 5
0 D’ D Full ckt D cube 1 2 3 4 5
0 1 0 D’ D Tool for building sensitized path Example To transmit fault through G2,
Propagation d cube of G2
must match d cube of fault X1=0,x2=1,x3=0 will sensitize path
from line 2 through 4 to line 5
D Algorithm: : D Algorithm: 1.choose primitive D cube of fault under consideration
2.sensitize all path from faulty gate to primary o/p successive intersection of primitive D cube of fault
with propagation D cube of successor gates
(Procedure called D-drive) 3.D-Drive is continued until a primary o/p has D or D’ 4. Consistency operation
D Algorithm Flowchart : D Algorithm Flowchart Choose primitive
D cube of fault start Sensitize all path
D-drive Consistency operation
Back tracing Test pattern Primary o/p
D or D’ ? yes No
Slide 24: G1 G2 G3 G4 G5
1 2 5 3 4 6 3 5 7 2 6 8 7 8 9
x 1 0 1 0 D 0 x 1 0 D D’ 1 D D’
1 x 0 0 1 D x 0 1 D 0 D’ 0 1 D‘
0 0 1 1 1 D’ 1 1 0 D D D’ D D D’
Singular primitive D singular propagation propagation
cover cube of fault cover D cube D cube example
Slide 25: D drive operation
Select pdcf for 6 s-a-0 1 0 D
Intersect with gate 4 propagation D cube 0 1 0 D D’
Intersect with gate 5 propagation D cube 0 1 0 D 1 D’ D 1 2 3 4 5 6 7 8 9 Consistency operation
Check line 7 at 1 from G3 singular cover 0 1 0 0 D 1 D’ D
set line 5 at 0
Check line 5 at 0 from G1 singular cover 1 0 1 0 0 D 1 D’ D
set primary input at 1 Test - 1010
Slide 26: PODEM
(Path Oriented Decision Making) Set up D or D at the o/p of gate under test
assign 0 or 1 to primary i/p line (pi)
Determine its implication on propagation of D or D if no
inconsistency found select another pi line & assign 0 or 1
Repeat process -- branching
If inconsistency found -- bounding Binary tree – node correspond to pi line
Slide 27: start [ Each pi is initially at X ] I1 0 I3 I2 1 0 1 0 1 Unused alternative
assignment inconsistent inconsistent Initial assignment
recorded as node
in decision tree Binary decision tree
Slide 28: Initial objective: line 5 = 1
Backward tracing and x1=0
1 2 3 4 5 6 7 8 9 10 11 12
0 x x x x x x x x x x x
x1x2x3x4 =0xxx not a test set
Assign x2=0,
1 2 3 4 5 6 7 8 9 10 11 12
0 0 x x D x x x x x x x NOR: 0 0 D o/p S-a-0
x 1 D’ o/p S-a-1
1 x D’ S-a-1
D=1 ckt fault Free
=0 fault presence
D’=0 fault free
=1 Fault presence S-a-0
Slide 29: 00xx not a test set.
find a gate so as to propagate D to o/p
Gate G & H are two option
Selection is gate G ; x3=0
1 2 3 4 5 6 7 8 9 10 11 12
0 0 0 x D x x 0 x D’ x x
000x not a test set.
Propagate D’ through gate J
By backward trace procedure x4=0
Test set = 0000 Podem is efficient in terms of computation time over D- algorithm
Slide 30: Test Generation for Sequential Circuits Converting to one
Dimensional Array of Identical
Combinational Ckts State Table
Verification
Approach single fault in Sequential circuit is equivalent to
multiple faults in iterative combinational circuit (Verify ckt operating in accordance with state table)
Slide 31: Sequential network Iterative model of sequential network Increasing no. of faults for complex ckt make unrealistic
Slide 32: State Table Verification Approach Assumptions for Deriving Checking Sequence:
Network is deterministic i.e. next state is determined uniquely from present state & i/p
Strongly connected i.e. there exist an i/p sequence that transfer n/w from state pi to qi
Fault will not increase no. of state . Given state table , Find an I/O sequence pair (X,Z) such that response of machine to X will be Z if machine is operating correctly.
sequence pair (X,Z) => checking sequence. For designing checking experiment initial state of
machine must be known => distinguishing sequence
Slide 33: Checking Experiment Preset Adaptive Inputs sequence are previously set choice of inputs depends on
o/p of previous experiment Initial uncertainty =>set containing all the states of machine uncertainty vector => Collection of uncertainties homogeneous => components have either single states or
identical repeated states i.e. (AA)(B)(C) trivial => components contain single state each,e.g. (A)(B)(C) Terminology:
Slide 34: Homing Tree: A node become terminal node if
Nodes with non homogeneous components associated with same node at preceding level.
Node associated with a trivial or homogeneous vector. Homing Sequence => I/p sequence whose response by machine uniquely determines its final state regardless of initial state.
Obtained from homing tree
Path from initial uncertainty to a node having trivial / homogeneous uncertainty vector.
Slide 35: Distinguishing Tree: A node become terminal node if
Nodes with non homogeneous components associated with same node in preceding level.
Node associated with a trivial uncertainty.
Node with homogeneous non-trivial component.
all distinguishing sequences are homing sequence but converse is not true Distinguishing Sequence: i/p sequence that applied to machine produce different O/P sequence for each initial state.
Obtain from distinguishing tree.
Slide 36: PS X=0 X=1
A B,0 D,0
B A,0 B,0
C D,1 A,0
D D,1 C,0 PS X=0 X=1
A C,1 D,0
B D,0 B,1
C B,0 C,1
D C,0 A,0 N M homing sequence = 010 (C)(C)(B)(A) distinguishing sequence = 101 state table input input
Slide 37: Transfer Sequence: shortest sequence to transfer machine from state Si to Sj transfer sequence from B to C = 00 PS X=0 X=1
A C,1 D,0
B D,0 B,1
C B,0 C,1
D C,0 A,0 state table input Response of machine M to 101 A 0 0 1 C
B 1 0 0 A
C 1 0 1 B
D 0 1 1 C Initial
state O/P sequence Final state Response of machine N to 010 A 0 0 0 A
B 0 0 1 D
C 1 0 1 D
D 1 0 1 D Initial
state O/P sequence Final state
Slide 38: Synchronizing Sequence : Take machine to specified final state regardless of o/p or initial state Synchronizing Tree: A node become terminal node if
Nodes with non homogeneous components associated with same node at preceding level.
Node associated with uncertainty containing a single element.
Slide 39: PS X=0 X=1
A B,1 C,0
B A,0 D,1
C B,0 A,0
D C,1 A,1 (AC) synchronizing sequence 110 for take it in state b state table Next-state/output input
Slide 40: 1.Initialization Phase: Take machine from unknown initial state to fixed known state by applying homing sequence then transfer sequence or by synchronizing sequence.
2.State Identification Phase: An i/p sequence is applied so as to cause machine to visit each of its state & display its response to distinguishing sequence.
3.Transition Verification Phase : Machine go through every state transition & Every state transition is verified by distinguishing sequence Designing Checking Experiment
Slide 41: PS x=0 x=1 A C,0 D,1
B B,0 A,1
C A,1 B,0
D B,0 C,0 state table homing sequence=00,01,11
distinguishing sequence=11 Initial state response to 00 final state A 01 A
B 00 B
C 10 C
D 00 B Example :
Slide 42: Step 1: taking machine from unknown to state A
response of machine to homing sequence 00
01 => state A
00 => state B A
10 => state C A Initial state final state A 10 C
B 11 D
C 01 A
D 00 B Step2: cause machine to visit each of its state Time 1 2 3 4 5 6 7 8 9 10 11 12
Input 1 1 1 1 1 0 1 1 1 1 1 1
State A C A B D B D
Output 1 0 0 1 1 0 1 1 0 0 1 1 1 0 - Visited all 4 states Response to distinguishing sequence 11 A B
B C
C D
Need 111
Slide 43: Time 1 2 3
Input 0 1 1
state D B D
o/p 0 1 1 Step 3: verifying machine transition with state table transition Time 1 2 3 4
Input 0 1 1 1
state D C
O/p 0 1 1 0 Apply i/p symbol which causes
desired transition & identify it
by distinguishing sequence Whole state table is tested in similar way
Slide 44: Random Testing Procedure
(for complex ckt) Random Testing
without
Test Generation RANDOM
PATTERN
GENERATOR KNOWN GOOD
CIRCUIT(Gold unit) COMPARATOR Random Test
Generation Reliability of known good ckt is not guaranteed CIRCUIT
UNDER
TEST
Slide 45: Random Test Generation INPUT PATTERN
GENERATION
USING LFSR CIRCUIT
UNDER
TEST COMPARISION OF O/P
WITH FAULT-FREE O/P IF DIFFERENT O/P
RETAIN I/P PATTERN AS A TEST SET produce very large test set Combinational ckt can be tested by random inputs by observing characteristics of ckt
Slide 46: Transition Count Testing circuit under test C(z) compared with
original recorded count
at selected test point(s) Total transition1 0 & 0 1 in response sequence
e.g Z=10011010 ,C(z)=5 predetermined
i/p sequence No need to store entire response sequence, only store transition count
Drawback:
Faulty sequence may produce same transition count as good sequence Fault remain undetected
Fault coverage changes with order of applying pattern Need less storage space
Slide 47: S-a-0
Slide 48: Signature Analysis Detects error in data stream caused by hardware faults Signature Generation Using LFSR Clock Start Stop n-bit shift register Xor Unique signatures Feedback from shift register Data stream Reset Shift Register At various node in system Node faulty if Difference in signature at that node
Slide 49: Initial State = 0000 inputs 4-bit Signature Generator State Diagram
Slide 50: Fault Detection Approach Comparison of Recorded Signature of Particular Node
with Signature Obtained 6 bit input sequence S-a-0 S-a-1 Ckt-1
Slide 51: Input values fault-free output faulty output
X1 X2 X3 Z Z Z Z
( α s-a-0) ( β s-a-1) ( α s-a-0
β s-a-1) Data streams 0 0 0 0 0 0 0
at the input & 0 0 1 0 0 0 0
output nodes 0 1 0 1 0 1 0
0 1 1 0 0 0 0
1 1 0 0 0 1 1
1 1 1 1 1 1 1 Register status 1 0 1 0 1 0 1
after six shifts 1 1 1 0 0 1 1
0 1 1 0 0 0 0
0 1 0 1 0 1 0
Signature F 7 P 1 8 5 F Generation of signatures for circuit-1 HP non-standard hexa character set 0-9ACFHPU For easy readability & compatibility with 7-segment display
References : References 1.Fault Tolerant & Fault Testable Hardware Design by P.K.Lala
2.Fault tolerant Computing by D.K. Pradhan
3.Finite Automata & Switching Theory by Zvi Kohavi
4.Digital System & Logic design by Samuel C. Lee
Contribution : Contribution Tarang Agarwal………………….10
S.Karthik…………………………..8
Jail Singh…………………………..7
Tirupati……………………………...7