Automatic Test Pattern Generation (ATPG)

Custom Search

Automatic Test Pattern Generation (ATPG) - Page 2 of 2

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