Delay abstraction in combinational logic circuits

Noriya Kobayashi, Sharad Malik

Research output: Contribution to conferencePaperpeer-review


In this paper we propose a data structure for abstracting the delay information of a combinatorial circuit. The particular abstraction that we are interested in is one that preserves the delays between all pairs of inputs and outputs in the circuit. The proposed graphical data structure is of size proportional to (m + n) in best case, where m and n refer to the number of inputs and outputs of the circuit. In comparison, a delay matrix that stores the maximum delay between each input/output pair has size proportional to m × n. We present heuristic algorithms for deriving these concise delay networks. Experimental results shows that, in practice, we can obtain concise delay network with the number of edges being a small multiple of (m + n).

Original languageEnglish (US)
Number of pages6
StatePublished - 1995
Externally publishedYes
EventProceedings of the 1995 Asia and South Pacific Design Automation Conference, ASP-DAC'95 - Chiba, Jpn
Duration: Aug 29 1995Sep 1 1995


OtherProceedings of the 1995 Asia and South Pacific Design Automation Conference, ASP-DAC'95
CityChiba, Jpn

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Delay abstraction in combinational logic circuits'. Together they form a unique fingerprint.

Cite this