Hybrid algorithm for test point selection for scan-based BIST

We propose a new algorithm for test point selection for scan-based BIST. The new algorithm combines the advantages of both explicit-testability-calculation and gradient techniques. The test point selection is guided by a cost function which is partially based on explicit testability recalculation and partially on gradients. With an event-driven mechanism, it can quickly identify a set of nodes whose testability need to be recalculated due to a test point, and then use gradients to estimate the impact of the rest of the circuit. In addition, by incorporating timing information into the cost function, timing penalty caused by test points can be easily avoided. We present the results to illustrate that high fault coverages for both area- and timing-driven test point insertions can be obtained with a small number of test points. The results also indicate a significant reduction of computational complexity while the qualities are similar to the explicity-testability-calculation method.