An Efficient State Space Search for the Synthesis of Asynchronous Circuits by Subspace Construction

Toshiyuki MIYAMOTO  Dong-Ik LEE  Sadatoshi KUMAGAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.11   pp.1504-1510
Publication Date: 1995/11/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Net Theory and Its Applications to Discrete Event System Design)
Category: 
Keyword: 
signal transition graph,  occurrence net,  asynchronous circuit,  derive logic functions,  state space explosion,  

Full Text: PDF(618.3KB)>>
Buy this Article




Summary: 
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.