ATPG or Automatic Test Pattern Generation or Automatic Test Pattern Generator, is an electronic design automation method or technology used to find an input or test sequence that, when applied to a digital circuit, enables testers to distinguish between the correct circuit behavior and the faulty circuit behavior caused by defects.

The generated patterns are used to test semiconductor devices after manufacture, and in some cases to assist with determining the cause of failure (in failure analysis). The effectiveness of ATPG is measured by the amount of modeled defects, or fault models, that are detected and the number of generated patterns. These metrics generally indicate test quality (higher with more fault detections) and test application time (higher with more patterns). ATPG efficiency is another important consideration. It is influenced by the fault model under consideration, the type of circuit under test (full scan, synchronous sequential, or asynchronous sequential), the level of abstraction used to represent the circuit under test (gate, register-transistor, switch), and the required test quality.

Sequential-circuit ATPG searches for a sequence of vectors to detect a particular fault through the space of all possible vector sequences. Stuck-at fault model is a popular ATPG fault model, in which one or more signal lines in a circuit is assumed to be stuck at a fixed logic value, regardless of what inputs are supplied to the circuit.

ATPG Algorithms

Testing very-large-scale integrated circuits with a high fault coverage is a difficult task because of complexity. Therefore many different ATPG methods have been developed to address combinational and sequential circuits.

  • Early test generation algorithms such as boolean difference and literal proposition were not practical to implement on a computer.
  • Exhaustive Algorithm: For n-input circuit, generate all 2n input patterns.
  • The D Algorithm was the first practical test generation algorithm in terms of memory requirements. The D Algorithm introduced D Notation which continues to be used in most ATPG algorithms.
  • Path-Oriented Decision Making (PODEM) is an improvement over the D Algorithm. PODEM was created when shortcomings in D Algorithm became evident when design innovations resulted in circuits that D Algorithm could not realize.
  • Fan-Out Oriented (FAN Algorithm) is an improvement over PODEM. It limits the ATPG search space to reduce computation time and accelerates backtracing.
  • Methods based on Boolean satisfiability are sometimes used to generate test vectors.
  • Pseudorandom pattern test generation is the simplest method of creating tests. It uses a pseudorandom number generator to generate test vectors, and relies on logic simulation to compute good machine results, and fault simulation to calculate the fault coverage of the generated vectors.