Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms

Srinivas Devadas, Kurt Keutzer, Sharad Malik

Research output: Contribution to journalArticle

57 Scopus citations

Abstract

This paper addresses the problem of accurately computing the delay of a combinational logic circuit in the floating mode of operation. (In this mode the state of the circuit is considered to be unknown when a vector is applied at the inputs.) It is well known that using the length of the topologically longest path as an estimate of circuit delay may be pessimistic since this path may be false, i.e., it cannot propagate an event. Thus, the true delay corresponds to the length of the longest true path. This forces us to examine the conditions under which a path is true. We introduce the notion of static cosensitization of paths which leads us to necessary and sufficient conditions for determining the truth or falsity of a single path, or a set of paths. We apply these results to develop a delay computation algorithm that has the unique feature that it is able to determine the truth or falsity of entire sets of paths simultaneously. This algorithm uses conventional stuck-at-fault testing techniques to arrive at a delay computation method that is both correct and computationally practical, even for particularly difficult circuits.

Original languageEnglish (US)
Pages (from-to)1913-1923
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume12
Issue number12
DOIs
StatePublished - Dec 1993

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms'. Together they form a unique fingerprint.

  • Cite this