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

Non-backtracking multipath algorithm for test pattern generation

无回溯并行多路径搜索算法(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.