SRI RAMAKRISHNA ENGINEERING COLLEGE

VATTAMALAIPALAYAM, N.G.G.O. COLONY POST,

COIMBATORE – 641 022.

Module 2
Test Generation -Part 1

Combinational Circuits – Test Generation

 Review of Functional and
Structural testing

8/9/2025 Testting of VLSI Circuits 2

 Functional Testing

• Functional testing verifies the function of the circuit or gate for its
correctness.
• For eg, consider a 25 input Bitwise AND gate

8/9/2025 Testting of VLSI Circuits 3

 Functional testing

8/9/2025 Testting of VLSI Circuits 4

 Structural Testing

8/9/2025 Testting of VLSI Circuits 5

 Structural Testing - Example

No. of test patterns required = 6. 25 = 160

which is much smaller than that of functional
Testing.
Time required for testing by using 1 MHz
tester is .000016 sec and for a million samples
is 16 seconds.

Structural testing is highly

beneficial over functional testing

8/9/2025 Testting of VLSI Circuits 6

 Structural Testing - Penalties

Efficient structural testing is the one with less no. of on-chip

components and yet maintaining the quality of test solution.
Structural testing with fault models is the answer to the
requirement.
8/9/2025 Testting of VLSI Circuits 7
 Structural Testing with fault models

8/9/2025 Testting of VLSI Circuits 8

 Types of Fault Models

8/9/2025 Testting of VLSI Circuits 9

 Comparison of Functional testing and Structural
testing

8/9/2025 Testting of VLSI Circuits 10

 Automatic Test Pattern Generation
(ATPG)

• Test generation is the bread-and-butter in VLSI Testing

-Efficient and powerful ATPG can alleviate high costs of DFT
- Goal: generation of a small set of effective vectors at a low
computational cost
• ATPG is a very challenging task
- Exponential complexity
- Circuit sizes continue to increase - Aggravate the complexity
problem further
- Higher clock frequencies -Need to test for both structural and delay
defects

8/9/2025 Testting of VLSI Circuits 11

 Test Generation Methods

Major Classification
1. Exhaustive Testing
• Apply 2n patterns to an n-input combinational circuit under test (CUT)
• Guarantees that all detectable faults in the combinational circuits are detected
• Test time maybe be prohibitively long if the number of inputs is large
• Feasible only for small circuits
2. Pseudo-exhaustive Testing
• Partition circuit into respective cones
• Apply exhaustive testing only to each cone
• Still guarantees to detect every detectable fault
Test Generation methods discussed
1. Path sensitization Method
2. D-algorithm
3. PODEM algorithm

8/9/2025 Testting of VLSI Circuits 12

 Path Sensitization Method

Basic steps:
1. Fault activation/sensitization/excitation :Specify inputs so as to generate the
appropriate value at fault site for fault excitation . (ie., set S to 1 for
Stuck-at-0 fault and set S to 0 for stuck-at-1 fault)

2. Fault 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)

4. Value implication: unique determination of values at other signals due to

value assignments made in (1), (2), or (3)

8/9/2025 Testting of VLSI Circuits 13

 Example 1

G4

G3=0,E=0

8/9/2025 Testting of VLSI Circuits 14

 Example 2

8/9/2025 Testting of VLSI Circuits 15

 Completeness of ATPG Agorithms

8/9/2025 Testting of VLSI Circuits 16

8/9/2025 Testting of VLSI Circuits 17
 D-Algorithm

8/9/2025 Testting of VLSI Circuits 18

 D Algorithm

• Use D-algebra
• Activate fault
• Place a D or at fault site
• Do justification, forward implication and consistency check for all
signals
• Repeatedly propagate D-chain toward POs through a gate
• Do justification, forward implication and consistency check for all
signals
• Backtrack if
• A conflict occurs, or
• D-frontier becomes a null set
• Stop when
• D or D at a PO, i.e., test found, or
• If search exhausted without a test, then no test possible

8/9/2025 Testting of VLSI Circuits 19

 D-algorithm contd.,

1) Select a primitive D-cube of the fault

2) Implication and checking for inconsistency.
- If inconsistency occurs, go to (1).
3) D-drive: selects an element in D-frontier & attempts to propagate D or ( or D’) in
its inputs to its output.
- D-frontier consists of set of all elements whose output values are unspecified but
inputs have some signals with D or D’.
- D-drive is done by intersecting the test cube with a propagation D-cube of the
selected element.
- Backtrack, i.e. select another propagation D-cube, if intersection is null.
4) Implication of D-drive: perform implication for the new test cube.
5) Repeat 3) & 4) until faulty signal propagated to an output.
6) Line justification: Consistency check on input conditions required.

8/9/2025 Testting of VLSI Circuits 20

 Definitions of terms in D-algorithm

Singular cover
• Singular cover of a logic gate is basically a compact version of the truth table
using don’t care inputs X which may be either 0 or 1.
Primitive D-cubes
• Specifies the minimal input conditions which must be applied to a logic element
E in order to produce an error signal at the output of E.
Propagation D-cubes
• The propagation D-cubes of a logic element E specify minimal input conditions
which are required to propagate an error signal on an input (or inputs) to the
output of that element.

Testting of VLSI Circuits 21

8/9/2025
 Definitions

• Justification: Changing inputs of a gate if the present input values do not

justify the output value.
• Forward implication: Determination of the gate output value, which is X,
according to the input values.
• Consistency check: Verifying that the gate output is justifiable from the values
of inputs, which may have changed since the output was determined.
• D-frontier: Set of gates whose inputs have a D or D’, and the output is X.

8/9/2025 Testting of VLSI Circuits 22

 Singular Cover

• A singular cover of a logic gate is the compact version of the truth table using
don’t care inputs X, which may be either 0 or 1. Each row in a singular cover is
called a singular cube.
• Used for:
• Line justification: determine gate inputs for specified output.
• Forward implication: determine gate output

a Singular
b a b c
c Truth Table covers
a b c
SC-1 0 X 1
0 0 1
0 1 1 SC-2 X 0 1
1 0 1
1 1 0 SC-3 1 1 0
8/9/2025 Testting of VLSI Circuits 23
 Propagation D-cubes (PDC)

• Used for D-drive (propagation of D through gates) and forward

implication.
• PDC consists of a table for each circuit element which has entries for
propagating faults on any one of its inputs to the output.
• To generate PDC entry corresponding to any one column, D-intersect any
two rows of SC which have opposite vales(0 & 1) in that column.
• For ex, consider a AND gate

• SC : ab c To find pdc for a, consider c1 and c3 intersection

c1 0X0 pdc : D’ 1 D’
c2 X00 Similarly for b, consider c2 and c3
c3 111 pdc ; 1 D’ D’

8/9/2025 Testting of VLSI Circuits 24

 D- intersection

A circuit node can take any value. D-intersection specifies the intersection of two
node values

∩ 0 1 X D D
Undefined
State
0 0 D’ 0

1 D 1 1
D (conflict)
X 0 1 X D so, not
allowed
D D D
D D D

8/9/2025 Testting of VLSI Circuits 25

 Propagation D-cubes -example

• Consider a 2-input NAND gate

•
a
b Propagation D-cube : Form
c
intersection of opposite outputs in singular
Singular cover
a b c
covers

SC-1 0 X 1 0X1 ∩ 110 = D’1D

X01 ∩ 110 = 1D’ D
SC-2 X 0 1

SC-3 1 1 0

8/9/2025 Testting of VLSI Circuits 26

 Primitive D-cubes

• Primitive D cubes are used to specify the existence of a given fault.

• It consists of an input pattern that brings the influence of a fault to the output of
the gate.
• For ex., if the output of a 2-input NOR gate is s-a-0, then the corresponding
primitive D-cube of the fault is 00D. Here D is interpreted as1 for fault-free
gate and 0 for faulty gate.

• Similarly for s-a-1 fault at the output of NOR gate, primitive D cubes are
1XD’ ; X1D’

8/9/2025 Testting of VLSI Circuits 27

 D-algorithm contd.,

8/9/2025 Testting of VLSI Circuits 28

 Example

8/9/2025 Testting of VLSI Circuits 29

8/9/2025 Testting of VLSI Circuits 30
8/9/2025 Testting of VLSI Circuits 31
8/9/2025 Testting of VLSI Circuits 32
8/9/2025 Testting of VLSI Circuits 33
8/9/2025 Testting of VLSI Circuits 34
8/9/2025 Testting of VLSI Circuits 35
 Path Oriented Decision Making
(PODEM)

8/9/2025 Testting of VLSI Circuits 36

8/9/2025 Testting of VLSI Circuits 37
8/9/2025 Testting of VLSI Circuits 38
 Flow Chart for PODEM

8/9/2025 Testting of VLSI Circuits 39

 Steps in PODEM

8/9/2025 Testting of VLSI Circuits 40

 Flow Chart of Backtrace

8/9/2025 Testting of VLSI Circuits 41

 Example

8/9/2025 Testting of VLSI Circuits 42

8/9/2025 Testting of VLSI Circuits 43
 Cost of ATPG

8/9/2025 Testting of VLSI Circuits 44

 Testable Combinational Logic circuit design

• A logic circuit is considered to be testable if it is easy to generate a set of

test patterns to achieve high fault coverage in the circuit..
Reed-Muller Expansion Technique
This technique can be used to design any arbitrary n-variable Boolean
function using AND & XOR gates only. The circuit so designed has the
following properties.
Properties :
1. If the primary input leads are fault-free, then at most n+4 tests are
required to detect all single stuck-at faults in the circuit.
2. If there are faults on the primary leads as well, then the number of tests
required is (n+4)+2nc, where nc is the no. of input variables that appear
even no. of times in the product terms of Reed-Muller expansion.

8/9/2025 Testting of VLSI Circuits 45

• But, by adding an extra AND gate with its output being made
observable, the additional 2n tests can be removed. The input to the
AND gate are those inputs appearing an even number of times in the
Reed-Muller expansion.
• Any combinational function of n variables can be described by a
Reed-Muller expansion of the form

8/9/2025 Testting of VLSI Circuits 46

• For a three-variable function, the Reed-Muller expansion is

• The constants Ci may be computed by using the following properties of

XOR operation:

• Example: To illustrate, consider the Boolean function

8/9/2025 Testting of VLSI Circuits 47

• A direct implementation of the function is shown in Fig.1.

8/9/2025 Testting of VLSI Circuits 48

• To detect a single faulty gate in a cascade of XOR gates, it is sufficient to apply a set of
test inputs that will exercise each XOR gate for all possible input combinations.
• Such a test set for the circuit in Fig.1 is

• The structure of the test is always the same independent of the no. of input variables, and
constitutes 4 tests only. For ex, a 5 variable circuit would have the test set

8/9/2025 Testting of VLSI Circuits 49

8/9/2025 Testting of VLSI Circuits 50
Sequential Circuits – Test Generation

8/9/2025 Testting of VLSI Circuits 51

 Sequential Circuits

• A sequential circuit has memory in addition to combinational logic.

• Test for a fault in a sequential circuit is a sequence of vectors, which
• Initializes the circuit to a known state
• Activates the fault, and
• Propagates the fault effect to a primary output
• Methods of sequential circuit ATPG
• Time-frame expansion methods
• Simulation-based methods
• Additionally, circuits with gated clocks and multiple clocks
present unique challenges in test generation.
 Time Frame Expansion

• This method essentially unrolls the sequential circuit into

multiple combinational circuits, one for each time frame.
• Automatic Test Pattern Generation (ATPG) tools, typically
used for combinational circuits, can then be applied to this
expanded structure.
• It is efficient for circuits described at the gate level but can
become computationally expensive for complex circuits
with cyclic structures, multiple clocks, or asynchronous
logic.
• The sequential depth (number of time frames) needed
depends on the circuit's characteristics and the type of faults
being targeted.
8/9/2025 Testting of VLSI Circuits 53
 Example – Serial Adder

A Bn
n
1 1
s-a-0
D
1

1 D
X

Combinational logic 1
S X
n
FF

Copyright 2001, Agrawal & Bushnell

 Concept of Time Frames

• If the test sequence for a single stuck-at fault contains n vectors,

• Replicate combinational logic block n times
• Place fault in each block
• Generate a test for the multiple stuck-at fault using
combinational ATPG with 9-valued logic
vector : 0 to n-1
Reverse direction : (-(n-1)) = -n+1
Vector – n +1 Vector – 1 Vector 0
Fault

Unknown Time- State Time- Time-

or given Frame variables frame frame
Init. state - n+1 -1 0
Comb.
block PO – n +1 PO – 1 PO 0
 Time Frame Expansion

An-1 Bn-1 An Bn
Time-frame -1 Time-frame 0
1 1 1 1
s-a- D s-a-
X D D
0 0
1 1
1 D X D
Cn 1 1
Cn+1
X
1
Combinational Combinational
logic Sn-1 logic Sn
X
D

FF

Copyright 2001, Agrawal & Bushnell

 Nine-Valued Logic D-Algorithm
(Muth, IEEE TC, June 1976)

• 9- valued logic : values under fault-free/faulty conditions , so for values

0,1 and X , we have 9 possibilities.
• Ordered pairs of states of the fault-free and faulty circuits (0/0, 0/1, 0/X,
1/0, 1/1, 1/X, X/0, X/1, X/X) are used
• A superset of the five values (0=0/0, 1=1/1, X=X/X, D=1/0, D=0/1) used
in the D-Algorithm
• Take into account the possible repeated effects of the fault in the
iterative array model
 Nine valued logic

A 0 faulty A X
Good
s-a-1
s-a-1
0/1 X/1
X 0/X 0/X
FF1 FF1

X 0/1 X/1
FF2 FF2

B X B 0/1
 Implementation of ATPG

• Select a PO (primary output) for fault detection based on

drivability analysis.
• Place a logic value, 1/0 or 0/1, depending on fault type and
number of inversions.
• Justify the output value from PIs, considering all necessary paths
and adding backward time-frames.
• If justification is impossible, then use drivability to select another
PO and repeat justification.
• If the procedure fails for all reachable POs, then the fault is
untestable.
• If 1/0 or 0/1 cannot be justified at any PO, but 1/X or 0/X can be
justified, then the fault is potentially detectable.
Summary: Test Complexity is high for sequential circuits
 Simulation-Based Test Generation

• This approach uses a fault simulator and a test vector

generator to derive test patterns.
• Fault simulation involves simulating the circuit with both
fault-free and faulty versions to identify test vectors that can
distinguish between them.
• This method can handle circuits modeled at various levels
(e.g., RTL, transistor) and is less sensitive to the circuit's
complexity compared to time frame expansion.
• Simulation-based techniques often involve techniques
like fault injection and distance-based cost functions to guide
the test generation process.

8/9/2025 Testting of VLSI Circuits 60

 Gated Clocks and Multiple Clocks

• Gated clocks:
These are achieved by inserting logic to selectively enable or
disable the clock signal, often to reduce power consumption by
minimizing switching activity. Testing gated clock circuits
requires special considerations to ensure that the clock gating
logic itself is functioning correctly.
• Multiple clocks:
Circuits with multiple, independently operating clock domains
introduce complexities in timing analysis and test
generation. Time frame expansion becomes more challenging,
and simulation-based methods may be preferred.

8/9/2025 Testting of VLSI Circuits 61

 Gated Clocks
• Concept: Clock gating is a technique used to reduce power
consumption by disabling (gating) the clock signal to certain parts
of the circuit when they are not needed.
• Testing Challenges: Gated clocks introduce additional
complexity, as the clock signal is not always present, and the
behavior of the circuit under different clocking scenarios needs to
be verified.
• Testing Strategies:
– Simulation-based verification: Simulating the circuit under various
clock gating scenarios, including different clock enable conditions, to
ensure correct functionality and avoid unintended behavior.
– Static Timing Analysis: Analyzing the timing behavior of the circuit
with gated clocks to ensure that no timing violations occur due to the
gating logic.
8/9/2025 Testting of VLSI Circuits 62
 Multiple Clocks
• Concept: Modern designs often utilize multiple clock domains,
each operating at different frequencies or phases, to optimize
performance.
• Testing Challenges: Interactions between different clock domains
can lead to complex synchronization issues and potential timing
problems.
• Testing Strategies:
– Clock Domain Crossing (CDC) analysis: Verifying that data
transfer between different clock domains is handled correctly,
avoiding metastability and other synchronization issues.
– Simulating different clock scenarios: Testing the circuit with
various clock combinations, including simultaneous clock
pulses and sequential clock applications, to ensure robustness.
8/9/2025 Testting of VLSI Circuits 63
 Summary

• Time-frame expansion and simulation-based methods

provide frameworks for testing sequential circuits,
specific techniques are needed to address the
complexities introduced by gated clocks and multiple
clock domains. These include careful design of clock
gating logic, DFT-aware design practices, and strategies
for handling CDC issues and clock skew during test
generation.
• Special design for testability (DFT) techniques like scan
chain reordering and the insertion of lockup latches help
manage clock skew and improve test coverage.
8/9/2025 Testting of VLSI Circuits 64