It is well known that n-detection test sets are effective to detect unmodeled defects and improve the defect coverage. However, in these sets, each of the n-detection test patterns has the same importance on the overall test set performance. In other words, the test pattern that detects a fault for the first time plays the same important role as the test pattern that detects that fault for the (n)-th time. In this paper, we propose a linear programming-based optimal test pattern selection method which aims at reducing the overall defect part level (DPL). Using resistive bridge faults as surrogates, our experimental results on ISCAS85 circuits demonstrate the proposed test pattern selection method achieves higher defect coverage than traditional n-detection method.

Dynamic defects are less likely to be fortuitously detected than static defects because they have more stringent detection requirements. We show that (in addition to more site observations) balanced excitation is essential for detection of these defects, and we present a metric for estimating this degree of balance. We also show that excitation balance correlates with the parameter /spl tau/ in the MPG-D defective part level model.

In previous work, we have shown that optimizing the number of site observations leads to more defect detection. However, for increasingly difficult defects, optimizing patterns for balanced random excitation also enhances test effectiveness. We can also reduce the effect of undetected defects by choosing tests that minimize the likelihood of field failures.

Recent probabilistic test generation approaches have proven that detecting single stuck-at-faults multiple times is effective at reducing the defective part level (DPL). Unfortunately, these test generation strategies increase the number of test patterns. In this paper, we present a novel linear programming-based method to accelerate the optimal selection of test sets to minimize the defective part level based upon the MPG-D model. Our experimental results show that the proposed method is on average 300 times faster than the existing test pattern selection method.

In this paper, we study the possibility of using logic defect-level prediction models to predict the detection behavior of statistical timing defects. We compare two known logic models: the Williams-Brown (WB) model and the Mercer-Park-Grimaila-Dworak (MPGD) model. In the WB-model, the defect coverage is replaced by the n-detection transition fault coverage. We first demonstrate that both logic models may fail to predict the detection of statistical timing defects. Then, we propose an improved WB model based upon selection of the hard-to-detect transition faults. We show that, by selecting a proper subset of the hard-to-detect transition faults, the detection behavior of these faults can correlate well to the detection behavior of statistical timing defects. We explain our findings through statistical delay defect injection and simulation, and report results based upon various benchmark circuits.

In conventional delay testing, the test clock is a single pre-defined parameter that is often set to be the same as the system clock. This paper discusses the potential of enhancing test efficiency by using multiple clock frequencies. The intuition behind our work is that for a given set of AC delay patterns, a carefully-selected, tighter clock would result in higher effectiveness to screen out the potential defective chips. Then, by using a smarter test clock scheme and combining with a second set of AC delay patterns, the overall quality of AC delay test can be enhanced while the cost of including the second pattern set can be minimized. We demonstrate these concepts through analysis and experiments using a statistical timing analysis framework with defect-injected simulation.

Logic BIST is about to become a more main stream test method for IC testing. In some flows when a failure is encountered the IC is diagnosed to determine the cause of the failure. Diagnosing fails in Logic BIST is significantly different from that in a stored pattern test methodology. The first step is to determine the failing pattern or interval among the many patterns that were applied. Today this involves a binary search of the tests that were applied with Logic BIST. In this paper we improve on this binary search strategy to reduce the time taken to isolate the failing patterns by orders of magnitude.

Deterministic observation and random excitation of fault sites during the ATPG process dramatically reduces the overall defective part level. However, multiple observations of each fault site lead to increased test set size and require more tester memory. In this paper we propose a new ATPG algorithm to find a near-minimal test pattern set that detects faults multiple times and achieves excellent defective part level. This greedy approach uses 3-value fault simulation to estimate the potential value of each vector candidate at each stage of ATPG. The result shows generation of a close to minimal vector set is possible only using dynamic compaction techniques in most cases. Finally, a systematic method to trade-off between defective part level and test size is also presented.

In conventional delay testing, two types of tests, transition tests and path delay tests, are often considered. The test clock frequency is usually set to a single pre-determined parameter equal to the system clock. This paper discusses the potential of enhancing test effectiveness by using multiple test sets with multiple clock frequencies. The two intuitions motivating our analysis are 1) multiple test sets can deliver higher test quality than a single test set, and 2) for a given set of AC delay patterns, a carefully-selected, tighter clock would result in higher effectiveness to screen out potentially defective chips. Hence, by using multiple test sets, the overall quality of AC delay test can be enhanced, and by using multiple-clock schemes the cost of adding the additional pattern sets can be minimized. In this paper, we analyze the feasibility of this new delay test methodology with respect to different combinations of pattern sets and to different circuit characteristics. We discuss the pros and cons of multiple-clock schemes through analysis and experiments using a statistical delay evaluation and delay defect-injected framework.

Uses data collected from benchmark circuit simulations to examine the relationship between the tests which detect stuck-at faults and those which detect bridging surrogates. We show that the coefficient of correlation between these tests approaches zero as the stuck-at fault coverage approaches 100%. An enhanced version of the MPG-D model, which is based upon the number of detections of each site in a logic circuit, is shown to be superior to stuck-at fault coverage-based defective part level prediction. We then compare the accuracy of both predictors for an industrial circuit tested using two different test pattern sequences.

Predicting the final value of the defective part level after the application of a set of test vectors is not a simple problem. In order for the defective part level to decrease, both the excitation and observation of defects must occur. This research shows that the probability of exciting an as yet undetected defect does indeed decrease exponentially as the number of observations increases. In addition, a new defective part level model is proposed which accurately predicts the final defective part level (even at high fault coverages) for several benchmark circuits and which continues to provide good predictions even as changes are made an the set of test patterns applied.

Presents the results of the study of a new algorithm for multi-level logic minimization. The study is based on the premise that an untestable node is a redundant node, and that nodes that do not demonstrably cause conflicting behavior at primary outputs may be compatible. Data gathered using the presented techniques show that fault dictionary analysis is a powerful tool for logic minimization. The algorithm developed in this study, the Texas Aggies Logic Optimizing Netlister (TALON), is shown to be competitive with, and complementary to, other methodologies. TALON can be used by itself or as a preprocessor or postprocessor for other tools, giving superior results to those obtained by any of them working independently.

If many potential defects exist at each site in an integrated circuit, then as the number of applied test patterns increases, the number of defects which remain undetected decreases monotonically. Modeling this rate of decline in defective part level is a non-trivial problem. We show that the number of times each site is observed serves as a significantly superior basis for modeling this phenomenon when contrasted with the number of faults detected. This "site observation-based" predictor not only increases the accuracy of defective part level prediction, it also provides the first quantitative method for comparing the effectiveness of various ATPG strategies to reduce the defective part level.

For many years, non-target detection experiments have been simulated by using AND/OR bridges or gross delay faults as surrogates. For example, the defective part level can be estimated based upon surrogate detection when test patterns target stuck-at faults in the circuit. For the first time, test pattern generation techniques that attempt to maximize non-target defect detection have been used to test a real, 100% scanned, commercial chip consisting of 75 K logic gates. In this experiment, the defective part level for REDO-based patterns was 1,288 parts per million lower than that achieved by DC stuck-at based patterns generated using today's state of the art tools and techniques.

Automatic test pattern generation (ATPG) requires justification of logic values on internal lines of circuits. For sequential circuits, the justification backtraces to primary inputs or flip-flops. Primary input values may be specified arbitrarily. In contrast, the required logic values at flip-flops must be justified backward through multiple time frames, and this often produces logic conflicts which cause backtracks. We employ functional analysis of the sequential circuit so as to minimize the number of logic value assignments to flip-flops. We also present strategy switching between two efficient state justification methods. Mutually complementary properties of the two state justification methods turn out to be very effective. These refinements significantly improve ATPG performance for sequential circuits.

The traditional goal of an ATPG algorithm is to achieve a high fault coverage by producing a small number of tests. However, since usually a high fault coverage does not imply a high defect coverage, such an objective can mislead us to overtrust an ATPG method which is optimal for faults but inefficient for defects. The paper presents several new principles to design an ATPG algorithm for solve this problem. The new principles direct an ATPG algorithm to improve its efficiency and reliability for detecting the non target defects through the target faults. Theory and experiments are presented to demonstrate the superiority of the new principles and the new test generation algorithm.

The traditional ATPG method relies upon faults to target all defects. Since faults do not model all possible defects, testing quality depends on the fortuitous detection of non-target defects. By analyzing different ATPG approaches, this paper intends to identify critical factors that may greatly affect the fortuitous detection. For enhancing the fortuitous detection of non-target defects through target faults, new concepts and novel ATPG methods are proposed.

While technology is changing the face of the world, it itself is changing by leaps and bounds; there is a continuing trend to put more functionality on the same piece of silicon. Without major changes in the CMOS technology, it has been shown that the scaling of devices has significant impact on the effectiveness of Iddq testing. The sensitivity of Iddq testing to individual device parameters is studied. It is explained how Iddq testing becomes increasingly ineffective in the scaled product with respect to most parameters and can be improved with others.

As the operating speed of digital circuits dramatically increases with the advance of VLSI technology, it is becoming more critical to ensure that the circuits are free from timing-related design errors. In a traditional static timing approach nonfunctional paths cannot be distinguished from functional ones since the functionality of a circuit is ignored. This often results in overestimation of circuit delay and can degrade the circuit performance. In today's design methodology where the use of automated logic synthesis and module-based design are popular, circuits with a very large number of nonfunctional (false) paths are common. This paper describes an efficient logic-level timing analysis approach that can provide an accurate delay estimate of a digital circuit which may have many long false paths. By using logic incompatibilities in a circuit as constraints for critical path search, the algorithm determines the longest sensitizable path without explicit path enumeration. Since the number of false paths that can be implicitly eliminated is potentially exponential to the number of path constraints, performance improvement is significant.

How can we guarantee that a testing method will stably and efficiently achieve a very low defective part level? Traditional testing methods rely upon faults to model all defects. As technology advances, this approach becomes increasingly questionable. If only a subset of defects are modeled as faults, then as fault coverage approaches 100%, the tests mill be more and more biased in favor of fault detection. Unfortunately, this reduces the testing efficiency for defects and limits the quality level that we can achieve. In this paper, we propose models for the testing process and suggest a solution which we call "unbiased test generation". We define two types of testing bias, and these new metrics can be used to compare and evaluate test generation methods in practice.

Testing is an indispensable process to weed out the defective parts coming out of the manufacturing process. Traditionally, test generation targets on a specific fault model, usually the single stuck-at fault model, to produce tests that are expected to identify defects such as unintended shorts and opens. With this approach, the test quality relies on fortuitous detection of the non-target defects. As the quality demands and circuit sizes increase, the feasibility of test generation on a single fault model becomes questionable. In the paper, we present empirical data from experiments on ISCAS benchmark circuits to demonstrate that using traditional methods the probability of detecting nontarget defects drops rapidly as the fault coverage approaches 100%. By assuming surrogates, we explain the mechanism which produces this effect and describe a new test pattern generation approach with better testing efficiency.

The stuck-at fault model has been used over decades as a guide to the test generation process and as an evaluation mechanism for the quality of the test set. As demands on quality have increased, the use of the stuck-at fault model as a predictor of the defect level has been questioned. This paper provides some insight on the issue and shows the limitations of using the stuck-at fault coverage to predict the defect level. The authors demonstrate that as defect level decreases the uncertainty of the estimate grows.>

This paper derives exact equations for the maximum number of nonterminal vertexes in reduced and quasi-reduced ordered binary decision diagrams (OBDD's). A reduced OBDD is reduced by both merging and deleting vertices, and a quasi-reduced OBDD is reduced only by merging. These formulas are used to tighten Lee's original bounds, and to correct the bounds recently reported by H.T. Liaw and C.S. Lin (1992).>

Verifying the correctness of logic design has been an important problem for a long time. But there have been no efficient design verification tools for very large circuits. We present an efficient symbolic design verification method for very large circuits which exploits the properties of OPDDs (ordered partial decision diagrams). By symbolically extracting and simulating test patterns with OPDDs our design verification system provides time and space advantages over existing methods.>

This paper explores a test pattern generation problem for switch-level combinational circuits. In test generation for switch-level circuits, constraints on assignable logic values can be introduced due to the difference between the implicated logic values and the justifiable logic values of a logic element. Therefore, identifying unjustifiable logic values as early as possible would greatly accelerate the switch-level test generation. For this, a new logic value system called taboo logic value is proposed to represent the unjustifiable logic values of a node. Also, a new switch-level ATPG system is developed which employs a constraint-guided line justification method using taboo logic value. Finally, experimental results on various types of circuits demonstrate the efficiency of the proposed approach and the possibility of the practical application to large switch-level circuits.>

The increasing size and complexity of current VLSI circuits has brought testing and design for testability into the mainstream of the design process. A significant amount of research has been done in the area of gate-level combinational ATPG using the stuck-at-fault model. The problem has been shown to be NP-complete and most of the current research attempts to find efficient ways to generate tests for hard faults in a reasonable amount of time on the average. Hence, there remains a lot of interest in the testing world for efficient techniques to do combinational ATPG. Use of ordered binary decision diagrams (OBDDs) for function representation has provided significant impetus to algebraic CAD techniques. This paper presents techniques for gate-level ATPG using OBDDs.>

A timing analyzer which performs timing analysis considering electrical-level details such as input signal slope, gate input distinction, charge sharing, and interconnect, while also taking into account such high-level concerns as path sensitization, is described. To achieve the greatest efficiency, ETA operates in two phases: (1) logic and delay precharacterization, and (2) longest path analysis. During the precharacterization phase, each gate is analyzed to get its Boolean function and its load at the transistor level. During the longest path analysis phase, paths from each primary input are enumerated and examined separately. Each potentially longest path is tested for sensitizability at the gate level until a sensitizable longest path is found. The circuit examples given demonstrate the importance of an accurate delay calculation in correctly finding the longest statistically sensitizable path.>

A fast algorithm for minimizing the two-level AND/XOR representation of combinational functions, based on a graphical data structure similar to the OBDD, is described. This GMX (Graphical Minimizer for XORs) algorithm works by 'reading-off' and minimizing the solution from an augmented OBDD, called an SFG. The advantage of the SFG structure is that it is often of polynomial size. The algorithm generates solutions significantly better, or no worse, than all previously published solutions on a set of example circuits.>

The standard approach to generating a test set for a logic circuit is to select a set of target fault,s and generate one test for each fault (or at least most of the faults). By far, the most common target fault set is composed of single stuck-at faults. However, many potential manufacturing (non-target) defects are not included in the target fault set, so that their detection is just a fortuitous coincidence. In most cases, many different tests may exist which detect a given single stuck-at fault. However, each of these tests (for the same stuck-at fault) may perform very differently in terms of their non-target defect detection. We investigate this phenomenon empirically using a subset of the ISCXS 85 benchmark circuits, and our results show that extremely wide variations in defective part level are possible over sets of tests which all guarantee 100% single non-redundant stuck-at fault coverage. Our objective in this work is the investigation of non-target defects and their impact on defective part level. Here, our thrust is not to develop new test gene rut i o n methods .

The nature of many problems related to testability requires detailed information about their underlying test parameters. These parameters are commonly referred to as controllability and observability. This research concerns exact measures of detectability, controllability, and observability to measure the relative importance of the latter two on the likelihood of the former. New functional methods for fault analysis are utilized which allow computations not previously possible; the empirical results presented here are an example of such an application.>

An algorithm for bounding the random pattern testability of individual faults in a circuit is proposed. Auxiliary gates for bounding the testability are constructed, converting the problem into one of determining the signal probability at the output of the auxiliary gate. The results presented are in terms of lower bounds of the testabilities of faults. The bounds generated by the algorithm can be used by designers to identify pseudorandom pattern resistant faults, to enable them to modify the circuit structure to make the faults easy to detect, and, hence, to increase the fault coverage.>

Delay testing at the operational system clock rate can detect system timing failures caused by delay faults. However, delay fault coverage in terms of the percentage of the number of tested faults may not be an effective measure of delay testing. A quantitative delay fault coverage model to provide a figure of merit for delay testing is presented. System sensitivity of a path to a delay fault along that path and the effectiveness of a delay test are described in terms of the propagation delay of the path under test and the delay defect size. A new statistical delay fault coverage model is established. A defect level model is also proposed as a function of the yield of a manufacturing process and the new statistical delay fault coverage. A new delay testing strategy driven by the defect level for delay faults is proposed.>

An efficient delay test generation (DTEST GEN) system for combinational logic circuits is presented. In the DTEST GEN system, delay testing problems are divided into gross delay faults and small delay faults separately so that the tradeoff between the levels of delay testing effort and the confidence levels of proper system operation can be explored. Complete automatic test pattern generation (ATPG) algorithms are proposed for both gross delay faults and small delay faults. A novel timing analysis method for delay test generation which uses a conventional depth-first search technique and a novel functionality analysis technique is introduced. The functionality analysis technique examines, necessary conditions for a given delay fault to be testable and estimates the upper bound of the good circuit propagation delay of the longest sensitizable path passing through the fault site. Several benchmark results are demonstrated for both gross delay fault testing and small delay fault testing.>

As CAD tools become more sophisticated, they can synthesize logic netivorks that more nearly optimize the circuit area resources to maximize operating speeds.In this work we show, through formal arguments, that the path delays in such optimized networks will follow a more compact distribution and, in the extreme in some networks, will all be equal to the m"mum delay through the network (cycle time).The impact of this type of synthesized network on delay testing will be shown and compared to the case for nonoptim"zed designs.Finally, recommendations will be made on how network tim"ng optimization can be abne in such a way as to minimize the adverse impact on product yield.

As electronic CAD synthesis tools become more powerful, they will increasingly refine delay measiirements and adjust path delays so as to increase the clock rate or to reduce the chip area. This paper discusses the implications of such events on testing for delay defects. We provide a timing optimization procedure and show that the resultant density function of path delays is a delta function. Finally, we discuss the impact of timing optimization on the yield of a manufacturing process and the defect level for delay faults.

A new method, Difference Propagation, is proposed to analyze fault models in combinational circuits. It propagates Boolean functional information represented by ordered binary decision diagrams. Results are presented concerning exact detectabilities and syndromes for a set of benchmark circuits. The data suggest answers to open questions in CAD and represent the first data of this type for bridging faults. The information is shown to affect testable design as well as test generation.

This paper presents an efficient delay test generation system for combinational logic circuits. Delay testing problems are divided into gross delay fault testing and small delay fault testing in order to explore the trade-off between the levels of delay testing effort and the confidence levels of proper system operation. Complete automatic test pattern generation algorithms are proposed for both gross delay faults and small delay faults. Especially for the small delay fault test generation, new search space enumeration techniques are employed so as to bias the search space such that a delay test for relatively long paths can be found. Also a novel timing analysis method via functionality check is presented for delay test generation. Finally, complete test results are demonstrated for both gross delay faults and small delay faults on several benchmark circuits.

Adjacency testing for delay faults is examined in both theory and implementation. We shall show that the necessary and sufficient conditions for adjacency testability yield an efficient method of robust delay test generation. Empirical results (including several different cost measurements) are presented which demonstrate that our technique: (1) achieves high fault coverages under both the robust and nonrobust delay fault models and (2) is cost effective.

A quantitative delay fault coverage model is discussed to provide a figure of merit for delay testing. System sensitivity of a path to a delay fault along that path and the effectiveness of a delay test are described in terms of the propagation delay of the path under test and the delay defect size. A statistical delay fault coverage model is established. A defect-level model is also proposed as a function of the yield of a manufacturing process and the statistical delay fault coverage.>

A high-speed fault simulator is presented that combines demand-driven simulation techniques with a bit-encoded deductive fault simulation scheme. The simulator uses an efficient approach to the management of signal value and fault list structures intended to minimize disk thrashing during execution. Input cone analysis is used during preprocessing to identify gates with independent inputs so that optimized evaluation routines that include early cutoff can be used. Results are given for the demand-driven deductive fault simulator and contrasted with an earlier demand-driven parallel fault simulator.>

The automatic generation of tests for combinational digital circuits is examined from the standpoint of a guided search through a search space. The limitations of this process, namely the size of the search space and the overall strategy, are identified and methods are presented to reduce the size of the search space as well as produce a more optimal ordering of node assignments. A new algorithm is proposed that uses the smaller search space and the improved ordering for node assignments based on a topological analysis of the circuit. Results are presented indicating that this new algorithm, termed TOPological Search (TOPS), is faster than existing algorithms and also rapidly identifies many redundant faults without search.

A new digital simulation algorithm is presented based on the concept of demand driven simulation. Where traditional event driven simulation propagates signal values forward through a circuit in response to input pin events, demand driven simulation propagates requests for simulation values backwards both through the circuit and through time. In this manner, only those evaluations required to obtain “watched” signal values are performed. BACKSIM, the simulator based on this algorithm, has proven to be faster and more efficient than event driven simulation for every test case tried to date.

In this paper, we analyze combinational logic circuits using "fan-out constraints" to generate tests for single stuck-at faults. A method of circuit transformation is employed to explicitly derive "fan-out constraints for controllability" and "fan-out constraints for observability," which are dependent Boolean functions and Boolen difference functions, respectively, in terms of primary inputs and fan-out stems. Then, a simplified version of a test generation algorithm which uses only the fan-out constraints for controllability at internal reconvergent fan-out stems is illustrated with an example. This approach differs from earlier work in that information about the circuit is accumulated and refined as the test generation process proceeds. In this test generation algorithm, the dependencies among fan-out nodes are ordered and solved in a hierarchical fashion so that the computation time for generating tests and detecting redundant faults can be greatly reduced--especially for locally redundant or "difficult" faults.

This paper defines a development system for computer-aided design (CAD) algorithms for combinational logic networks. The principle features of this system include graph-oriented commands and control structures, list handling facilities, and an expandable library of commonly used CAD subprograms. Application programs written using the prototype system, CADTOOLS, include worst case path delay analysis, Sandia Controllability and Observability Analysis (SCOAP) testability measure, and logic simulation. The experience with these programs suggests that such a system can reduce the time required to develop CAD programs.