AN EFFICIENT HEURISTIC-PROCEDURE FOR SOLVING THE STATE ASSIGNMENT PROBLEM FOR EVENT-BASED SPECIFICATIONS

We propose a novel framework to solve the state assignment problem ari sing from the signal transition graph (STG) representation of an async hronous circuit. We first establish a relation between STG's and finit e state machines (FSM's). Then we solve the STG state assignment probl em by minimizing the number of states in the corresponding FSM and by using a critical race-free state assignment technique. State signal tr ansitions may be added to the original STG. A lower bound on the numbe r of signals necessary to implement the STG is given. Our technique si gnificantly increases the STG applicability as a specification for asy nchronous circuits.