Verification Algorithm of a Sequential Circuit's Equivalence Based on State Transfer Graph

摘要

An equivalence verification algorithm of sequential circuits based on state transfer graph (STG) is presented in this paper, which obtains some certain useful information through verifying the corresponding state transfer graphs' isomorphism, namely that two corresponding sequential circuits' equivalence. And the verifying includes two steps: firstly, find out all state pairs of the vertexes, which are being verified; secondly verify the equivalence of state pairs, if all the state pairs can be matched as equal state pairs, thus we can come to a conclusion that the corresponding circuits have the same sequential behavior. The algorithm mainly verifies ISCAS85 circuits and some simple state transfer graphs, and the final experiment data shows that the algorithm introduced in the paper will obtain better results compared to BDD (Binary Decision Diagram) and SET (Symbolic Trajectory Evaluation) methods.