3.TEST GENERATION

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