基于K近邻的数字电路自动测试向量生成方法

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

基于分支限界搜索的自动测试向量生成(ATPG)是数字电路测试中的关键技术,搜索中的回溯次数对ATPG性能造成很大影响.为了减少ATPG回溯次数,提出一种基于K近邻(KNN)的数字电路ATPG方法.将机器学习中的KNN算法引入POEDM测试生成算法,KNN结合电路结构数据和可测试性度量信息来指导PODEM算法中回退路径的选择,替代传统的启发式策略,以尽快地到达有效决策点,减少回溯次数.在ISCAS85,ISCAS89和ITC99基准电路上进行验证,与传统启发式策略以及一种基于人工神经网络(ANN)的回退路径选择策略相比,所提方法在回溯次数、回退次数、运行时间和故障覆盖率指标方面分别实现了最高1625.0%,466.0%,260.0%和2.2%的改进.同时,相比基于ANN的方法,KNN没有显式的训练过程,在搭建模型阶段能够节省一定的显存资源开销,并且可以使用更少的训练集样本得到有效的预测模型.

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 1625.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.