On the general false path problem in timing analysis

David H.C. Du, Steve H.E. Yen, S. Ghanta

Research output: Contribution to journalConference articlepeer-review

60 Scopus citations


The false path problem is often referred to as the problem of detecting the longest sensitizable path (a path that is not a false path is a sensitizable path). In the present work, a clear and precise definition of a false path is given. The general false path problem is formulated. The general false path problem is to detect whether a given path (not necessarily the longest one) is a false path. An efficient algorithm for solving the general false path problem is presented. Another algorithm which generates all the possible sensitizable paths with the delays greater than a given threshold T is proposed. As a result of the elimination of most of the false paths, a much higher confidence can be placed in the timing verifier. The efficiency and effectiveness of the latter algorithm are demonstrated by experimental results.

Original languageEnglish (US)
Pages (from-to)555-560
Number of pages6
JournalProceedings - Design Automation Conference
StatePublished - 1989
Event26th ACM/IEEE Design Automation Conference - Las Vegas, NV, USA
Duration: Jun 25 1989Jun 29 1989

Cite this