Automatic Test Pattern Generation (ATPG)

Custom Search

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.

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

Home