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 path in the PODEM algorithm, replacing the traditional heuristic strategy to reach an effective decision as soon as possible to reduce the number of backtracks. Through validation on the ISCAS85, ISCAS89, and ITC99 benchmark circuits, the proposed method compared to traditional heuristic strategies, as well as the backtrace path selection strategy based on artificial neural network (ANN), achieved the highest increases of 1625%, 466%, 260%, and 2.2% in the number of backtracks, backtraces, running time, and fault coverage rate, respectively. 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 to get an effective prediction model.