A POLYNOMIAL-TIME HEURISTIC APPROACH TO SOLVING THE FALSE PATH PROBLEM

In this paper we present a new approach to solving the false path prob lem, The method is based on our previous work on Timed Boolean Algebra [13], Given a logic circuit, we first derive timed Boolean expression s to model its dynamic behavior, Then, for each term in the expression s, we compute its corresponding sensitizability function, expressed in conjunction normal form; and use an expression in product form to app roximate the function, Finally we remove the redundant terms whose sen sitizability functions are not satisfiable and determine the maximal d elays from the terms remained, Complexity analysis shows that our meth od identifies false paths and computes delays for sensitizable paths i n polynomial time, while experimental results on ISCAS benchmark circu its prove its better efficiency and effectiveness.