计算机应用 ›› 2010, Vol. 30 ›› Issue (05): 1390-1393.

• 典型应用 • 上一篇    下一篇

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

黄越1,于宗光2,万书芹3   

  1. 1. 江南大学
    2. 江南大学 信息工程学院;中国电子科技集团公司 第五十八研究所
    3. 江南大学信息工程学院
  • 收稿日期:2009-11-30 修回日期:2010-01-25 发布日期:2010-05-04 出版日期:2010-05-01
  • 通讯作者: 黄越
  • 基金资助:
    江苏省自然科学基金

Non-backtracking multipath algorithm for test pattern generation

  • Received:2009-11-30 Revised:2010-01-25 Online:2010-05-04 Published:2010-05-01

摘要: 无回溯并行多路径搜索算法(NBMP)在生成测试向量过程中生成基于原始输入端奇异立方和与原始输出端关联的传输立方,并利用生成的奇异立方和传输立方生成测试向量。算法在实现过程采用无须回溯和多路径探索策略。通过分析和实验结果证明算法时间复杂度近似为线性。算法对ISCAS85基准电路中规模最大的8个电路进行实验,将实验结果与传统算法进行比较,结果表明NBMP算法故障覆盖率优于传统算法。

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

Abstract: 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.

Key words: digital circuits, benchmark circuits, test pattern generation, fault coverage, multipath