USING CONNECTIVITY AND SPECTRAL METHODS TO CHARACTERIZE THE STRUCTUREOF SEQUENTIAL LOGIC-CIRCUITS

Representing finite state systems by means of finite state machines is a common approach in VLSI circuit design. BDD-based algorithms have m ade possible the manipulation of FSMs with very large state spaces; ho wever, when the representation of the set of reachable states grows to o much, the original FSM is no longer manageable as a whole, and it ne eds to be decomposed into smaller sub-machines, Structural analysis of the circuit from which the FSM has been extracted has shown to be ver y effective to determine good state variable partitions which induce F SM decomposition for logic synthesis and formal verification applicati ons. In this paper we propose FSM analysis techniques based on connect ivity and spectral characteristics of the state machine which take int o account the mutual dependency of the state variables, but which are no longer dependent on the structure of the underlying circuit; theref ore, they may be used in a context different from sequential logic opt imization and FSM verification. Experimental results are presented and discussed for the MCNC'91 FSM benchmarks and for the ISCAS'89 sequent ial circuits,