Fault Simulation and Test
Generation
Dr. E. Papanasam
Associate Professor
SENSE, VIT Chennai
Simulation
• Simulation
• Predicting the behavior of a circuit design before it is physically built
• Simulation
– Logic simulation helps the designer verify that the design conforms to
the functional specifications during the design stage.
– Fault simulation is used to simulate faulty circuits during test
development.
• Logic simulation is generally referred to as fault-free simulation
• Fault simulation is also an important component of automatic test pattern
generator (ATPG) programs.
Logic Simulation
• Logic simulation (design verification) is generally performed at each design
stage
– Ranging from the behavioral down to the switch level
– During each design stage, the design is described in a suitable description
language
• Design verification begins at the behavioral level or electronic system level
(ESL)
– At this level, the behavioral model of the target design is described in ESL
languages such as C/C++, SystemC, and SystemVerilog
Functional verification
• Once the behavioral model has been verified to an acceptable confidence
level, the verification process moves to the register-transfer level (RTL)
design stage
– The circuit at this stage is described in hardware description languages
(HDLs) (Verilog and VHDL ), in terms of blocks
• such as registers, counters, data processing units, and controllers,
as well as the data/control flow between these blocks
• Because ESL/RTL verification usually does not involve detailed timing
analysis, design verification of the ESL or RTL is also referred to as
functional verification
Fault Simulation
Fault Simulation
• Used for the development of manufacturing test
• Normally done after the design has been verified
Tool used to anlayze the quality of test vectors
Input
▪ A circuit netlist
▪ Test set
▪ A fault model
Compute
▪ Fault coverage statistics
▪ Fraction (or percentage) of modeled faults detected by test vectors
▪ Set of undetected faults
▪ Fault coverage = # of detected faults / total # of faults
Motivation
▪ Determine test quality and in turn product quality
▪ Find undetected fault to improve tests
Fault simulation for test generation
Courtesy: M. Bushnell, Vishwani Agrawal
Fault Simulation
• Fault simulation is a more challenging task than logic simulation due to the
added dimension of complexity
• Simulating one fault at a time the amount of computation is
approximately proportional to
– Circuit size, the number of test patterns, and the number of modeled
faults
• Overall time complexity of fault simulation is O(pn2) (# modeled faults is
roughly proportional to the circuit size)
– p test patterns
– n logic gates,
• Infeasible for large circuits
Fault Simulation
• Test vectors (Logic simulation) is preferred. Mostly written by human
designers for design verification
• For fault simulation, the term “test patterns” is used, as the fault
simulators frequently work with ATPG to grade test patterns
• Key fault simulation techniques (single stuck-at fault model)
– Serial, Parallel, Deductive, Concurrent
Applications of Fault Simulation
• 1. Evaluate quality of test sets (aka. Fault Grading)
– Determine fault coverage of a test set
• 2. Automatic Test Pattern Generation (ATPG)
– Identify detected faults and undetected faults
• 3. Diagnosis
– Generate fault dictionary
– Find culprit fault responsible for failure
• Therefore, fault simulators can be used as either
– Stand alone tool, or
• Fault grading
– Embedded tool
• ATPG
• Diagnosis
Fault Sim. Embedded in ATPG
• After each test pattern generation
– fault simulation
• Fault dropping
– Remove detected faults from fault list
– Prevent repeated test generation for detected faults
Serial Fault Simulation
• Simplest fault simulation technique
• Fault-free and faulty circuit simulations
• Fault simulator simulates faults one at a time
• Initially fault-free logic simulation performed on the original circuit and
responses are stored
• For every fault
– Modify good circuit (fault injection) to obtain a faulty circuit
– Run logic simulation on faulty circuit
– Compare faulty outputs with stored good outputs
– Fault is detected if they are different
• After first fault simulation, circuit is restored by removing fault
• This process repeats until all faults in the fault list have been simulated
Serial Fault Simulation
• Advantages
– Easy to implement (regular logic simulator)
– Ability to simulate many fault models (stuck-at, delay, Br, …)
• Disadvantage
– Long CPU time
• Require n(m+1) runs of logic simulation.
– n – Number of test vectors
– m – Number of faults
Serial Fault Simulation
Fault dropping
• Nine simulation runs are performed
– 3 fault-free
– 6 faulty circuit simulations
• Nine simulation runs can be divided into three simulation passes
– In each simulation pass, either the fault-free or the faulty circuit is
simulated for the whole test pattern set
• Simulations of the faulty circuit with fault f for patterns P2 and P3 are
redundant
– Because f is already detected by P1
• Assumption - test patterns are simulated in the order P1, P2, and then P3
• Halting simulation of detected faults known as fault dropping
The serial fault simulation algorithm flow
Parallel Fault Simulation
• Take advantage of the bitwise parallelism inherent in the host computer to
reduce fault simulation time
– 32-bit wide CPU, logic operations (AND, OR, or XOR) can be performed
on all 32 bits at once
• In every pass of simulation 1 fault free and w-1 faulty circuits were
simulated in parallel for a given test vector
• w – Number of bits in a word
• If q faults are to be simulated number of passes required for a vector =
q/w-1
• Bitwise parallelism in fault simulation:
– Parallel fault simulation - Parallelism in faults
– Parallel pattern single fault propagation - Parallelism in patterns
Example of parallel fault simulation
• To simulate the fault-free and
two faulty circuits in parallel,
the signal on each line is
expressed as one word
• The state of the left-most bit
(bit 0) represents the signal
value in the fault-free circuit,
• Middle bit (bit 1) that in the
circuit with c s-a-0
• Right-most bit (bit 2) that in the
circuit with f s-a-1
Fault Injection for Parallel fault simulation
Fault injection for parallel fault simulation
• To force the second bit of Af
to one without affecting the
other two bits, the second
input of Gf is set to be 010.
• Injection of fault f does not
affect the fault-free circuit and
the faulty circuit with fault g.
• Injecting fault g, a stuck-at
zero fault
• Achieved by adding the AND
gate Gg and setting its side
input to be 110
Parallel Fault Simulation
• P1: 010; P2:001; P3:100
Parallel Fault Simulation
• The faulty response of the first pattern is {1, 0, 1}
• Fault f is detected (the second bit) but fault g (the third bit) is not
• Similarly, the outputs of P2 and P3 are {1, 0, 1} and {0, 0, 1}, respectively.
• Three simulations (in one simulation pass) are performed
• Compared to serial fault simulation, which requires nine simulations,
• Parallel fault simulation saves two-thirds of the simulation time.
Parallel-Pattern Fault Simulation
• Aka Parallel-pattern single fault propagation (PPSFP)
• One fault at a time is simulated
• Logic simulations on the fault-free circuit are first performed on the first w
test patterns, and the circuit outputs are recorded
• Then, the faults are simulated one at a time on these w test patterns
• For each fault, the simulation results are compared with the correct
responses to determine if the fault is detected
• Simulation continues until the fault is detected or all the test patterns are
simulated
• The faulty circuit is restored to its original state and the next fault is
processed
• The same procedure repeats until all faults in the fault list are simulated
PPSFP
PPSFP Flowchart
Comparison
• Serial fault simulation: one fault, one pattern
• Parallel fault simulation: multiple faults, one pattern
• PPSFP: multiples pattern, one fault
Deductive Fault Simulation
• Based on logic reasoning rather than simulation
• Identifies, all at once, the faults that can be detected
• Only fault-free simulations have to be performed
• Very fast
• Fault list (Lx) is associated with a signal x
• Lx is the set of faults that causes x to differ from its fault-free value
Fault lists in a deductive fault simulator
Fault lists in a deductive fault simulator
• Fault b0 is present at both
inputs of the OR gate
• This fault will invert both inputs
and the output of the faulty
circuit will remain 1, the same
as the fault-free output
• That is why b0 is absent from Lg
• This completes the fault
propagation
• Input vector (1,1) detect four
faults, a s-a-0, c s-a-0, e s-a-0,
and g s-a-0
Deductive fault simulation w.r.t P1 (010)
• Fault A/1 appears in LA because its presence causes the value of primary
input A to deviate from its correct value of zero
• Fault A/0 is not in the fault list because the value of A remains correct
when the fault A/0 is present
Fault list propagation
• The process of deriving the fault list of a gate output from those of the gate
inputs
• Based on logic reasoning
• Fault list of gate output E is the union of the fault list of B and the E/0 fault
• E/0 fault should be included in LE as the correct value of E is one
• LC is not propagated to the gate output because the other input B holds
the controlling value (one) of gate G1
• Fanout branches do nothing but add faults L/0 and F/0 to LL and LF,
respectively
• Pattern P1 detects the seven faults in LK
• All faults detected by a test pattern are obtained in one fault list
propagation pass
Deductive fault simulation w r. t. P2 (001)
Deductive fault simulation w r. t. P3 (100)
Fault Coverage = 11/18 = 61%
Deductive Fault Simulation Flowchart
Concurrent Fault Simulation
• Event driven simulation - both good and bad events simulated at the
same time
• Every gate has a concurrent fault list, consists of a set of bad gates
• Bad gate
– an imaginary copy of gate x in the presence of a fault
– Contains a fault index and the associated gate I/O values in the
presence of the corresponding fault
• Local faults - faults on the inputs or outputs of gate x
• Initially, the concurrent fault list of gate x contains local faults of gate x.
• As the simulation proceeds, the concurrent fault list contains both local
faults and faults propagated from previous stages
• Local faults of gate x remain in the concurrent fault list of gate x until they
are detected
Fault-lists (bad-gates) in concurrent
fault simulation
Fault-lists (bad-gates) in concurrent fault
simulation
• All single stuck-at faults are concurrently simulated
• a0 - fault a s-a-0
• bad-gates are attached in a linked-list structure
• At least one value around a bad-gate differs from the good-gate and the
difference is caused by the corresponding fault
• At the primary output g, any bad-gate whose output differs from that of
the good-gate indicates fault detection
• Faults a0, c0, e0 and g0 are detected (bad-gate output differs from that
of the good-gate)
Deductive Vs Concurrent Simulation
• Deductive simulator
– Fault-list is for a signal
– Contains only the faults that affect (or are detected at) that signal
– Fault lists are dynamically created at run time and their sizes are difficult
to predict prior to simulation
– Memory requirement can be a problem
• Concurrent simulator
– Fault-list is for a gate
– Even faults that affect the inputs of that gate are included in the list.
– Fault-lists are comparatively longer
– Has more severe memory problems
Concurrent Fault Simulation w r t P1 (010)
• Assume three faults
– A stuck-at one (A/1)
– C stuck-at zero (C/0)
– J stuck-at zero (J/0)
• The fault list of G1, G2, and G3
initially contains their local faults:
C/0, A/1, and J/0
• The bad gates C/0 and J/0 are
both invisible
– Faulty output is the same as
the good output
– They are not propagated to
the subsequent stages
Concurrent Fault Simulation w r t P1 (010)
• Bad gate A/1 becomes visible (Its faulty output is different from the good
output)
• Visible bad gate A/1 creates a bad event u → 1 on net H (in gray)
• A new copy of bad gate A/1 is added to the concurrent fault list of G4 (it
has one input different from the good gate)
• Fault A/1 is detected because the faulty output K is different from the
good output
• At this time, we could drop detected fault A/1
Concurrent fault simulation P2 (001)
Concurrent fault simulation P2 (001)
• The bad gate C/0, invisible in pattern P1, now becomes newly visible
• Newly visible bad gate creates a bad event—net E falls to zero, which in
turn creates two divergences in G2 and G3
• G2 invisible but G3 creates a bad event—net J rises to one
• Finally, the concurrent fault list of G4 contains two bad gates
• Both faults A/1 and C/0 are detected
Concurrent fault simulation P3 (100)
Concurrent fault simulation
• A bad gate converges to its good gate
– if it is not a local fault &
– its I/O values are identical to those of the good gate.
• Similarly, the other bad gates of C/0 also converge to G2 and G4.
• Note that bad gate C/0 does not converge to G1 because it is a local fault
for G1.
• Bad gate J/0 newly visible.
• The newly visible event (in gray) is propagated to G4 and a new bad gate
J/0 diverges from G4.
• Fault J/0 is detected by pattern P3
Event processing and convergence in
concurrent fault simulation
Concurrent fault simulation flowchart
TEST GENERATION
• Task of producing an effective set of vectors
• Achieve high fault coverage for a specified fault model
• The objective
– Produce a set of test vectors that will uncover any defect in a chip
• High-level concept of test generation
TEST GENERATION
• Without powerful ATPGs, chips will increasingly depend on design for
testability (DFT) techniques to alleviate the high cost of generating vectors
• DFT would no longer be necessary
– if the ATPG engine is capable of delivering high-quality test patterns
that achieve high fault coverages and small test sets,
• Test vector abc = 001
• Fault targeted = d/1, a/1, b/1, c/0
Test Generation
• Random test pattern generation
– no target fault
• Deterministic test pattern generation
– one target fault at a time
• Deterministic Test Pattern Generation
– Boolean difference*
– Path sensitization**
– D-Algorithm (1965)**
– PODEM (1981)**
– FAN(1985) **
– SAT-based (1992)*
*Boolean-based methods **path-based methods
Path sensitization
• No need to know Boolean expression
– we can find a test from circuit netlist
• Fault activation: Assign gate inputs to generate appropriate value at fault
site (H) A=0
• Sensitization: Assign side-inputs to non-controlling value to propagate fault
effect forward J=0
• Justification: Assign primary inputs to achieve desired values
Path Sensitization Method
Single path sensitization (SPS) Algorithm
• 1. Activation, fault excitation: Specify inputs so as to generate the appropriate
value at fault site for fault excitation (I.e. set S to 1 for S-stuck-at-0 fault)
• 2. Error propagation: specify additional signal values to propagate the fault effect
from the fault site to the outputs/observation points
• 3. Line justification: Specify input values so as to produce the signal values
specified in (1) or (2)
– If justification fails, backtrack.
• 4. Value implication: unique determination of values at other signals due to value
assignments made in (1), (2), or (3)
Example
• (1) Fault activation : A = B = C = 1
• (2) Error propagation: through G5 or G6
– (a) Propagating through G5 requires G2 = 1 ⇒ A=D=0 ⇒ Justification fails
– (b) Propagating through G6 requires G4 = 1 ⇒ C=1, E=0 ⇒ justification
succeeds
– Test ABCDE=(111x0)
Single path sensitization (SPS)
• Pros
– Easy to implement
– No Boolean equation needed
• Cons
– Too many paths to choose, which one is correct?
– Single-path sensitization not enough to detect all faults
Example 2
• E s-a-1 ⇒ E =0
• C = D = 1 to propagate through G1.
• To propagate G4, need G2 = G3 = 1
• Attempt to line justify G2 = G3 = 1
• – G3 = 1 possible
if A = F = 1 or B = H = 1
• If A = F = 1 ⇒ inconsistency since C
= 1 so G2 = 0. ⇒ Therefore, G3 = 1
⇒B=H=1
• – G2 = 1 need A = 0 or F = 0 ⇒
• Tests are ABCDEFH = (0111011 or
1111001 or 0111001)
Completeness of ATPG Algorithms
• A test generation algorithm is deemed complete iff
– find a test for a fault if exists or
– prove that there exists no test, given sufficient time
– Complete algorithms can identify untestable faults
• Major complete algorithms for comb. ckts –
– D-algorithm (Roth, 1966)
– PODEM (Goel, 1981)
– FAN (Fujiwara, 1983)
– Socrates (Schulz, 1988)
– Boolean-SAT-based ATPG (Larrabee, 1992)
Example
Single Path Sensitization is NOT Complete
• d s-a-0 : ⇒ A = B = 1
• Propagate along G3, G6
• Requires C =1, G2 = G4 = G5 = 1
• C =1 => G2 =1
• For G4 = 1 either E = 0 or G1 = 0
• E = 0, B = 1 ⇒ G5 = 0 ⇒ justification
fails
• Propagate along G4, G6 ⇒ E = 1 &
G2 = G3 = G5 = 1
• For G3 = 1 require either C or G1 =0
• C=0 makes G2=0 justification fails
• SPS algorithm fails
Multiple Path Sensitization
• This fault requires multiple path sensitization
• Both two paths {G3-G6} and {G4-G6} are sensitized
– Error is propagated along both paths simultaneously
– G2 = G5 = 1 , c = e = 1
– Test generated successfully
Boolean Difference Method
• Let the target fault be the stuck-at-0 fault on primary input y
Boolean Difference Method
• f = xy+y’z
• f' = f(y = 0) (f’ faulty circuit with the fault y/0)
• Any input vector that can make f ⊕ f’ = 1 can distinguish the faulty circuit
f’ from the fault-free counterpart f
• The logic value on primary input y must be logic 1 to excite the fault y/0
• y · f(y = 1) ⊕ f(y = 0) = 1
• f(y = 1) ⊕ f(y = 0) => XOR operation on two functions f(y =1) and f(y = 0)
• Evaluates to logic 1 if and only if two functions evaluate to opposing values
– In terms of ATPG, this is synonymous to propagating the fault effect at
node y to the primary output f
• Therefore, any input vector on primary inputs x, y, and z that can satisfy
above equation is a valid test vector for fault y/0
Boolean Difference Method
• Two vectors xyz = (110, 011) are candidate test vectors for fault y/0
• f(y = 1) ⊕ f(y = 0) is called the Boolean difference of f with respect to y
Untestable Faults
• Let the fault is z/0
• There exists no input vectors that can satisfy z · df/dz = 1
• The fault z/0 is untestable
D-Algebra
• Five-valued logic: 1, 0, D, D’, X
– D = 1/0
• 1 in fault-free circuit and 0 in the faulty circuit
– D’ = D = 0/1
• 0 in fault-free circuit and 1 in the faulty circuit
– x means “ not yet specified” in ATPG
D-Algebra
D Algebra
D-frontier, J-frontier
• D-frontier : a set of gates whose output value is currently x,
– but have one or more D (or D’) at their inputs
• J-frontier: a set of gates whose output value is assigned
– But input values have not been decided yet
Primitive D-Cubes for a Fault (PDCF)
• Specify minimal input conditions to produce error at gate
output
– Used in fault activation
• Example:
• AND gate output stuck-at faults:
– Stuck-at-0 fault: 11D
– Stuck-at-1 fault: 0xD’ and x0D’
Propagation D-Cube (PDC)
• Minimum gate input assignments required
– to propagate a D or D’ from gate input(s) to gate output
• Used in D-Drive or implication
Implication
• Forward Implication
– partially (or fully) specified input values uniquely determines the
output values.
• Backward Implication
– knowing the output values (and some input values) can uniquely
determine the un-specified input values
• Implication means NO choice
• Implication can be done any time a decision is made
Justification
• Definition: find a valid primary input assignment for desired values
• Justification is easy inside a fanout-free circuit
• No decision needed
– Always finds an answer
• Justification may fail
– when there are fanout branches
D-Algorithm Example
D-Algorithm Example 2
D-Algorithm Example 2
D-Algorithm Example 2
Merits and Demerits of D-Alg.
• D algorithm is complete ATPG
– Guarantee to generate a pattern for a testable fault
• Large search space
– Assignment of values is allowed for internal signals
– Backtracking could occur at each gate
– Very large search space
Sequential ATPG
• Time-frame expansion methods
– The extended D-algorithm
– 9-valued D algorithm
– EBT
• IDEA:
• Replicate circuits and connect time frames by wires
– yi= “states”; No FF!
– Replace clock cycles by space
• Becomes combinational ATPG problem
• Target fault appears in every time frame
Time-frame expansion methods
Extended D-Algorithm
• Select a target fault f
• Create a copy of the combinational logic, set it to time frame 0
• Generate a test for f for time frame 0 using D-algorithm
• If the fault effect is propagated to the FF’s, continue fault effect
propagation in the next time frame
• If there are values required in the FF outputs, continue the justification in
the previous time frame
Extended D-Algorithm
• Fault effect propagate to FF
Extended D-Algorithm
• Fault effect propagation to time frame 1
Extended D-Algorithm
• Fault activation back to time frame -1
Example
• Generate a test for stuck-at zero fault in sequential circuit
Answer
• No way to propagate
– This fault is untestable by sequential ATPG
• Endless timeframe expansion …
– Memory explosion
Summary of Sequential ATPG
• Time and space consuming
• Low fault coverage
• Time-frame expansion methods - extended D-algorithm
• Replicate circuits into many time frames
• Propagate forward, the then activated backward
• create new time frame if needed
• In comb. ATPG, first fault activation, then propagation
• In seq. ATPG, first propagation, then activation
UNTESTABLE FAULT IDENTIFICATION
• Untestable faults
• Faults for which there exists no test pattern that can both
– excite the fault and propagate its fault-effect to a primary output
• a fault may be untestable for any of the following three reasons:
– The conditions necessary to excite the fault are not possible.
– The conditions necessary to propagate the fault-effect to a primary
output are not possible.
– The conditions for fault excitation and fault propagation cannot be
simulta neously satisfied.
UNTESTABLE FAULT IDENTIFICATION
• From an ATPG’s point of view, the presence of untestable faults in a design
can degrade the performance of the ATPG tool.
• When considering untestable faults, an ATPG engine must exhaust the
entire search space before declaring such faults as untestable.
• Thus, the performance of ATPG engines (awa fault-simulators) can be
enhanced if knowledge of untestable faults is available a priori.
UNTESTABLE FAULT IDENTIFICATION
• Benefits of untestable fault identification:
– The presence of an untestable fault can potentially prevent the
detection of other faults in the circuit
– Untestable faults may result in unnecessary yield loss in scan-based
testing.
• This is because even though the circuit remains fully operational in
the presence of untestable faults, scan-based testing may detect
such faults and reject the chip.
– Untestable faults in the form of redundancies increase the chip area;
– They may also increase the power consumption and the propagation
delays through a circuit
References
• Laung-Terng Wang, Cheng-Wen Wu, and Xiaoqing Wen, VLSI Test
Principles and Architectures, The Morgan Kaufmann, 2013
• [Link]