Automatic test pattern generation

Last updated April 03, 2023

ATPG (acronym for both Automatic Test Pattern Generation and 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 automatic test equipment 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, or to assist with determining the cause of failure (failure analysis ^[1]). The effectiveness of ATPG is measured by the number of modeled defects, or fault models, detectable and by 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 that 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-transfer, switch), and the required test quality.

Basics

A defect is an error caused in a device during the manufacturing process. A fault model is a mathematical description of how a defect alters design behavior. The logic values observed at the device's primary outputs, while applying a test pattern to some device under test (DUT), are called the output of that test pattern. The output of a test pattern, when testing a fault-free device that works exactly as designed, is called the expected output of that test pattern. A fault is said to be detected by a test pattern if the output of that test pattern, when testing a device that has only that one fault, is different than the expected output. The ATPG process for a targeted fault consists of two phases: fault activation and fault propagation. Fault activation establishes a signal value at the fault model site that is opposite of the value produced by the fault model. Fault propagation moves the resulting signal value, or fault effect, forward by sensitizing a path from the fault site to a primary output.

ATPG can fail to find a test for a particular fault in at least two cases. First, the fault may be intrinsically undetectable, such that no patterns exist that can detect that particular fault. The classic example of this is a redundant circuit, designed such that no single fault causes the output to change. In such a circuit, any single fault will be inherently undetectable.

Second, it is possible that a detection pattern exists, but the algorithm cannot find one. Since the ATPG problem is NP-complete (by reduction from the Boolean satisfiability problem) there will be cases where patterns exist, but ATPG gives up as it will take too long to find them (assuming P≠NP, of course).

Fault models

single fault assumption: only one fault occur in a circuit. if we define k possible fault types in our fault model the circuit has n signal lines, by single fault assumption, the total number of single faults is k×n.
multiple fault assumption: multiple faults may occur in a circuit.

Fault collapsing

Equivalent faults produce the same faulty behavior for all input patterns. Any single fault from the set of equivalent faults can represent the whole set. In this case, much less than k×n fault tests are required for a circuit with n signal line. Removing equivalent faults from entire set of faults is called fault collapsing.

The stuck-at fault model

In the past several decades, the most popular fault model used in practice is the single stuck-at fault model. In this model, one of the signal lines in a circuit is assumed to be stuck at a fixed logic value, regardless of what inputs are supplied to the circuit. Hence, if a circuit has n signal lines, there are potentially 2n stuck-at faults defined on the circuit, of which some can be viewed as being equivalent to others. The stuck-at fault model is a logical fault model because no delay information is associated with the fault definition. It is also called a permanent fault model because the faulty effect is assumed to be permanent, in contrast to intermittent faults which occur (seemingly) at random and transient faults which occur sporadically, perhaps depending on operating conditions (e.g. temperature, power supply voltage) or on the data values (high or low voltage states) on surrounding signal lines. The single stuck-at fault model is structural because it is defined based on a structural gate-level circuit model.

A pattern set with 100% stuck-at fault coverage consists of tests to detect every possible stuck-at fault in a circuit. 100% stuck-at fault coverage does not necessarily guarantee high quality, since faults of many other kinds often occur (e.g. bridging faults, opens faults, delay faults).

Transistor faults

This model is used to describe faults for CMOS logic gates. At transistor level, a transistor maybe stuck-short or stuck-open. In stuck-short, a transistor behaves as it is always conducts (or stuck-on), and stuck-open is when a transistor never conducts current (or stuck-off). Stuck-short will produce a short between VDD and VSS.

Bridging faults

A short circuit between two signal lines is called bridging faults. Bridging to VDD or Vss is equivalent to stuck at fault model. Traditionally both signals after bridging were modeled with logic AND or OR of both signals. If one driver dominates the other driver in a bridging situation, the dominant driver forces the logic to the other one, in such case a dominant bridging fault is used. To better reflect the reality of CMOS VLSI devices, a Dominant AND or Dominant OR bridging fault model is used. In the latter case, dominant driver keeps its value, while the other one gets the AND or OR value of its own and the dominant driver.

Opens faults

Delay faults

Delay faults can be classified as:

Gate delay fault
Transition fault
Hold Time fault
Slow/Small delay fault
Path delay fault: This fault is due to the sum of all gate propagation delays along a single path. This fault shows that the delay of one or more paths exceeds the clock period. One major problem in finding delay faults is the number of possible paths in a circuit under test (CUT), which in the worst case can grow exponentially with the number of lines n in the circuit.

Combinational ATPG

The combinational ATPG method allows testing the individual nodes (or flip-flops) of the logic circuit without being concerned with the operation of the overall circuit. During test, a so-called scan-mode is enabled forcing all flip-flops (FFs) to be connected in a simplified fashion, effectively bypassing their interconnections as intended during normal operation. This allows using a relatively simple vector matrix to quickly test all the comprising FFs, as well as to trace failures to specific FFs.

Sequential ATPG

Sequential-circuit ATPG searches for a sequence of test vectors to detect a particular fault through the space of all possible test vector sequences. Various search strategies and heuristics have been devised to find a shorter sequence, or to find a sequence faster. However, according to reported results, no single strategy or heuristic out-performs others for all applications or circuits. This observation implies that a test generator should include a comprehensive set of heuristics.

Even a simple stuck-at fault requires a sequence of vectors for detection in a sequential circuit. Also, due to the presence of memory elements, the controllability and observability of the internal signals in a sequential circuit are in general much more difficult than those in a combinational logic circuit. These factors make the complexity of sequential ATPG much higher than that of combinational ATPG, where a scan-chain (i.e. switchable, for-test-only signal chain) is added to allow simple access to the individual nodes.

Due to the high complexity of the sequential ATPG, it remains a challenging task for large, highly sequential circuits that do not incorporate any Design For Testability (DFT) scheme. However, these test generators, combined with low-overhead DFT techniques such as partial scan, have shown a certain degree of success in testing large designs. For designs that are sensitive to area or performance overhead, the solution of using sequential-circuit ATPG and partial scan offers an attractive alternative to the popular full-scan solution, which is based on combinational-circuit ATPG.

Nanometer technologies

Historically, ATPG has focused on a set of faults derived from a gate-level fault model. As design trends move toward nanometer technology, new manufacture testing problems are emerging. During design validation, engineers can no longer ignore the effects of crosstalk and power supply noise on reliability and performance. Current fault modeling and vector-generation techniques are giving way to new models and techniques that consider timing information during test generation, that are scalable to larger designs, and that can capture extreme design conditions. For nanometer technology, many current design validation problems are becoming manufacturing test problems as well, so new fault-modeling and ATPG techniques will be needed.

Algorithmic methods

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.
The D Algorithm was the first practical test generation algorithm in terms of memory requirements. The D Algorithm [proposed by Roth 1966] introduced D Notation which continues to be used in most ATPG algorithms. D Algorithm tries to propagate the stuck at fault value denoted by D (for SA0) or D (for SA1) to a primary output.
Path-Oriented Decision Making (PODEM) is an improvement over the D Algorithm. PODEM was created in 1981, by Prabhu Goel, 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 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.
Wavelet Automatic Spectral Pattern Generator (WASP) is an improvement over spectral algorithms for sequential ATPG. It uses wavelet heuristics to search space to reduce computation time and accelerate the compactor. It was put forward by Suresh kumar Devanathan from Rake Software and Michael Bushnell, Rutgers University. Suresh kumar Devanathan invented WASP as a part of his thesis at Rutgers.^{[ citation needed ]}

Relevant conferences

ATPG is a topic that is covered by several conferences throughout the year. The primary US conferences are the International Test Conference and The VLSI Test Symposium, while in Europe the topic is covered by DATE and ETS.

Related Research Articles

A logic gate is an idealized or physical device that performs a Boolean function, a logical operation performed on one or more binary inputs that produces a single binary output.

<span class="mw-page-title-main">Digital electronics</span> Electronic circuits that utilize digital signals

Digital electronics is a field of electronics involving the study of digital signals and the engineering of devices that use or produce them. This is in contrast to analog electronics and analog signals.

A signal generator is one of a class of electronic devices that generates electrical signals with set properties of amplitude, frequency, and wave shape. These generated signals are used as a stimulus for electronic measurements, typically used in designing, testing, troubleshooting, and repairing electronic or electroacoustic devices, though it often has artistic uses as well.

In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history. This is in contrast to combinational logic, whose output is a function of only the present input. That is, sequential logic has state (memory) while combinational logic does not.

This is an index of articles relating to electronics and electricity or natural electricity and things that run on electricity and things that use or conduct electricity.

JTAG is an industry standard for verifying designs and testing printed circuit boards after manufacture.

A fault model is an engineering model of something that could go wrong in the construction or operation of a piece of equipment. From the model, the designer or user can then predict the consequences of this particular fault. Fault models can be used in almost all branches of engineering.

Boundary scan is a method for testing interconnects on printed circuit boards or sub-blocks inside an integrated circuit. Boundary scan is also widely used as a debugging method to watch integrated circuit pin states, measure voltage, or analyze sub-blocks inside an integrated circuit.

Asynchronous circuit is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circuit which indicates a completion of a set of instructions. Handshaking works by simple data transfer protocols. Many synchronous circuits were developed in early 1950s as part of bigger asynchronous systems. Asynchronous circuits and theory surrounding is a part of several steps in integrated circuit design, a field of digital electronics engineering.

A stuck-at fault is a particular fault model used by fault simulators and automatic test pattern generation (ATPG) tools to mimic a manufacturing defect within an integrated circuit. Individual signals and pins are assumed to be stuck at Logical '1', '0' and 'X'. For example, an input is tied to a logical 1 state during test generation to assure that a manufacturing defect with that type of behavior can be found with a specific test pattern. Likewise the input could be tied to a logical 0 to model the behavior of a defective circuit that cannot switch its output pin. Not all faults can be analyzed using the stuck-at fault model. Compensation for static hazards, namely branching signals, can render a circuit untestable using this model. Also, redundant circuits cannot be tested using this model, since by design there is no change in any output as a result of a single fault.

Design for testing or design for testability (DFT) consists of IC design techniques that add testability features to a hardware product design. The added features make it easier to develop and apply manufacturing tests to the designed hardware. The purpose of manufacturing tests is to validate that the product hardware contains no manufacturing defects that could adversely affect the product's correct functioning.

Scan chain is a technique used in design for testing. The objective is to make testing easier by providing a simple way to set and observe every flip-flop in an IC.The basic structure of scan include the following set of signals in order to control and observe the scan mechanism.

Scan_in and scan_out define the input and output of a scan chain. In a full scan mode usually each input drives only one chain and scan out observe one as well.
A scan enable pin is a special signal that is added to a design. When this signal is asserted, every flip-flop in the design is connected into a long shift register.
Clock signal which is used for controlling all the FFs in the chain during shift phase and the capture phase. An arbitrary pattern can be entered into the chain of flip-flops, and the state of every flip-flop can be read out.

Iddq testing is a method for testing CMOS integrated circuits for the presence of manufacturing faults. It relies on measuring the supply current (Idd) in the quiescent state. The current consumed in the state is commonly called Iddq for Idd (quiescent) and hence the name.

Semiconductor fault diagnostics are predictive software algorithms which are used to refine and localize the circuitry responsible for the failure of scan-based devices.

<span class="mw-page-title-main">CircuitLogix</span>

CircuitLogix is a software electronic circuit simulator which uses PSpice to simulate thousands of electronic devices, models, and circuits. CircuitLogix supports analog, digital, and mixed-signal circuits, and its SPICE simulation gives accurate real-world results. The graphic user interface allows students to quickly and easily draw, modify and combine analog and digital circuit diagrams. CircuitLogix was first launched in 2005, and its popularity has grown quickly since that time. In 2012, it reached the milestone of 250,000 licensed users, and became the first electronics simulation product to have a global installed base of a quarter-million customers in over 100 countries.

Test compression is a technique used to reduce the time and cost of testing integrated circuits. The first ICs were tested with test vectors created by hand. It proved very difficult to get good coverage of potential faults, so Design for testability (DFT) based on scan and automatic test pattern generation (ATPG) were developed to explicitly test each gate and path in a design. These techniques were very successful at creating high-quality vectors for manufacturing test, with excellent test coverage. However, as chips got bigger and more complex the ratio of logic to be tested per pin increased dramatically, and the volume of scan test data started causing a significant increase in test time, and required tester memory. This raised the cost of testing.

<span class="mw-page-title-main">Hardware Trojan</span> Malware embedded in hardware; harder to detect and fix than software vulnerabilities

A Hardware Trojan (HT) is a malicious modification of the circuitry of an integrated circuit. A hardware Trojan is completely characterized by its physical representation and its behavior. The payload of an HT is the entire activity that the Trojan executes when it is triggered. In general, Trojans try to bypass or disable the security fence of a system: for example, leaking confidential information by radio emission. HTs also could disable, damage or destroy the entire chip or components of it.

In electronic engineering, a bridging fault consists of two signals that are connected when they should not be. Depending on the logic circuitry employed, this may result in a wired-OR or wired-AND logic function. Since there are O(n^2) potential bridging faults, they are normally restricted to signals that are physically adjacent in the design.

This glossary of electrical and electronics engineering is a list of definitions of terms and concepts related specifically to electrical engineering and electronics engineering. For terms related to engineering in general, see Glossary of engineering.

FAN algorithm is an algorithm for automatic test pattern generation (ATPG). It was invented in 1983 by Hideo Fujiwara and Shimono Takeshi at the Department of Electronic Engineering, Osaka University, Japan. It was the fastest ATPG algorithm at that time and was subsequently adopted by industry. The FAN algorithm succeeded in reducing the number of backtracks by adopting new heuristics such as unique sensitization and multiple back tracing. Unique sensitization is to determine as many signal values as possible that can be uniquely implied. Multiple backtracing is concurrent backtracing of more than one path, which is more efficient than backtracing along a single path. In order to reduce the number of backtracks, it is important to find the nonexistence of the solution as soon as possible. When we find that there exists no solution we should backtrack immediately to avoid the subsequent unnecessary search. These heuristics can lead to the early detection of inconsistency and decrease the number of backtracks. FAN algorithm has been introduced in several books and many conference papers such as ACM/IEEE Design Automation Conference, et al.

References

Electronic Design Automation For Integrated Circuits Handbook, by Lavagno, Martin, and Scheffer, ISBN 0-8493-3096-3 A survey of the field, from which the above summary was derived, with permission.
Microelectronics Failure Analysis. Materials Park, Ohio: ASM International. 2004. ISBN 0-87170-804-3.

↑ Crowell, G; Press, R. "Using Scan Based Techniques for Fault Isolation in Logic Devices". Microelectronics Failure Analysis. pp. 132–8.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Crowell, G; Press, R. "Using Scan Based Techniques for Fault Isolation in Logic Devices". Microelectronics Failure Analysis. pp. 132–8.

[1]