INCREDYBLE - A NEW SEARCH STRATEGY FOR DESIGN AUTOMATION PROBLEMS WITH APPLICATIONS TO TESTING

A new search strategy for design automation problems is proposed, that is directly applicable to circuits having a size parameter (e.g., ope rand size), and indirectly, to random-logic circuits as well. Under th e proposed approach, exhaustive search for an optimal solution is perf ormed for small versions of the target circuit, obtained by scaling-do wn all the size parameters of the circuit (e.g., by reducing the opera nd size). The optimal solutions obtained for the small circuits are st udied, and analytic rules are derived to capture their common features . Using these rules, the solutions are scaled-up into a high-quality s olution for the large target circuit. The method, its feasibility and limitations are described in this work. The method is applied to two p roblems related to testing of digital circuits, namely, test generatio n for stuck-at faults and test generation for path delay faults.