Automatic Test Pattern Generation (ATPG)

Automatic 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) creation of the test; and 2) application 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) by manual methods; 2) by algorithmic methods (with or without heuristics); and 3) by pseudo-random methods. 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 main considerations 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.' Path sensitization refers to 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 D and D'. 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 circuit exists.

Algorithmic pattern generation basically consists of the following steps: 1) fault selection, or choosing a fault that needs to be detected; 2) initial assignment, or finding an input pattern that sets up a D or D' at the output of the faulty gate; 3) forward drive, or propagating a D or D' to an observable output using the shortest path possible; 4) justification, 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, backtracking 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.

The 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', or 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.

The D 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 minimal set of input patterns necessary to test the circuit for the specified faults is determined.

Path-oriented Decision Making, or PODEM, 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.

For every 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 'back-tracing.' 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 testable.

The Fan-out 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 signals.

The test 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.

Pseudo-random 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.

The 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 'probabilistic' ATPG, since 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 'mixed' 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.

See Also: Electrical Testing; BIST; JTAG - Scan Test

Home