Test Pattern Generation (ATPG)
Test Pattern Generation,
or ATPG, is a process used in semiconductor electrical testing
wherein the vectors or input patterns required to check a device for faults are automatically
generated by a program. The vectors are sequentially applied to
the device under test and the device's response to each set of inputs is compared
with the expected response from a good circuit. An 'error' in the response
of the device means that it is faulty. The effectiveness of the ATPG is
measured primarily by the fault coverage achieved and the cost of
performing the test.
A cycle of
ATPG can generally be divided into two distinct phases: 1)
of the test; and 2)
of the test. During the creation of the test, appropriate models
for the device circuit are developed at gate or transistor level in such
a way that the output responses of a faulty device for a given set of
inputs will differ from those of a good device. This generation of test
is basically a mathematical process that can be done in three ways: 1)
methods (with or without heuristics); and 3) by
The software used for complex ATPG applications are quite expensive, but
the process of generating a test needs to be done only once at the end
of the design process.
When creating a test, the
goal should be to make it as efficient in memory space and time
requirements as much as possible. As such, the ATPG process must
generate the minimum or near minimum set of vectors needed to detect all
the important faults of a device. The
for test creation are: 1) the time needed to construct the minimal test
set; 2) the size of the pattern generator, or hardware/software system
needed to properly stimulate the devices under test; 3) the size of the
testing process itself; 4) the time needed to load the test patterns;
and 5) the external equipment required (if any).
Examples of ATPG algorithmic
methods that are in wide use today include the D-Algorithm, the PODEM,
and the FAN. Pattern generation through any of these algorithmic
methods require what is known as 'path sensitization.'
finding a path in the circuit that will allow an error to show up at an
observable output of a device if it is faulty. For example, in a
two-input AND gate, sensitizing the path of one input requires the other
input to be set to '1'.
Most algorithmic generation
methods also refer to the notations
These notations were introduced by the D algorithm and have been adopted
by other algorithms since then.
D simply stands for a '1' in a good circuit and a '0' in a faulty one.
On the other hand, D', which is the opposite of D, stands for a '0' in a
good circuit and '1' in a faulty circuit. Thus, propagating a D or
D' from the inputs to the output simply means applying a set of inputs
to a device to make its output exhibit an 'error' if a fault within the
pattern generation basically consists of the following steps: 1)
or choosing a fault that needs to be detected; 2)
or finding an input pattern that sets up a D or D' at the output of the
faulty gate; 3)
or propagating a D or D' to an observable output using the shortest path
or assigning of values to other unassigned inputs in order to justify
the assignments made during the forward drive. If an inconsistency
arises during justification,
or back propagation is performed, i.e., forward drive is done again
using an alternate path. This recursive cycle is performed until the
right set of input patterns needed to 'sensitize' a path and propagate
the fault to an observable output is determined.
D algorithm was
developed by Roth at IBM in 1966, and was the first 'complete' test
pattern algorithm designed to be programmable on a computer. A
test algorithm is 'complete' if it is able to propagate a failure to an
observable output if a fault indeed exists. As discussed in the previous paragraph, the D
algorithm entails finding all sets of inputs to the circuit that will
bring out a fault within the circuit. A 'primitive D cube of failure',
PDCF, is a set of inputs that sensitizes a path for a particular
fault within a circuit. The 'propagation D cube', or
PDC, is a set of
inputs that propagates a D from the inputs to the output.
algorithm picks all possible PDCF's for the circuit under test and
applies them to the circuit with their corresponding PDC's to propagate various
faults to the output. While the PDCF's and PDC's are
being applied, the 'implied' values for other circuit nodes are tested
for consistency, rejecting sets of inputs that cause a circuit violation.
The application and testing of various PDCF's and PDC's for a circuit is
done repeatedly and recursively, until the
set of input
patterns necessary to test the circuit for the specified faults is
was developed by Goel in 1981 to address a problem that the D algorithm
had with XOR gates. PODEM was the first major enhancement to the D
algorithm as far as efficiency is concerned. The D algorithm
progresses exponentially in complexity with the number of internal
circuit nodes, while PODEM's complexity varies exponentially with the
number of circuit inputs. PODEM is more efficient than the D algorithm
because the number of inputs is usually much smaller than the number of
internal circuit nodes.
target fault to be covered, PODEM checks all the possible input values
until a valid test is found for that fault. It does so by assigning
different values to the primary inputs of the circuit. Every time a new
value is applied to a primary input, its implication is evaluated in
terms of whether it is contributing to the detection of the fault or
not. Input values that prevent fault detection either by desensitizing
the path or blocking the propagation are changed by a process called
PODEM repeatedly assigns different values to the primary inputs until a
test vector that detects the fault is found. PODEM also stops once all
input combinations have already been exhausted without finding an
applicable test vector, in which case the fault is deemed to be not
Oriented (FAN) algorithm is a further improvement to PODEM with some
additional features. For instance, it utilizes circuit topology information to
increase search efficiency. FAN differs from PODEM in several ways,
including the following: it stops backtracking at certain internal
lines; it performs multiple back-tracing; it allows both backward and
forward implications; and it immediately assigns uniquely-determined
pattern generation algorithmic methods discussed in previous paragraphs
are all computation-intensive and can be quite expensive, not to mention
the numerous difficulties that may be encountered in complex cases.
In fact, in some complex circuits, the use of such algorithms is no
longer feasible or practical.
test pattern generation coupled with fault simulation is a simpler
alternative to algorithmic methods. This involves the generation of
input vectors using a relatively inexpensive pseudo random number
generator and the performance of fault simulations to determine if these
vectors will lead to the detection of the target fault. The
characteristics of the target fault has a great influence on how well
pseudo-random test generation will work. It is typically used in the
beginning of the test generation process to cover easy-to-detect faults
from the list of faults to be covered. Faults that were not
covered by the pseudo-random test generation may be covered by
algorithmic methods for test generation are examples of
'deterministic' ATPG, since the tests are systematically developed with a definite
outcome for the targeted faults.
Pseudo-random test generation is an example of a
the test vectors are generated by 'chance' and simply confirmed by fault
simulations for effectiveness. Combining the pseudo-random test
generation with the algorithmic test generation is an example of
ATPG. Mixed ATPG is a good approach in the sense that it is able
to utilize the advantages of both deterministic and probabilistic ATPG's.
Electrical Testing; BIST;
JTAG - Scan
All Rights Reserved.