Title :
Verification of the speed-independent circuits by STG unfoldings
Author :
Kondratyev, A. ; Taubin, A.
Author_Institution :
Dept. of Comput. Hardware, Aizu Univ., Fukushima, Japan
Abstract :
In this paper we show how to analyze an arbitrary STG for the speed-independence property. The idea of analysis is based on the STG unfolding into an acyclic graph. The improved method of unfolding is suggested, in which the size of the obtained description is always less (or equal in the case of a fully sequential process) than the size of a corresponding state graph. Based on this method the verification algorithms of STG analysis are developed. These algorithms are polynomial from the size of STG unfolding. Their efficiency is considered on the set of benchmarks
Keywords :
circuit analysis computing; STG unfoldings; acyclic graph; fully sequential process; speed-independent circuits verification; state transition graphs; verification algorithms; Algorithm design and analysis; Circuit synthesis; Cities and towns; Formal specifications; Hardware; Logic circuits; Polynomials; Robustness; Signal synthesis; Very large scale integration;
Conference_Titel :
Advanced Research in Asynchronous Circuits and Systems, 1994., Proceedings of the International Symposium on
Conference_Location :
Salt Lake City, UT
Print_ISBN :
0-8186-6210-7
DOI :
10.1109/ASYNC.1994.656287
