Verification and test are critical phases in the development of any hardware or software system. This article focuses on black box testing of the control part of hardware and software systems. Black box testing involves specification, test generation, and fault coverage. Finite state machines (FSMs) are commonly used for specifying controllers. FSMs may have shortcomings in modeling complex systems. With the introduction of X-machines, complex systems can be modeled at higher levels of abstraction. An X-machine can be converted into an FSM while preserving the level of abstraction. The fault coverage of a test sequence for an FSM specification provides a confidence level. We propose a fault coverage metric for an FSM specification based on the transition fault model, and using this metric, we derive the coverage of a test sequence. The article also presents a method which generates short test sequences that meet a specific coverage level and then extends this metric to determine the coverage of a test sequence for an FSM driven by an FSM network. We applied our FSM verification technique to a real-life FSM, namely, the fibre channel arbitrated loop port state machine, used in the field of storage area networks.

An interconnect break is a break that occurs in the interconnect wiring, which results in logic gate inputs being disconnected from the drivers and causes the wire to float. Interconnect breaks are the most common types of breaks in modern $CMOS$ integrated circuits, so testing and detecting these breaks has become very important. This paper proposes a model by which standard tests for stuck-at-faults can be used to detect interconnect breaks in a circuit. We do a worst-case analysis of the detection of these breaks and calculate the minimum number of test vectors required to detect breaks with a specified confidence level, using n-detection principles. To enhance the understanding of the breaks in the circuit, we present a statistical model based on the length distribution of the wires surrounding the floating wire where the break occurs. From the model we compute the detection probabilities of such breaks and show that the worst case of detection is when the bias voltage is the same as the logic threshold voltage.

A heuristic algorithm, chesmin (checking sequence based state minimization), is proposed for state reduction in incompletely specified finite state machines (ISFSMs). The algorithm is based on checking sequence generation and identification of sets of compatible states. We have obtained results as good as the best exact method in the literature but with significantly better run-times. In addition to finding a reduced FSM, our algorithm also generates an I/O sequence that can be used as test vectors to verify the FSM's implementation.

Verification is a critical phase in the development of any hardware and software system. Finite state machines have been widely used to model hardware and software systems. Therefore, testing finite state machines (FSMs) is an important issue. Coverage analysis of a test suite for a system's implementation determines the adequacy and the confidence level of the verification phase. In this paper, we derive a fault coverage metric for a test suite for an FSM specification. We also extend this metric for fault coverage estimation of interconnected FSMs, and we propose symbolic input based fault coverage for large FSMs. Finally, we also study incremental construction of a test suite associated with a coverage for a given FSM specification.

An algorithm for generating checking sequences for asynchronous finite state machines is proposed. A checking sequence distinguishes a finite state machine (FSM) from all other FSMs with the same inputs and outputs, and with the same or fewer number of states. This algorithm is applied to normal fundamental mode asynchronous finite state machines (AFSM). The derived checking sequences can be used either as a test sets that detect all logic faults or to verify that the circuit design as a correct implementation of the AFSM. The resulting test is guaranteed to detect all logic faults occurring in the machine even if the defect causes a limited number of additional states.

This paper describes a simple algorithm for eliminating possible aggressor-victim net pairs for crosstalk analysis. This algorithm makes use of the observation that timing constraints in sequential circuits apply to crosstalk induced pulses. We show how this algorithm can be applied to a design to prune the candidate list for ATPG to detect crosstalk glitches that are introduced by manufacturing defects.

We present an automated procedure for improving the testability of a product by improving the testability of cells in the cell library. This method was applied to a scan flip-flop from Cyrix's standard cell library. Based on this analysis, some design and layout changes were suggested, which brought down the probability of difficult-to-detect faults by 70%, without compromising the performance or increasing the area of the circuit.

This paper describes how an inductive fault analysis (IFA) method was used in determining the expected yield and test algorithm effectiveness in SRAMs. One portion of the paper describes the process of gathering and correlating defect data from different sources to get a meaningful and accurate defect distribution. This data is used in the IFA software to weight the probability of faults occurring. With the fault data from two SRAM cells the yield of those devices is estimated and compared with actual yield. The effectiveness of certain test patterns is also evaluated based on the probable faults for those circuits.

Automated fault diagnosis based on the stuck-at fault model is not always effective. This paper presents practical experiences in applying a bridging fault based diagnosis technique to a TI ASIC design. Results are presented for units into which known bridging defects have been introduced via a focused ion beam (FIB) machine.

This paper develops a Physical Design for Test (PDFT) metric that is directly related to the expected quality level (QL) contribution of a cell to a circuit, and it details experimental results showing the usefulness of this metric in predicting the quality level contribution of a cell to circuits that have yet to be designed. The PDFT metric shows what QL increase can be expected for the circuit by changing the physical design of a component of the circuit.

Shorts and opens are the most common types of catastrophic defects in today's CMOS ICs. In this paper, we show that an open in the interconnect wiring of a digital CMOS circuit, which permanently disconnects inputs of logic gates from their driver, can cause oscillation or sequential behavior. We present supporting experimental data collected by creating an interconnect open in a manufactured chip. We also show that the conditions for oscillation and sequential behavior are likely to occur in many interconnect opens.

Successful failure analysis requires accurate fault diagnosis. This paper presents a method for diagnosing bridging faults that improves on previous methods. The new method uses single stuck-at fault signatures, produces accurate and precise diagnoses, and takes into account imperfect fault modeling; it accomplishes this by introducing the concepts of match restriction, match requirement, and match ranking.

Shorts and opens are the most common types of defects in today's CMOS ICs. In this paper we show for the first time that an open in the interconnect wiring of a digital CMOS circuit can cause oscillation or sequential behavior. We also analyze and compare the factors affecting the probabilities for an interconnect open and a feedback bridging fault to oscillate or display sequential behavior.

Effective bridging fault diagnosis requires reducing the (/sub 2//sup n/) number of bridging faults to a handful of candidates. A preliminary step can reduce the O(n/sup 2/) candidates to a manageable O(n) candidates by using layout information to eliminate those bridging faults that are very unlikely to be shorted together. This step removes from consideration those faults that match the fault signature but are physically impossible. However, sometimes-perhaps due to issues of intellectual property or because the degree of information stored about a circuit changes over its lifecycle-the physical design of the circuit is not available, and the number of nodes is too large to explicitly consider all pairs. In this paper we present two ways to provide successful diagnoses without access to physical information. The second method produces optimal diagnoses under our ranking criteria. Either technique can be used in conjunction with information extracted from the physical design to allow for diagnoses of much larger circuits than previously possible.

In addition to automatically generating correct wiring, routers are used to meet additional design goals. Examples include reducing capacitive coupling and improving yield. Using routers to improve testability has been mentioned in the literature, but concrete rules or methods have not been explained or implemented. In this paper, we show how a modified router improves bridge fault testability for two different test metrics, static-voltage testing and pseudo-exhaustive segmentation testing, with no significant increase in area or time. This method is flexible in that further testability improvements are possible by trading off routing area or routing time.

There is an increasing amount of effort spent in designing integrated circuits to be more testable in hopes of increasing quality levels. Most of this effort has focused on modifying the schematic-level design of circuits to improve their stuck-at fault coverage. However, many researchers have shown that a circuit's stuck-at fault coverage is not an accurate predictor of IC quality for low values of DPM. This work focuses on improving the testability of cells at the level of abstraction that directly interacts with the manufacturing defects - the physical design level. We first define a metric for measuring the effective testability of a cell. The effective testability of a cell is based on the physical design of the cell, the circuit in which the cell is used, and the methods that will be used to test the circuit. In this paper the term testability refers to effective testability. We then show how this metric is used to guide cell design for testability.

We present the experimental evidence, for the first time, that the die surface can act as an RC interconnect, becoming an important factor in determining the voltage of a floating wire created by a CMOS open. We present a circuit model for this effect verified with HSPICE simulations. A detailed analysis of potential mechanisms behind this phenomenon is provided. We also present our measurement results for the trapped charge deposited on floating gates during fabrication.

We provide test sets proportional to the sum of the two dimensions of the array for a large class of cells, which allow us to test rows (or columns) of cells of the array independently. Constant length test sets for array multipliers have been found under the single faulty cell model if the array is modified, and otherwise test sets are proportional to the number of cells. We can verify the full adder array of a combinational n/spl times/m multiplier in O(n+m) tests under the Multiple Faulty Cell (MFC) model. The entire multiplier, including the AND gates which generate the summands, can be verified after applying the same modifications which make the multiplier C-testable under the single faulty cell model.

We define a network break as a break fault in the p-network or in the n-network of a CMOS cell that breaks one or more transistor paths between the cell output and V/sub dd/ or GND. Previous work, mostly in the context of transistor stuck-open faults, studied test invalidation due to transient paths to V/sub dd/ or GND, and due to charge sharing. In this paper we show the importance of Miller feedthrough and feedback capacitances in network break test invalidation, which was ignored by previous work. We present a new fault simulation algorithm for network breaks, with the following novelties: First, the electrical charge coming from Miller and p-n junction capacitances is computed using a transistor charge model; this automatically handles the nonlinear nature of transistor capacitances accurately, as opposed to assuming constant capacitance values as was done in previous work. Next, we use only six voltage levels for charge computations, which allows us to create look-up tables that dramatically reduce the computation time. Finally, the maximum voltage an internal node in an n-network can acquire is about three-fourths of the V/sub dd/ voltage (instead of V/sub dd/ as assumed by previous work), and similarly, a p-network node cannot discharge all the way down to the GND voltage. Using our simulator to analyze test sets for the ISCAS'85 circuits, we found that the charge coming from Miller capacitances has a larger share in test invalidation than the charge from p-n junction capacitances. Our simulator spends less time for charge computations than it spends for transient path identification.

We present a new fault simulation algorithm for realistic break faults in the p-networks and n-networks of static CMOS cells. We show that Miller effects can invalidate a test just as charge sharing can, and we present a new charge-based approach that efficiently and accurately predicts the worst case effects of Miller capacitances and charge sharing together. Results on running our fault simulator on ISCAS85 benchmark circuits are provided. 1 INTRODUCTION Defects that occur during the IC manufacturing process can be categorized into three classes according to Hawkins et al. [7]. These classes are bridge, open circuit, and parametric defects. Open circuit defects cause breaks in the conducting materials in the layout, and contacts are particularly susceptible to such breaks. Breaks can be divided into two categories: those that physically disconnect one or more transistor gates from their drivers, and those that disconnect transistors from each other in the p-network or n-network of ...

Precise failure analysis requires accurate fault diagnosis. A previously proposed method for diagnosing bridging faults using single stuck-at dictionaries was applied only to small circuits, produced large and imprecise diagnoses, and did not take into account the Byzantine Generals Problem for bridging faults. We analyze the original technique and improve it by introducing the concepts of match restriction, match requirement, and failure recovery. Our new technique, which requires no information other than that used by standard stuck-at methods, produces diagnoses that are an order of magnitude smaller than those produced by the original technique and produces many fewer misleading diagnoses than that of traditional stuck-at diagnosis.

It is assumed that tests generated using the single stuck-at fault model will implicitly detect the vast majority of fault-causing defects within logic elements. This may not be the case. In this paper we characterize the possible shorts in the combinational cells in a standard cell library. The characterization includes errors on the cell outputs, errors on the cell inputs, and excessive quiescent current. The characterization provides input vectors to stimulate these errors. After characterizing the faults that occur due to possible electrical shorts, we compare the coverage of the logic faults using a single stuck-at test set and tests developed specifically to detect these shorts. We discuss the effectiveness of I/sub DDQ/ testing for these faults.

The IC test industry has struggled for move than 30 years to establish a test approach that would guarantee a low defect level to the customer. We propose a comprehensive strategy for testing CMOS ICs that uses defect classes based on measured defect electrical properties. Defect classes differ from traditional fault models. Our defect class approach requires that the rest strategy match the defect electrical properties, while fault models require that IC defects match the fault definition. We use data from Sandia Labs failure analysis and test facilities and from public literature. We describe test pattern requirements for each defect class and propose a test paradigm.

Presents a procedure for reducing the probability of undetectable shorts occurring between horizontal wires. This procedure is implemented by modifying a channel router to predict many of the shorts that are undetectable and then place the associated signal wires in nonadjacent tracks. For the designs routed, it is found that the probability of an undetectable nonfeedback short between horizontal lines in the routing channels is reduced by 39.9% with no increase in the number of routing tracks required and little increase in routing computation cost.>

Present research in design for testability has largely been confined to the logic level. This paper presents directions for research in design for testability at the layout or physical design level. These are illustrated for bridge faults in circuits consisting of CMOS standard cells.>

Traditional fault models for testing CMOS VLSI circuits do not take into account the actual mechanisms that precipitate faults in CMOS circuits. As a result, tests based on traditional fault models may not detect all the faults that occur in the circuit. This paper discusses the Carafe software package which determines which faults are likely to occur in a circuit based on the circuit's physical design, defect parameters, and fabrication technology.>

Describes a built-in self-test (BIST) technique for general sequential circuits in which storage elements in a circuit are replaced with self-test elements. These elements are connected as a feedback shift register, and used to both generate test patterns and compress test responses. Benchmarks were run on a number of standard sequential benchmark circuits to determine single stuck-at fault coverage. The results of these tests indicate that the self-test techniques presented obtain fault coverage similar to that of random test techniques.>

Many manufacturing defects in static CMOS circuits are not detected by tests generated using the traditional single stuck-at fault model. May of these defects may be detected as increased propagation time or as excessive quiescent power supply current (IDDQ). In this paper the authors consider the probable manufacturing defects and compare the costs of detecting them by the resulting excess IDDQ versus the cost of traditional testing methods.>

The authors compare the cost of testing for excess of I/sub DDQ/ caused by bridge, break, and transistor stuck-on faults versus the cost of traditional testing methods. It is shown that, since many defects, cause nonlogical faults, I/sub DDQ/ monitoring during the application of test vectors to an IC provides significantly higher defect coverage than using only conventional testing. The costs for I/sub DDQ/ testing are compared with those for SSF (single-stuck-at-fault) testing by modifying an existing SSF ATPG (automatic test pattern generation) system. It is concluded that test generation for I/sub DDQ/ faults is quicker and more complete than for equivalent SSF faults, and even without explicit I/sub DDQ/ test generation, I/sub DDQ/ monitoring can be added to existing SSF testing for increased defect coverage.>

Test sets that detect multiple faults in MOS circuits are characterized, guided by the observation that such circuits are implemented as networks of switches. This leads to a conceptually simple technique for generating multiple fault test sets. Sufficient conditions for the detection of all multiple faults are given for switch networks, and it is shown that a test set exists meeting these conditions for any irredundant circuit with certain restrictions on fan out. In the cases where these conditions cannot be met, a class of robust test sets is presented. Test sets that generate complete multiple fault test sets with fewer vectors for many MOS complex gates than is possible using a gate-level description of the circuit are presented.>

FXT is a software tool which implements inductive fault analysis for CMOS circuits. It extracts a comprehensive list of circuit-level faults for any given CMOS circuit and ranks them according to their relative likelihood of occurrence. Five commercial CMOS circuits are analyzed using FXT. Of the extracted faults, approximately 50% can be modeled by single-line stuck-at 0/1 fault model. Faults extracted from two circuits are simulated with the switch-level fault simulator FMOSSIM. The test set provided by the circuits' manufacturer, which detects 100% of the single-line stuck-at 0/1 faults, detected between 73% and 89% of the simulated faults.>

The inductive fault analysis (IFA) method is presented and a description is given of the CMOS fault extraction program FXT. The IFA philosophy is to consider the causes of faults (manufacturing defects) and then simulate these causes to find the faults that are likely to occur in a circuit. FXT automates IFA for a CMOS technology by generating a list of faults that are likely to occur in a CMOS circuit. The realistic faults generated by FXT are used to evaluate fault models, find the realistic fault coverage of test sets, and guide future testing research. How well various fault models characterize the realistic faults can be quantitatively measured because FXT's fault list includes the relative likelihood of occurrence (weight) of each extracted fault. The value of IFA and FXT is demonstrated by the analysis of five commercial CMOS circuits. This analysis shows that the traditional SSA fault model characterizes fewer than half of the faults extracted by FXT; graph-theoretic techniques provide little improvement in the percentage of realistic faults modeled.>

Array multipliers are well suited for VLSI implementation because of the regularity in their iterative structure. However, most VLSI circuits are difficult to test. This correspondence shows that, with appropriate cell design, array multipliers can be designed to be very easily testable. An array multiplier is called C-testable if all its adder cells can be exhaustively tested while requiring only a constant number of test patterns. The testability of two well-known array multiplier structures is studied in detail. The conventional design of the carry–save array multiplier is modified. The modified design is shown to be C-testable and requires only 16 test patterns. Similar results are obtained for the Baugh–Wooley two's complement array multiplier. A modified design of the Baugh–Wooley array multiplier is shown to be C-testable and requires 55 test patterns. The C-testability of two other array multipliers, namely the carry–propagate and the TRW designs, is also presented.

Array multipliers are well-suited for VLSI implementation because of the regularity in their iterative structure. However, most VLSI circuits are very difficult to test. This paper shows that, with appropriate cell design, array multipliers can be designed to be very easily-testable. An array multiplier is called C-testable if all its adder cells can be exhaustively tested while requiring only a constant number of test patterns. The testability of two well-known array multiplier structures are studied. The conventional design of the carry-save array multiplier is shown to be not C-testable. However, a modified design, using a modified adder cell, is generated and shown lo be C-testable and requires only 76 test patterns. Similar results are obtained for the Baugh-Wooley two's complement array multiplier. A modified design of the Baugh-Wooley array multiplier is shown to be C-testable and requires 55 test patterns. The implementation of a practical C-testable 16 × 16 array multiplier is also presented.