An important step in using combinational equivalence checkers to verify sequential designs is identifying and matching corresponding compare-points in the two sequential designs to be verified. Both non-function and function-based matching methods are usually employed in commercial verification tools. In this paper, we describe a heuristic algorithm using ATPG for matching comparepoints based on the functionality of the combinational blocks in the sequential designs. Results on industrial-sized circuits show our methods are both practical and efficient.

In this paper we present a method for verifying structurally dissimilar arithmetic circuits which does not depend on knowledge of the circuit's intended behavior. Rather than trying to prove that two outputs are equivalent, the method tries to find an implication of the form A/spl rarr/C where the consequent C states that the outputs are equivalent. If we then prove that the antecedent, A, of the implication is true, then our original outputs must be equivalent. Since the truth of A implies the truth of C, we call this method implicit verification. Unlike previously reported implication techniques, we allow the antecedent A to be the conjunction of many conditions rather than a single condition. In addition to allowing more general antecedents, we give a method for choosing them in a useful manner. Using this implicit verification technique, we have been able to verify a 32/spl times/32 array multiplier versus a 32/spl times/32 Wallace tree multiplier.

In this paper, we present an algorithm for finding a good Ashenhurst decomposition of a switching function.Most current methods for performing this type of decomposition are based on the Roth-Karp algorithm.The algorithm presented here is based on finding an optimal cut in a BDD.This algorithm differs from previous decomposition algorithms in that the cut determines the size and composition of the bound set and the free set.Other methods examine all possible bound sets of an arbitrary size.We have applied this method to decomposing functions into sets of -variable functions.This is a required step when implementing a function using a lookup table (LUT) based FPGA.The results compare very favorably to existing implementations of Roth-Karp decomposition methods.

We present a new algorithm for generating tests for single stuck line (SSL) faults in combinational logic circuits using a combination of Boolean and path-oriented techniques. We use Boolean techniques employing the ordered binary decision diagram (BDD) to limit the effect of hard faults on the performance of the algorithm. We use path-oriented techniques similar to those in conventional test generation algorithms to limit the number of algebraic operations that must be performed. The test set generated for each fault is exhaustive in the sense that we find all test patterns which make the fault observable at some primary output. We implemented the algorithm as the program TSUNAMI and applied it to the standard ISCAS '85 and ISCAS '89 benchmark circuits. Results indicate that for circuits which are amenable to analysis by BDD's, TSUNAMI performs significantly better than conventional algorithms such as FAN or EST in generating tests for all targeted faults. Moreover, TSUNAMI finds a large set of test vectors for each fault. The program can easily manipulate these sets of vectors to produce test vectors which test many faults. As a result, we are able to compress the sets of vectors into a very small total number of patterns.

A method for performing Boolean division and factorization using a new cofactor operation, the interval cofactor, is proposed. This method Is efficiently implemented using BDD's and allows for the use of external and internal don't care sets. As well as generating a normal factored form, the method also generates an extended factored form that allows for the use of the exclusive-OR function in the expression. Using this extended form, much better factorizations may sometimes be found. The method was implemented in Catamount, a logic synthesis system currently under development. The method compares favorably to existing algebraic methods.>

The maximum flexibility of a function at a node in a Boolean network is described by the incompletely specified function formed using the union of the satisfiability don't-care set (SDC) and observability don't-care set (ODC) of the node. The normal representation of these sets depends on every variable in the network, can be quite large and may be hard to compute. Usually, we are only interested in the don't care set when restricted to a certain set of variables. We give a formulation for the don't care set of a node in terms of a pre-specified set of variables and prove that this formulation is the maximum projection of the entire don't care set onto the chosen set of variables. This formulation allows computation to start at the target node and proceed by traversing the network outwards. The computation may be stopped at any time yielding a valid subset of the don't care set.