An Automatic Test Pattern Generation Method for Digital Circuits Based on K-Nearest Neighbor

Automatic test pattern generation (ATPG) based on branch-and-bound search is a key technology in digital circuit testing, and the number of backtracks in the search has a great impact on ATPG performance. In order to reduce the number of ATPG backtracks, a K-nearest neighbor (KNN)-based ATPG method for digital circuits is proposed. The KNN algorithm in machine learning is introduced into the POEDM test generation algorithm. It combines the circuit structure data and testability metric information to guide the selection of the backtrace paths in the PODEM algorithm, replacing the traditional heuristic strategy to reach an effective decision as soon as possible to reduce the number of backtracks. Experimental results on the ISCAS85, ISCAS89, and ITC99 benchmark circuits showed that, compared to traditional heuristic strategies, as well as a backtrace path selection strategy based on artificial neural network (ANN), the proposed method achieved an improvement of 1 625.0%, 466.0%, 260.0%, and 2.2 % respectively, in terms of number of backtracks, number of backtraces, running time, and fault coverage in the best cases. At the same time, in comparison with the ANN-based method, the proposed method can save a certain amount of memory resource overhead because KNN has no explicit training process. In addition, our method consumes much less training data than the ANN-based method does to get an effective prediction model.