Sequential equivalence checking without state space traversal
C.A.J. van Eijk · 1998
Because general algorithms for sequential equivalence checking require a state space traversal of the product machine, they are computationally expensive. In this paper, we present a new method for sequential equivalence checking which utilizes functionally equivalent signals to prove the equivalence of both circuits, thereby avoiding the state space traversal. The effectiveness of the proposed method is confirmed by experimental results on retimed and optimized ISCAS'89 benchmarks. 1. Introduction With the increasing use of sequential optimizations during logic synthesis, sequential equivalence checking is becoming an important practical verification problem. Conventional algorithms for solving this problem require a state space traversal of the product machine. Impressive progress has been made in this area by the introduction of so-called symbolic techniques, which are based on the application of binary decision diagrams (BDDs) to traverse the state space (see e.g. [2] for an over...