Stuck fault coverage estimation for sequential circuits relies on a time expansion model, where combinational techniques are employed for each time-frame. Faults that are hard to detect and require a particular sequence of states are often incorrectly estimated to be detected. This problem is more evident for designs that exhibit low coverage either due to low testability or insufficient vectors that fail to exercise the required sequence of states. This paper illustrates how a simple state traversal analysis can mitigate this problem. For circuits with large number of sequential elements, we propose an entropy based technique that collapses the state graph to be analyzed. Experimental results for larger ISCAS benchmarks show that this technique reduces the coverage estimation error by as much as 50%.

Previously reported work on path and gate delay tests fail to analyze path reconvergences when a bounded gate delay model is used. While robust path delay tests are of the highest quality, most path faults are only testable nonrobustly. Many non-robust tests are usually found but, in practice, are easily invalidated by hazards. The invalidation of non-robust tests occurs primarily due to non-zero delays of off-path circuit elements that may reconverge. Thus, non-robust tests are of limited value when process variations cause gate delays to vary. For gate delay faults, failure to recognize the correlations among the ambiguity waveforms at inputs of reconvergent gates cause fault coverages to be optimistic. This paper enhances a recently published ambiguity simulation algorithm [5] to accurately measure both non-robust path and gate delay coverages for the bounded delay model. Experimental results for the ISCAS circuits show accurate results are often 20-30% less than the optimistic ones that fail to analyze signal reconvergences.

Conventionally, path delay tests are derived in a delay-independent manner, which causes most faults to be robustly untestable. Many non-robust tests are invalidated by hazards caused primarily due to non-zero delays of off-path circuit elements. Thus, non-robust tests are of limited value when process variations change gate delays. The authors propose a bounded gate delay model for test quality evaluation and give a novel simulation algorithm that is less pessimistic than previous approaches. The key idea is that certain time-correlations among the multiple transitions at the inputs of a gate cannot cause hazard at its output. The authors maintain "ambiguity lists" for gates. These are propagated with events, similar to fault lists in a traditional concurrent fault simulation. They are used to suppress erroneous unknown states. Experimental results for ISCAS benchmarks with gate delay variation of plusmn14% show a miscorrelation of critical path delay as much as 20%.

Statistical stuck-at fault coverage estimation assumes that signals at primary inputs and at other internal gates of the circuit are statistically independent. While valid for random and pseudo-random inputs, this causes substantial errors in coverage estimation for input sequences that are functional and not random, as shown by experimental data presented in this paper. At internal gates, signal correlation due to fanout reconvergence, even for random input sequences, contributes to errors. A significantly improved coverage estimation algorithm is presented in this paper. First, during logic simulation we identify faults that are guaranteed to stay undetected by the applied vectors. Then, after logic simulation, we estimate the detection probabilities of the remaining faults. Compared to Stafan, the statistics gathered during logic simulation are modified in order to eliminate the non-random biasing of the input sequence. Besides the improved detection probabilities, a newly defined effective length (Neff) of the vector sequence corrects for the temporally correlated signals. Experimental results for ISCAS combinational benchmarks demonstrate validity of this approach

A new algorithm for identifying stuck faults in combinational circuits that cannot be detected by a given input sequence is presented. Other than pre and post-processing steps, certain signal conditions are monitored during logic simulation. These signal conditions are specified by an analysis of dominators and signal reconvergences in the circuit graph. After simulation, a post-processing step identifies faults that cannot be detected by the sequence. For combinational IS GAS benchmarks, the runtime overhead for the algorithm is found to be around 30-40% over that of a logic simulator. Experimental data show a substantial reduction of error in statistical estimates obtained by a stuck-fault coverage estimator when corrected for faults found by this algorithm as guaranteed to be undetected by the given sequence. An effective application of this technique is demonstrated for scan-based test point selection in an industrial scenario where circuit size and vector length prohibit the use of fault simulation

The modeling and simulation of memory circuits remains an outstanding problem whenever accuracy with respect to the actual schematic implementation is desired. Functionally equivalent Register Transfer (RT) level models often cannot be used for designs with embedded memory blocks, because schematic models for the surrounding logic may be required for fault-modeling accuracy. Existing methods derive a latch model that essentially represents each memory location as a latch primitive. This approach results in models that have a large number of primitives. We present new algorithms that model such circuits as decoded arrays that access entire rows of cells for individual read and write operations. Decoded array models are easy to generate and allow fault-modeling accuracy for the surrounding logic, including the memory address decoder. Experimental data show improvements of an order of magnitude for both logic and fault simulations, when compared to the equivalent latch model.

The modeling and simulation of memory circuits remains an outstanding problem when accuracy with respect to the actual schematic implementation is desired. Functionally equivalent RTL models often cannot be used for designs with embedded memory blocks, because schematic models for the surrounding logic may be required for fault modeling accuracy. Existing methods derive a latch model that essentially represents each memory location as a latch primitive, and have a large number of gates. We present new algorithms that model such circuits as decoded arrays that access entire rows of cells for individual read and write operations. Decoded array models allow fault modeling accuracy for the surrounding logic, including the memory address decoder. Experimental data show improvements of an order of magnitude for both logic and fault simulations, when compared to the equivalent latch model.

Models meant for logic verification and simulation are often used for ATPG. For custom digital circuits, these models contain many tristate devices, which leads to lower fault coverage. Unlike other research in the literature, the modeling algorithms presented in this paper analyze each channel connected component in the context of its environment, thereby capturing the relationship among its input signals. This reduces the number of tristates and increases the modeling efficiency, as measured by fault coverage. Experimental results demonstrate the superiority of this approach.

We present an algorithm to derive logic systems for various classes of path delay test problems. In these logic systems, the value of a signal represents the relevant conditions that occur during a set of consecutively applied vectors. Starting from a set of basic values for valid signals at primary inputs, a state transition graph is constructed to enumerate all possible signal states relevant to path activation that are reachable by Boolean operations. These states include all incompletely specified states, composed as combinations of basic values. A distinguishability analysis then finds all state-pairs that need to be distinguished during test generation. The final step minimizes the number of states. For forward and backward implications of test generation in combinational or sequential circuits, the procedure provides optimal logic systems. We define optimality as the smallest set of logic states that provides the least possible ambiguity in implications. Thus, an optimal set of logic states will minimize the number of backtracks in test generation. A 10-valued logic described in the literature is found to be optimal for generating tests for single path delay faults. Other problems addressed in this paper include compact test generation through activation of many single path delay faults, test generation for rated-clock test application, and test generation for multiple path delay faults. The limitations and capabilities of various logic systems are illustrated by examples.

Even though hardware accelerators are common in very large scale integration (VLSI) computer-aided design (CAD), fault simulation is a notable exception because of limited availability of memory, the need for dynamic memory management and the complexity of the algorithms themselves. Although simplified fault simulation algorithms that assume a zero delay circuit model can be accelerated, their applicability is limited. Most application specific integrated circuits (ASIC's) designed in industry today have on-chip memory blocks of different dimensions and characteristics, enhancing the complexity of a fault simulator. In this paper, we present a multiple delay algorithm for concurrent fault simulation of logic gates and functional memory blocks. This algorithm has been implemented on the microprogrammable accelerator for rapid simulation (MARS) hardware accelerator system with a 22 MHz clock and a capacity to simulate circuits with millions of devices. Speedup factors of 20 to 30 are easily achieved when compared to software simulators running on comparable hardware platforms and using identical circuit models.

Current test generation algorithms for path delay faults assume a variable-clock methodology for test application. Two-vector test sequences assume that the combinational logic reaches a steady state following the first vector before the second vector is applied. While such tests may be acceptable for combinational circuits, their use for nonscan sequential circuit testing is impractical. A rated-clock path delay simulator shows a large drop in coverage for vectors obtained from existing test generators that assume a variable clock. A new test generation algorithm provides valid tests for uniform rated-clock test application. In this algorithm, signals are represented for three-vector sequences. The test generation procedure activates a target path from input to output using the three-vector algebra. For an effective backward justification, we derive an optimal 41-valued algebra. This is the first time, rated-clock tests for large circuits are obtained. Results for ISCAS-89 benchmarks show that rated-clock tests cover some longest, or close to longest, paths.

Delay test problems are well understood for gate level circuits. For certain logic families, delays depend on the charge stored at internal nodes. For such circuits, gate level models do not surface, A switch level simulator can be used for logic verification and stuck-at fault simulation. Toward making the delay fault simulation possible, this paper contributes three innovations to the switch-level technique: (1) Signals that remain steady over two consecutive vectors are identified using additional strength designations for charge and discharge paths; (2) Delay faults are propagated through MOS gates using articulation analyse's of the graph; and (3) A modified relaxation procedure determines the steady or non-steady status of signals at the same time it evaluates nodes. Experimental results demonstrate the validity of algorithms.

Many test generation algorithms for path delay faults assume a special methodology for application of the test sequence. The two-vector test sequences are valid under the assumption that the combinational logic reaches a steady state following the first vector before the second vector is applied. While such vectors may be acceptable for combinational circuits, their use for testing a non-scan sequential circuit is virtually impossible where it is difficult to run the clock at a constant rate. Most multi-valued algebras for combinational circuits are rendered invalid when vectors are applied at the rated speed. We present a new multi-valued algebra and a test generation algorithm to derive tests for a uniform rated speed test application methodology. The main ideas in the paper include an algebra that derives three-vector test sequences combinational logic and (2) a value propagation rule for latches, resulting in more realistic fault coverages in sequential circuits when all vectors are applied at the rated speed. The test generator uses Boolean functions to reason about state transitions in sequential machines. These Boolean functions are stored and manipulated as Binary Decision Diagrams (BDDs). Experimental data on moderate size ISCAS89 benchmarks are included.

For a given set of vectors, the guaranteed failure frequency of a synchronous sequential circuit is defined. This frequency is obtained from multiple delay logic simulation by selectively suppressing timing hazards. Any path delay fault testable by the vectors, if present, is guaranteed to be detected if the tests were run at this frequency.>

We use a 23-value logic system to generate robust path delay tests. Each test is successively augmented to detect as many path faults as possible. Other features of the test generator are a podem-like branch and bound search for test, an efficient path designation based on ordering of paths, and an algorithmic selection of secondary target faults for augmenting the tests to cover multiple faults. Results for ISCAS '89 benchmarks are given.>

To analyze path delay faults in synchronous sequential circuits, stimuli are simulated in a dual-vector mode. The signal states represent the logic and transition conditions for two consecutive vectors. After the simulation of each vector, only the activated paths are traced and the corresponding fault effect, if propagated to a flip-flop, is added to its fault list. A path numbering scheme avoids storage of path data which can be generated, if needed, from the path number. The simulation is independent of the specific delays of the combinational elements, and either robust or nonrobust detection can be simulated as options to the user. For robust simulation, an update rule for state variables is proposed whereby a flip-flop is updated with its correct value, provided it is a destination of at least one robustly activated path. This rule gives a higher and more realistic coverage of robustly detected faults. Experimental results verify the effectiveness of the simulator.>

A method is presented for automated verification of synchronous pipelined circuits, based on symbolic simulation and the well-known program verification concept of representation functions. The use of representation functions to allow straightforward formulation of readable and intuitive specifications is demonstrated, along with the use of a symbolic switch-level simulator to automatically prove that a circuit meets its specification. As an example, a systolic stack with more than 5000 transistors can be formally verified in a few minutes on a VAX 8800.>

A parallel resolution theorem prover, called Parthenon, that handles first-order logic is described. Parthenon is apparently the first general-purpose theorem prover to be developed for a multiprocessor. The system is based on a modification of D.H.D. Warren's SRI model (Int. Symp. on Logic Prog., pp.92-101, 1987) for OR-parallelism and implements a variant of D.W. Loveland's (J. ACM, vol.15, pp.236-51, 1968) model elimination procedure. It has been evaluated on various shared memory multiprocessors, including a 16-processor Encore Multimax. The authors have found that typical theorem-proving problems exhibit a great deal of potential parallelism. Parthenon has been able to exploit much of this parallelism, producing both impressive absolute run times and near-linear speed-up curves.>