# 3.TEST GENERATION

Views:

Category: Education

## Presentation Description

No description available.

By: ramanaidu1 (45 month(s) ago)

please send me the softcopy of this presentation. I am presently professor.ramanaidu.gangu@aec.edu.in

By: linusrayappa (51 month(s) ago)

By: linusrayappa (51 month(s) ago)

please allow me to download the ppt. this will help me to guide the pg students. thank you

By: aravind5000 (59 month(s) ago)

By: kmanjunathk (61 month(s) ago)

please send me the softcopy of this presentation. I need to prepare foe the M. TECH course. I am presently professor.

See all

## Presentation Transcript

### 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: 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

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