无回溯并行多路径搜索测试向量生成算法  

Non-backtracking multipath algorithm for test pattern generation

作　　者：黄越[1] 于宗光[1,2] 万书芹[1] 

机构地区：[1]江南大学信息工程学院,江苏无锡214122 [2]中国电子科技集团公司第五十八研究所,江苏无锡214035

出　　处：《计算机应用》2010年第5期1390-1393,共4页journal of Computer Applications

基　　金：江苏省自然科学基金资助项目(BK2007026);江苏省"333高层次人才培养工程"专项资助项目(2007124)

摘　　要：无回溯并行多路径搜索算法(NBMP)在生成测试向量过程中生成基于原始输入端奇异立方和与原始输出端关联的传输立方,并利用生成的奇异立方和传输立方生成测试向量。算法在实现过程采用无须回溯和多路径探索策略。通过分析和实验结果证明算法时间复杂度近似为线性。算法对ISCAS85基准电路中规模最大的8个电路进行实验,将实验结果与传统算法进行比较,结果表明NBMP算法故障覆盖率优于传统算法。A Non-Backtracking MultiPath （NBMP） algorithm constructed singular cubes containing primary inputs and fault driving cubes connected with primary outputs,and produced test patterns by using generated singular cubes and fault driving cubes.It adopted non-backtracking strategy and multipath searching strategy during processing.The time complexity is proved to approximate linearity by the time complexity analysis and experimental results.Moreover,the fault coverage of test pattern involving eight biggest ISCAS85 benchmarks show that NBMP algorithm is superior to the traditional test generation algorithm.

关 键 词：数字电路 基准电路 测试向量生成 故障覆盖率 多路径 

分 类 号：TP391.76[自动化与计算机技术—计算机应用技术]