Computational Complexity of Test-Point Insertions and Decompositions
Nageswara S. V. Rao, Shunichi Toida · 2005
We consider two basic computational problems that arise in the areas of pseudo-exhaustive testing, design, of polynomial-time testable classes, test-point inuertion, and Crosscheck, in the context of test generation and design for testability of combinational circuits. The first problem is to decom.pose a circuit info subcircuits such that the number of inputs to each subcircuit is bounded by I<; we show that this problem is NP-complete. This result establishes that the detection (minimization) problems associated with three polynomial-time testable classes and the method of pseudo-exhaustive testing are all NP-complete (hard). We then present simple approximation algorith.ms for solving these problems. The second problem deals with placing k test points on a circuit so as to facilitate the observability and/or controllability; this problem is also shown to be NP-hard. This problem arises in, the methods of Crosscheck and segment-cell placem.ent. 1 Tnt roduct ion There are several methods in the area of test generation and design for testability, and in these methods some basic computational problems appear in disguises in seemingly different contexts. We consider two such problems: circuit decompositions with bounded number of inputs for each subcircuit, and computing a subset of nets which can be used to inject and/or inspect signals. The first problem arises in the design of polynomial-time testable classes of combinational circuits [2,3,13], and in the method of pseudo-exhaustive testing [6,9,113. The second problem occurs in the method of segment cell placement [15] and in some parts of the method of CrossCIieck [16]. Despite the differences in the origins of their