For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Efficient State Space Search for the Synthesis of Asynchronous Circuits by Subspace Construction
Toshiyuki MIYAMOTO Dong-Ik LEE Sadatoshi KUMAGAI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/11/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Net Theory and Its Applications to Discrete Event System Design)
signal transition graph, occurrence net, asynchronous circuit, derive logic functions, state space explosion,
Full Text: PDF(618.3KB)>>
In this paper, an approach to derive a logic function of asynchronous circuits from a graph-based model called Signal Transition Graphs (STG) is discussed. STG's are Petri nets, whose transitions are interpreted as a signal transition on the circuit inputs or gate outputs, and its marking represents a binary state of the circuit. STG's can represent 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 unfolding, has been proposed. 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 space of a given STG using the structural properties of OCN. The proposed method can be seem as a parallel algorithm for deriving a logic function.