Due to the increased use of field-programmable gate arrays (FPGAs) in production circuits with high reliability requirements, the design-specific testing of FPGAs has become an important topic for research. Path delay testing of FPGAs is especially important since path delay faults can render an otherwise fault-free FPGA unusable for a given design layout. This paper presents a new approach for FPGA path delay testing, which partitions target paths into subsets that are tested in the same test configuration. Each path is tested for all combinations of signal inversions along the path length. Each configuration consists of a sequence generator, response analyzer, and circuitry for controlling inversions along tested paths, all of which are formed from FPGA resources not currently under test. Two algorithms are presented for target-path partitioning to determine the number of required test configurations. The test circuitry associated with these methods is also described. The results of applying the methods indicate that our path-delay-testing approach requires seconds per design to cover all paths with delay within 10% of the critical path delay. The approach has been validated using Xilinx Virtex devices.

The widespread use of field programmable gate arrays (FPGAs) as components in high-performance systems has increased the significance of path delay faults in FPGAs. We present a technique for FPGA path delay fault detection which integrates test insertion with the FPGA placement and routing stages to accomplish testing with low test application time. An accurate static timing analyzer is used to identify critical paths and built-in self-test (BIST) hardware is inserted using a placement and routing tool. Initial experimental results show that testing is accomplished with low test application time for several benchmark designs.

This paper presents a method of primitive fault identification and test generation for combinational and nonscan sequential circuits. It uses the concept of sensitizing cubes to obtain input vectors that statically sensitize primitive faults in combinational circuits. The same technique is used to identify combinationally primitive faults in the next-state and output logic of sequential circuits. Such faults are primitive if and only if the fault effects on paths to state variable flip-flops can be propagated to a primary output (PO). Test sequences, including initializing sequences from a reset state and sequences that propagate fault effects from flip-flops to POs, are generated for primitive faults, wherever possible. The proposed method has been implemented and used to derive tests for primitive faults in the ISCAS'89 and MCNC'91 benchmark circuits. It was able to find all primitive faults and also obtain robust tests for a large fraction of them when the circuits were treated as combinational. When the same circuits were treated as nonscan sequential circuits, all primitive faults could not be found because fault propagation had to be limited to a relatively small number of time frames.

A path delay fault in a sequential circuit will affect circuit timing only if it can be activated during normal operation of the circuit. Since vector pairs that can be applied to the next-state logic of a nonscan sequential circuit are restricted by the available state transitions, some faults may be impossible to activate. Such faults are redundant and need not be tested. In this paper, we present a method of identifying redundant path delay faults in the next-state logic implemented in a two-level sum of products form and extend it to multilevel realizations. Experimental results on MCNC'91 benchmarks show that large fractions of faults in most of the MCNC'91 benchmarks are redundant.

Recent research has characterized a class of faults, called primitive faults, that must be tested to insure timing correctness of digital circuits. Experimental results have shown that a large fraction of primitive faults usually have only non-robust tests. In this paper, we propose a method of improving robust coverage of primitive faults using test point insertion. An important feature of the proposed method is that instead of considering primitive faults explicitly, single faults are analyzed to determine whether they can be members of robustly testable primitive faults. If not, test points are specified to make any primitive fault containing such faults robustly testable. Results of experiments to determine the effectiveness of the proposed method show significant improvements in fault coverage.

A method is presented for identifying primitive path-delay faults in non-scan sequential cixuits and generating robwt tests for all robustly testable primitive faults.It uses the concept of sensitizing cubes introduced in an earlier paper and a nw, more eficient algon.thmforgenerating them.Sensitizing cubes of the natstate and output logic are used to obtain static sensitizing vectors that can be applied to the non-scan sequential cixuit as part of a vector-paiz These vector-pairs are also used in den.ving robust tests.Initializing sequencesfim a reset state and sequences that propagate fault effects~m @p-@ps to pn.nra~outputs are also generated The proposed method has been implemented and used to derive testsforprimitivefaults in ISCAS'89 and MCNC'91 benchmark cixuits.

The authors introduce a new approach to fault simulation, using reconfigurable hardware to implement a critical path tracing algorithm. The performance estimate shows that the approach is at least on order of magnitude faster than serial fault emulation used in prior work.

The paper presents a method of identifying primitive path delay faults in combinational circuits, and deriving robust tests for all robustly testable primitive faults. It uses the concept of sensitizing cubes to reduce the search space. This approach helps identify faults that cannot be part of any primitive fault, and avoids attempting test generation for them. Sensitization conditions determined for primitive fault identification are also used in test generation, reducing test generation effort. Experimental results on some of the ISCAS'85 and MCNC'91 benchmark circuits indicate that they contain a fair number of primitive multiple path delay faults which must be tested.

The path delay fault testability of sequential circuits is limited by state transitions that can be produced during normal operation. As a result, there may be untestable faults some of which may affect circuit behavior. The authors first extend the concept of primitive faults to sequential circuits. They then describe a method of selecting a set of flip-flops for partial enhanced-scan, such that falling transitions on all paths are made robustly testable in a two-level prime and irredundant realization of the sequential circuit. It results in a robust or VNR test for every rising transition primitive fault, using the available state transitions. A method of synthesizing sequential circuits such that untestable faults do not affect the initialization, is presented. An area comparison between area-optimized and delay-verifiable versions of the MCNC '91 benchmark circuits is also presented.

Path delay fault testing in non-scan sequential circuits is complicated by the limited state transitions during normal operation. An accepted method for overcoming this difficulty is to use a scan chain consisting of enhanced scan flip-flops which makes the application of arbitrary vector pairs possible. However, the method results in increased path delays because of the enhanced scan flip-flops themselves. In this paper we present a new method for improving path delay fault testability without increasing path delays in the circuit. It uses a simple clock control circuit to produce single bit transitions on state variables and a parity check circuit for observing state variable flip-flops. The area overhead of this method is comparable to enhanced scan but no performance penalty is incurred. We demonstrate the effectiveness of this method in delay testing and show how it can be used for stuck-at fault testing.

This paper proposes a new approach to multilevel logic optimization based on automatic test pattern generation (ATPG). It shows that an ordinary test generator for single stuck-at faults can be used to perform arbitrary transformations in a combinational circuit and discusses how this approach relates to conventional multilevel minimization techniques based on Boolean division. Furthermore, effective heuristics are presented to decide what network manipulations are promising for minimizing the circuit. By identifying indirect implications between signals in the circuit, transformations can be derived which are "good" candidates for the minimization of the circuit. A main advantage of the proposed approach is that it operates directly on the structural netlist description of the circuit so that the technical consequences of the performed transformations can be evaluated in an easy way, permitting better control of the optimization process with respect to the specific goals of the designer. Therefore, the presented technique can serve as a basis for optimization techniques targeting nonconventional design goals. This paper only considers area minimization, and our experimental results show that the method presented is competitive with conventional technology-independent minimization techniques. For many benchmark circuits, our tool, the Hannover implication tool, based on learning (HANNIBAL) achieves the best minimization results published to date. Furthermore, the optimization approach presented is shown to be useful in formal verification.

This paper investigates the relationship between path-delay-fault testability and multiple stuck-at-fault testability in multilevel combinational circuits. It is shown that a complete robust path-delay-fault test set may not detect all multiple stuck-at faults in multilevel circuits. We also show that path-delay-fault testability does not imply multiple stuck-at-fault testability in multilevel circuits, contradicting a recent paper. Certain path delay tests are also shown to be invalidated by the presence of untestable or untested multiple stuck-at faults.

We address the problem of testing circuits for temporal correctness. A circuit is considered delay-verifiable if its timing correctness can be established by applying delay tests. It is shown that verifying the timing of a circuit may require tests which can detect the simultaneous presence of more than one path delay fault. We provide a general framework for examining delay-verifiability by introducing a special class of faults called primitive path delay faults. It is necessary and sufficient to test every fault in this class to ensure the temporal correctness of combinational circuits. Based on this result, we develop a synthesis procedure for combinational circuits that can be tested for correct timing. Experimental data show that such implementations usually require less area than completely delay testable implementations.>

In this paper we show that any finite state machine can be implemented by a fully path-delay-fault testable nonscan sequential circuit. Synthesis methods are proposed, which use a one-hot encoding of states, a special circuit structure and at most one additional input. Combined with existing synthesis techniques for delay-fault testable combinational circuits, these methods can produce nonscan sequential circuits in which every path has a robust or validatable nonrobust test.>

We show that most symmetric functions do not have delay-testable two-level implementations. A method of transforming any untestable minimal two-level implementation of a symmetric function into a delay-testable three- or four-level one using the distributive law is presented.>

It is shown that verifying the timing of a circuit by testing may require tests which can detect the simultaneous presence of more than one path delay fault. We introduce a special class of path delay faults, called primitive faults, whose detection is shown to be necessary and sufficient to ensure the temporal correctness of a circuit. Using this result, we develop a synthesis procedure for combinational circuits that can be tested for correctness of timing. Experimental data show that such implementations usually require less area than completely delay testable implementations.>

We present a new approach to synthesizing fully path-delay-fault testable non-scan sequential circuits. Two methods are proposed. Given the state transition graph of a finite state machine, one of our methods generates a fully robustly testable circuit while the other method, which may lead to more area-efficient circuits, guarantees robust or validatable non-robust tests for all paths.>

Identification and removal of redundancy in digital circuits is important for improving their testability as well as reducing their area. This paper presents a method of identifying and removing redundancy in combinational circuits by analyzing circuit structure. Experimental results indicate that the method is quite efficient in execution time, but may not identify all undetectable faults. It is expected to be suitable for integration into a logic synthesis system. It can also be used as a preprocessor for a test pattern generation program or for a test pattern generation based redundancy removal program.>

The authors point out that significant improvements in the speed of fault simulation of combinational circuits have been achieved in recent years by combining parallel pattern simulation for the fault-free circuit with trace-based methods for identifying detected faults. Here, two concepts-joining stems for reducing explicit simulation of stem faults and quit lines for reducing backtracing within fanout-free regions-are presented. These concepts are used in a parallel-pattern trace-based simulation algorithm. Results of simulating the ISCAS85 benchmark combinational circuits with the proposed methods show their effectiveness both with and without fault-dropping.>

An efficient fault simulation algorithm for synchronous sequential circuits is presented. It uses parallel fault simulation with dynamic fault grouping, and combines it with backtracing within certain fanout-free regions and the use of surrogate faults. A backtracing method is developed to handle the three logic values, 0,1, and X, accurately. The concept of surrogate faults is also extended to represent all nine combinations of fault-free and faulty values. The results of simulating a set of benchmark sequential circuits show that reductions in execution time of 7-54% were obtained by the use of backtracing and surrogate faults compared to the well-known method, PROOFS.>

Two important components of the concurrent simulation algorithm are divergence and scheduling. The effects of timing specifications in functional modules on divergence and scheduling are examined, and an efficient method for performing these operations is proposed. >

Redundancy in combinational circuits is usually identified when faults are found to be undetectable during test generation. Redundancy removal based on test generation is not efficient, because removal of the redundancy causing a fault to be undetectable will usually affect the detectability of other faults, making it necessary to repeat test generation. The authors present a method of identifying and removing redundancy in combinational circuits by analyzing regions between fanout stems and reconvergence gates, and experimental results for the ISCAS85 benchmark circuits.>

In this paper, two methods of applying two-pattern tests for stuck-open faults in scan-testable CMOS sequential circuits are presented. These methods require shifting in only one pattern and require no special latches in the scan chain. Sufficient conditions for 110bust testability of all single FET stuck-open faults and design techniques for robustly scan-testable CMOS sequential circuits are presented. These techniques lead to realizations with at most two additional inputs and some additional FETS in the first-level gates.

The basic critical path tracing method for combinational circuits is outlined, and it is shown how it can produce pessimistic results in certain cases where fault effects propagate along multiple paths. The problem of extending the critical path tracing method to sequential circuits is considered. It is shown that the pessimistic nature of critical path tracing in combinational circuits may lead to optimistic results in sequential circuits, and a modification of the critical path tracing method to make it exact for combinational circuits is proposed. Based on this modification, a critical path tracing algorithm for synchronous sequential circuits is developed which is also exact.>

It is shown that the detectability of stuck-open faults in CMOS sequential circuits with scan paths containing ordinary shift register latches depends on the state assignment used. A method by which any state table can be realized by a circuit that is scan testable for stuck-open faults is presented. Tests can be applied to these circuits by shifting in only one vector per test, reducing the test application time. The proposed method is applied to five state tables from the MCNC Logic Synthesis and Optimization Benchmarks. It is found that the overhead of the method is in the range of 14% to 29%.>

Significant improvements in the speed of fault simulation of combinational circuits have been achieved by combining parallel pattern simulation of the fault-free circuit with tracing-based methods for identifying detected faults. The authors propose a method of reducing the expense of backtracing by identifying lines where backtracking may be stopped, and they show its efficiency through an experiment with a set of benchmark circuits. The proposed method has been implemented in the C language on a VAX 6210/VMS which has a machine word of 32 b. Thirty-two patterns are processed in parallel during true-value simulation, backtracing, and stem analysis. Calculations of the sensitivity, stem-criticality, and checkup vectors are performed by vector operations when each line is reached during first backtracing. The results indicate that the proposed method is more efficient than that of K.J. Antreich and M.H. Schultz (1987) for all the benchmark circuits that were simulated.>

The authors present the CAD tools used for system-level design verification (DV) in the AT&T computer division. They discuss features of the tools for building and preparing the model of the system, developing tests, simulation, static timing analysis, results analysis, and circuit comparison. While a good simulator is an essential component, many other tools are required. Although some of them provide only relatively minor capabilities, together they form an integrated set of tools that greatly simplify the designers' work and make possible successful completion of system-level DV projects.>

Identification of undetectable faults is essential for preventing test invalidation due to the occurrence of such faults, and for improving the efficiency of test generation. Methods for identifying undetectable faults in combinational circuits by analyzing regions between fanout stems and reconvergent gates are presented. These methods have been successful in identifying many of the undetectable faults in several benchmark circuits, without test generation.>

The authors present a symbolic test generation algorithm which uses a hierarchical model of the data path and a finite state model of the control section of the system under test. The data path may contain sequential modules, as well as synchronous feedback loops. The stable table of the control section can be used by the test generation algorithm to generate test even in complex sequential modes of operation of the system. The symbolic approach presented is applicable with a top-down, as well as a bottom-up, approach to hierarchical test generation. With a top-down approach, symbolic constraints derived at a higher level are used in deriving module tests, thereby guaranteeing that the tests will be applicable in the environment in which the module is used. If a bottom-up approach is used, tests for any module in its operating environment are obtained by combining symbolic tests and module tests.>

The authors present an approach to testability analysis applicable to circuits containing functional modules described behaviorally. They consider two types of modules-combinational modules described by binary decision diagrams and sequential modules defined by state tables. Controllability and observability measures for such modules are defined, and algorithms are developed for computing them. The method has been applied to a few small modules and circuits, and appears to be feasible. The combinational measures, applicable to both combinational and sequential modules, indicate the probability of setting a lead to a particular value or observing the effect of a signal change at an output. The sequential measures, also applicable to both types of modules, give estimates of sequence lengths needed for controlling and observing any lead in the circuit. These two measures together give an indication of not only the difficulty in deriving tests for a circuit but also the length of test sequences that may be needed.>

Critical path tracing has been shown to be faster than traditional fault simulation methods, but it produces pessimistic results in some cases involving reconvergent fanout. It is shown that the pessimistic nature of critical path tracing in combinational circuits can lead to incorrect results that are not necessarily pessimistic in sequential circuits. A modification of the method for removing the approximation is proposed, and a critical path tracing algorithm for synchronous sequential circuits is presented.>

Stuck-at faults on primary inputs and fan-out branches are commonly used as target faults in test generation algorithms for combinational circuits. This correspondence shows that these faults may not constitute an adequate set of target faults. A procedure is presented for selecting a set of target faults with the property that the detection of all detectable faults from this set guarantees the detection of all detectable faults in the circuit.

In this correspondence we prepent a practical approach to fault simulation and test generation for bridging faults in combinational circuits. Unlike previous work, we consider Unrestricted bridging faults, including those that introduce feedback. Our approach is based on extending fault simulation and test generation for stuck faults to cover bridging faults as well. We consider combinational testing only, and show that adequate bridging fault coverage can be obtained in most cases without using sequences of vectors.

In this paper, we intoduce a new class of checking experiments, called uniform checking experiments, in which the entire input sequence, including the initialization part, is preset. The input sequence of a uniform checking experiment is called a uniform checking sequence. It is shown that every sequential machine possesses a uniform checking sequence. Trivially, if the machine has a synchronizing sequence, then the checking sequence constructed by employing any existent procedure is a uniform checking sequence. Some classes of machines which do not have synchronizing sequences are given and discussed. They are permutation machines, cycle machines, and symmetry machines. Different procedures for constructing efficient uniform checking sequences for them are then derived. It is found that while uniform checking sequences may be considerably longer than conventional checking sequences for arbitrary machines with no synchronizing sequences, the above classes of machines are shown to have uniform checking sequences comparable in length to conventional checking sequence.

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1 000 000 gate evaluations/sec can be achieved.

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1,000,000 gate evaluations/second can be achieved.

Special-purpose CAD hardware is increasingly being considered as a means to meet the challenge posed to conventional (software-based) CAD tools by the growing complexity of VLSI circuits. In this paper we describe the architecture of a logic simulation machine employing distributed and parallel processing. Our architecture can accommodate different levels of modeling ranging from simple gates to complex functions, and support timing analysis. We estimate that simulation implemented by the proposed special-purpose hardware will be between 10 and 60 times faster than currently used software algorithms running on general-purpose computers. With the available technology, a throughput of 1,000,000 gate evaluations/second can be achieved.

This paper proposes an extension of the D-algorithm to functions described in computer hardware description languages. The proposed extension is applicable to both procedural and nonprocedural languages. Methods of D-propagation through the basic constructs of these languages and test generation for circuits containing functions described in CHDL's are discussed. The fault modes considered are function variables stuck at 0 or 1, control faults, and function faults with user-specified faulty behaviors.

This paper presents a method of propagating the effects of faults through functional blocks using the deductive (fault list) technique. An extension of the method is shown to be effective for simulating internal faults in functional blocks. The techniques presented here have been used for implementing the functional simulation capability in the Logic Analysis for Maintenance Planning (LAMP) System at Bell Laboratories.

The effective use of simulation for logic verification and test evaluation frequently requires simulation capabilities at different levels of detail. This paper discusses the functional level simulation capability in the LAMP system at Bell Laboratories and its relation to gate level simulation. The Function Definition Language (FDL) used for specifying the behavior of functional blocks is discussed. Functions described in this language can be embedded in gate level circuits and simulated to determine the normal circuit behavior or faulty behavior. Classical faults external to functions and user specified internal faults in functions may be simulated. The effectiveness of functional simulation has been demonstrated in a number of applications such as memory modules in a large controller of an Electronic Switching System, the ROM in a small controller and an entire microprocessor treated as an interconnection of a few functional blocks.

This paper shows that the imposition of some restrictions on the realization of a sequential machine facilitates the derivation of efficient checking sequences for some machines. Specifically, it is assumed that the state logic or the output logic may be faulty, but both of them cannot be faulty at the same time. This condition is satisfied if there is no shared logic between the state and output logic and at most a single fault in the circuit. It is also assumed that the normal machine has a synchronizing sequence. With these restrictions on the realization, the machine identification approach may be used to derive checking sequences that are often shorter than those without the restrictions and detect a larger set of faults than with the circuit testing approach.

This correspondence shows that, contrary to a statement in the cited paper, fault location is sometimes possible in one-dimensional arrays in which only the outputs of the rightmost cell are observable.

This note considers the operation of systems composed of interconnected asynchronously operating modules and shows that some such systems may enter "blocking conditions" in which no module can change state. The model considered applies specifically to asynchronous systems in which each module is controlled only by its neighbors, but may also be relevant to other systems such as parallel computational schemes. We also demonstrate a procedure that may speed up computation and we show that the function computed by a given network may depend upon the initial state.

Kautz has studied the problem of testing one-and two-dimensional arrays of combinational cells under the assumptions that all cell inputs must be applied to a cell to test it completely and that a fault in a cell may cause any arbitrary change in its outputs. In this paper we study the same problem under a more restricted set of assumptions: 1) all faults in a cell can be detected by a known set of inputs (usually smaller than the set of all inputs); and 2) each fault will affect the cell outputs in a known manner. Necessary and sufficient conditions for detection of faults in one-dimensional arrays are obtained. A procedure for deriving efficient tests for one-dimensional arrays is presented. Sufficient conditions for the testability of two-dimensional arrays and procedures for constructing tests for some arrays are obtained.

This paper considers the general problem of the synthesis of asynchronous combinational and sequential circuits based on the assumption that gate delays may be unbounded and that line delays are suitably constrained. Certain problems inherent to circuit realizations with unbounded gate delays are discussed and methods of solving them are proposed. Specific synthesis techniques are presented for both combinational and sequential circuits. The use of completion detection necessitated by the assumption of unbounded gate delays also causes the circuits to stop operating for approximately half of all possible single faults, thus achieving a degree of self-checking.

In this paper, we extend the partition theory developed by Hartmanis and Stearns for synchronous sequential circuits to asynchronous sequential circuits. A method which utilizes the concept of partition pairs to obtain single transition time asynchronous state assignments with reduced dependence is presented. Parallel and serial decompositions of asynchronous sequential circuits are also considered. Single transition time and multiple transition time serial decompositions are discussed and procedures for obtaining such decompositions are presented.

Abstract—In an earlier paper, Unger showed that any normal mode flow table can be realized by an asynchronous sequential circuit without inserted delays in the feedback paths if and only if the flow table contains no essential hazards. No restrictions were placed on the relative magnitudes of line and gate delays. In this paper, we show that if the line delays are less than the minimum gate delay in the circuit, any normal mode sequential function can be realized without inserted delays. It is also shown that a weaker line delay assumption is sufficient. Two procedures for realizing asynchronous sequential circuits without inserted delays are presented.

Abstract—A frequently imposed restriction in theoretical treatments of asynchronous sequential circuits is that only one input variable be allowed to change during a transition. In this paper, we present three methods for realizing asynchronous sequential circuits allowing multiple-input changes, but requiring that all input changes associated with an input transition be completed within a specified time after the first change. We also show that a single delay element is sufficient in the realization of normal mode flow tables, under these conditions.