Timed Boolean calculus and its applications in timing analysis

Abstract

Introduces a formalism, called timed Boolean calculus (TBC), and its applications to solving the false path problem in timing analysis. TBC is an extension of conventional Boolean algebra with a delay operator to facilitate modeling the timing behavior of logic circuits. By performing algebraic manipulations on timed Boolean expressions, the actual maximal delays of logic circuits can be obtained. The delay information can then be used by a path reporting algorithm to detect the long false paths, thereby identifying the paths which need be optimized to meet timing constraints. The authors have developed a timing analysis tool based on TBC and tested on ISCAS benchmarks. Experimental results are shown to justify the effectiveness and efficiency of the proposed TBC and algorithms.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>