AN EFFICIENT STATE-SPACE SEARCH FOR THE SYNTHESIS OF ASYNCHRONOUS CIRCUITS BY SUBSPACE CONSTRUCTION

In this paper, an approach to derive a logic Function of asynchronous circuits from a graph-based model called Signal Transition Graphs (STG )[1] is discussed. STG's are Petri nets[2], whose transitions are inte rpreted as a signal transition on the circuit inputs or gate outputs, and its marking represents a binary state of the circuit. STG's can re present a behavior of circuit. to derive logic functions, however, the reachability graph should be constructed. In the verification of STG' s some method based on Occurrence nets (OCN) and its prefix, called un folding, has been proposed[3],[4]. OCN's can represent both causality and concurrency between two nodes by net structure. In this paper, we propose a method to derive a logic function by generating substate spa ce of a given STG using the structural properties of OCN. The proposed method can be seem as a parallel algorithm for deriving a logic funct ion.