We present a robust, efficient algorithm for combinational test generation using a reduction to satisfiability (SAT). The algorithm, Test Generation Using Satisfiability (TEGUS), solves a simplified test set characteristic equation using straightforward but powerful greedy heuristics, ordering the variables using depth-first search and selecting a variable from the next unsatisfied clause at each branching point. For difficult faults, the computation of global implications is iterated, which finds more implications than previous approaches and subsumes structural heuristics such as unique sensitization. Without random tests or fault simulation, TEGUS completes on every fault in the ISCAS networks, demonstrating its robustness, and is ten times faster for those networks which have been completed by previous algorithms. Our implementation of TEGUS can be used as a base line for comparing test generation algorithms; we present comparisons with 45 recently published algorithms. TEGUS combines the advantages of the elegant organization of SAT-based algorithms with the efficiency of structural algorithms.

Proposes an objective criterion for determining if, given a specific circuit technology, a gate model is suitable for synthesis and verification. This is based on relating the analog circuit behavior to the digital model behavior using a formal definition of implementation. We illustrate the type of design errors which occur when the criterion is not satisfied, and introduce a gate model designed to satisfy the criterion.>

The authors introduce an efficient method for generating the functional forms of path analysis problems. They demonstrate that the resulting function is linear in the size of the circuit. The functions are then tested for satisfiability either using a Boolean network satisfiability algorithm suggested by T. Larrabee (1989) or through the construction of BDDs. The effectiveness of the proposed approach is shown for timing analysis and robust path delay-fault test generation. This method also holds promise for both static and dynamic hazard analysis, and for test generation using all other delay-fault models, tau -irredundant fault models, and stuck-open fault models.>

The authors propose some syntactic and semantic extensions to a graphical specification called the signal transition graph (STG). They allow controlled-choice places to have fanout transitions of input signals and arbitrary Boolean expressions can be used as edge labels. They also allow one STG marking to represent more than one state. These extensions allow for a more natural and compact specification of asynchronous behavior. It is also shown that syntactic constraints on STGs are not sufficient to guarantee hazard-free implementations, and techniques are presented to synthesize hazard-free SOP, (sum of products) implementations under both SIC (single input change) and MIC (multiple input change) conditions. The synthesized circuits are speed-independent. They are hazard-free, independently of the gate delay variations, assuming that the circuit operates in fundamental mode.>