Hardware-optimal test register insertion

Implementing a built-in self-test by a “test per clock” scheme offers advantages concerning fault coverage, detection of delay faults, and test application time. Such a scheme is implemented by test registers, for instance built-in logic block observers (BILBO´s) and concurrent BILBO´s (CBILBO´s), which are inserted into the circuit structure at appropriate places. An algorithm is presented which is able to find the cost optimal placement of test registers for nearly all the ISCAS´89 sequential benchmark circuits, and a suboptimal solution with slightly higher costs is obtained for all the circuits within a few minutes of computing time. The algorithm can also be applied to the Minimum Feedback Vertex Set problem in partial scan design, and an optimal solution is found for all the benchmark circuits. The provably optimal solutions for the benchmark circuits mainly use CBILBO´s which can simultaneously generate test patterns and compact test responses. Hence, test scheduling is not required, test control is simplified, and test application time is reduced