STG-level decomposition and resynthesis of speed-independent circuits

Ren Der Chen, Jer Min Jou

Research output: Contribution to journalArticlepeer-review


This paper presents a time-efficient method for the decomposition and resynthesis of speed-independent (SI) circuits. Given the specification of an SI circuit, our method first generates its standard C implementation. Then, the combinational decomposition is performed to decompose each high-fanin gate that does not exist in the gate library into some available low-fanin gates. The time efficiency of our method is achieved in two ways. First, the signal transition graph (STG), whose complexity is polynomial in the worst case, is adopted as our input specification. Second, to reduce the resynthesis cycles, which constitute a major part of the run time, our method first investigates the hazard-free decomposition of each high-fanin gate without adding any signals. Then, for those gates that cannot be decomposed hazard free, two signal-adding methods constructed at the STG level are developed for resynthesis. This decomposition and resynthesis process is iterated until all high-fanin gates are successfully decomposed or no solution can be found. Several experiments have been done on the asynchronous benchmarks and it can be seen from the results that our method largely reduces the run time only at a little more area expense when compared with previous work.

Original languageEnglish
Pages (from-to)1751-1763
Number of pages13
JournalIEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications
Issue number12
Publication statusPublished - 2002 Dec

All Science Journal Classification (ASJC) codes

  • Electrical and Electronic Engineering


Dive into the research topics of 'STG-level decomposition and resynthesis of speed-independent circuits'. Together they form a unique fingerprint.

Cite this