stg1.

Chapter 4: Sequential Test

Pattern Generation
Cheng-Wen Wu 吳誠文

Lab for Reliable Computing

Dept. Electrical Engineering
National Tsing Hua University

Outline

• Issues in sequential circuit testing

• ATPG approaches
• Time-frame expansion
• Simulation-based approach
• Functional testing

stg1.9 Cheng-Wen Wu, NTHU 2

Cheng-Wen Wu, LARC, NTHU 1

 stg1.9

Issues in Sequential Circuit Testing

• Exhaustive testing requires > 2n tests (sensitive to
the order of tests)
• Testing requires a sequence of test vectors
• Requires initialization of the machine, which may
be difficult:
− Long initialization sequence, simulator limitations,
invalid state justification, etc.
• Faults may cause the number of internal states to
grow
• Have to cope with the harder-to-detect delay
faults (timing errors)

stg1.9 Cheng-Wen Wu, NTHU 3

Sequential ATPG Approaches

1. Time-frame expansion: convert time domain into
space domain and use combinational ATPG
2. Simulation-based approach: search for test
vectors guided by cost functions and simulations
3. Checking experiment: formal approach to derive
test sequence for FSM
4. Scan: modify the circuit to facilitate combinational
ATPG
5. Functional test: testing that a (part of a) system
operates correctly in a functional sense

stg1.9 Cheng-Wen Wu, NTHU 4

Cheng-Wen Wu, LARC, NTHU 2

 stg1.9

Time Frame Expansion

x y (state)

Combinational State
Logic Vector

z Y (excitation)

x(0) x(1) x(2)

y(0) Y(1) y(1) Y(2) y(2)

C/L pFF C/L pFF C/L pFF

Time frame 0 Time frame 1 Time frame 2

z(0) z(1) z(2)

stg1.9 Cheng-Wen Wu, NTHU 5

Extended D-Algorithm
1. Select a target fault f
2. Create a copy of C/L; time-frame = 0
3. Generate a test for f by D-algorithm for time-
frame 0
4. If fault effect is propagated to FFs, continue
propagation in the next time-frame
5. If there are values required in FFs, continue
justification in the previous time-frame

stg1.9 Cheng-Wen Wu, NTHU 6

Cheng-Wen Wu, LARC, NTHU 3

 stg1.9

Extended Backtrace (EBT) Algorithm

1. Select a path from the fault site to a PO
/* May involve several time-frames. */

2. Sensitize the path backwards from the PO to the

fault site /* Justification is done in the same direction. */
3. If it fails, select another path; if there is no path
left, select another PO; go to 2
4. Justify the required value at the fault site
• Only 2 time-frames needed
• Easier to identify cycles
• Only a single path is selected each time
• Number of paths from fault site to POs can be large

stg1.9 Cheng-Wen Wu, NTHU 7

Back Algorithm
1. Calculate controllability for the fault-free circuit
2. Pick a target fault; calculate controllability measures for
the faulty circuit
3. Derive drivability measures
4. Assign a D/D’ to a PO; time-frame = 0; if all POs with
finite drivability have been considered, go to 2 (fault
undetectable)
5. Justify all values---use drivability to guide the search
¾ May involve several time-frames backwards, and
backtracking on the decisions and time-frames
¾ May need to back up to step 4
¾ Sensitized paths are created implicitly
stg1.9 Cheng-Wen Wu, NTHU 8

Cheng-Wen Wu, LARC, NTHU 4

 stg1.9

Simulation-Based Approach: CONTEST

• A concurrent test generator for sequential circuits—using
a concurrent fault simulator which automatically analyzes
races and oscillations.
Initialization:
Initialization
1 Start with an arbitrary vector
and all FFs in unknown state;
2 Generate new vectors to reduce
cost by 1-bit changes in the
present vector;
/*cost=#FFs in unknown state*/
3 Stop when cost drops below
desired value;

stg1.9 Cheng-Wen Wu, NTHU 9

CONTEST
Tests for concurrent targets:
targets
1 Start with initialization
vectors;
2 Fault simulate vectors and
remove detected faults;
3 Compute cost function for the
last vector;
/* cost(untested f.) = min dist of
its effect from an o/p; cost(vector)
= sum of costs of all untested f. */
4 New vectors = those 1-bit
changes that reduce vector cost;
stg1.9 Cheng-Wen Wu, NTHU 10

Cheng-Wen Wu, LARC, NTHU 5

 stg1.9

CONTEST
Tests for remaining single faults:
faults
1 Revise the cost function;
/* cost = K x activation cost +
propagation cost; activation cost =
dynamic controllability of faulty
line; propagation cost = min dynamic
observability of faulty line; K is a
large weighting factor */
2 Generate a test for a single
fault;
¾ Timing is considered
¾ Can easily be implemented by an existing fault simulator
¾ Cannot identify untestable faults, and coverage for hard-to-
detect faults can be low

stg1.9 Cheng-Wen Wu, NTHU 11

Functional Testing
• Select (usually manually) tests which will validate
the functional operation of the device under test
− For example, the functional test for a FF may
consists of:
∗ Validating that the FF can be set and reset
∗ Validating that the FF can hold its state
− The testing of RAMs (and PLAs) are usually
functional
− There is a growing need for functional-level ATPG:
∗ Increasing circuit complexity
∗ Synthesis

stg1.9 Cheng-Wen Wu, NTHU 12

Cheng-Wen Wu, LARC, NTHU 6