Title :
An efficient algorithm for the realizability analysis of signal transition graphs
Author :
Li, H.F. ; Leung, S.C.
Author_Institution :
Dept. of Comput. Sci., Concordia Univ., Montreal, Que., Canada
Abstract :
This paper presents a necessary and sufficient condition for realizability from signal transition graphs to circuits that use the complex gate implementation method. A polynomial time algorithm is developed for checking the condition. The advantages of performing checking in signal transition graphs lie in its avoiding state space enumeration and searching, which incur exponential complexity due to concurrency
Keywords :
VLSI; logic CAD; sequential circuits; VLSI; asynchronous circuits; complex gate implementation method; logic design; polynomial time algorithm; realizability analysis; signal transition graphs; Algorithm design and analysis; Circuit synthesis; Computer science; Concurrent computing; Delay; Polynomials; Signal analysis; Signal synthesis; State-space methods; Testing;
Conference_Titel :
VLSI, 1994. Design Automation of High Performance VLSI Systems. GLSV '94, Proceedings., Fourth Great Lakes Symposium on
Conference_Location :
Notre Dame, IN
Print_ISBN :
0-8186-5610-7
DOI :
10.1109/GLSV.1994.289974
