ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (11): 2448-2457.doi: 10.7544/issn1000-1239.2019.20180754

• 人工智能 • 上一篇    下一篇

基于极小碰集求解算法的测试向量集约简

欧阳丹彤1,3,陈晓艳1,叶靖2,4,邓召勇1,张立明1,3   

  1. 1(吉林大学计算机科学与技术学院 长春 130012);2(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190);3(符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012);4(中国科学院计算技术研究所 北京 100190) (ouyangdantong@163.com)
  • 出版日期: 2019-11-12
  • 基金资助: 
    国家自然科学基金项目(61672261,61502199,61402196,61872159,61704174)

Test Pattern Set Reduction Based on the Method of Computing Minimal Hitting Set

Ouyang Dantong1,3, Chen Xiaoyan1, Ye Jing2,4, Deng Zhaoyong1, Zhang Liming1,3   

  1. 1(College of Computer Science and Technology, Jilin University, Changchun 130012);2(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190);3(Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012);4(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)
  • Online: 2019-11-12

摘要: 自动测试向量生成的目的是对特定的故障模型确定1个高质量测试向量集使得芯片(设计)的故障覆盖率达到期望值,在芯片测试中是非常重要的环节.TetraMAX ATPG 2018是众多ATPG工具中功能最强、最易于使用的自动测试向量生成工具,可以在很短的时间内生成具有高故障覆盖率的高质量测试向量集.提出基于极小碰集求解算法的极小完全测试向量集求解算法,通过对测试向量集约简问题重新建模,利用极小碰集求解算法对TetraMAX ATPG 2018产生的测试向量集进行约简.利用这一算法可以有效地缩减测试向量集规模,且保证其故障覆盖率不变,对降低芯片的测试成本有着重要的现实意义.实验针对固定型故障,结果表明:该算法具有良好的约简效果,而且可以保证所得测试向量集中不包含冗余的测试向量.

关键词: 电路测试, 自动测试向量生成, 测试向量集, 约简, 故障覆盖率, 极小碰集, 固定型故障

Abstract: The purpose of automatic test pattern generation (ATPG) is to determine a high-quality set of test patterns for a particular fault model. Automatic test pattern generation is a very important part in chip testing. Through using the test set, generated by the automatic test pattern generation process, we can detect most of the faults in the circuit so that the fault coverage of the chip (design) can reach the desired value. Nowadays, there are many commercial tools available to generate the set of test patterns. Among these tools, TetraMAX ATPG 2018 is the most powerful and easy-to-use automatic test pattern generation tool. It can generate the highest quality test pattern set with the highest fault coverage in the shortest amount of time. In this paper, a method for computing minimal complete test pattern set based on the minimal hitting set method is proposed. By re-modeling the test pattern set reduction problem, the test set generated by TetraMAX ATPG 2018 is reduced with the method of computing minimal hitting set. This method can effectively reduce the scale of the test pattern set and ensure that the fault coverage of the test set does not change. It has important practical significance to reduce the test cost of the chip. In the experimental part of the paper, we use stuck-at fault as the fault model. The experimental results show that the proposed method can effectively reduce the size of the test set. At the same time, the method we proposed can guarantee that the obtained test pattern set does not contain redundant test pattern.

Key words: circuit test, automatic test pattern generation (ATPG), test pattern set, reduction, fault coverage, minimal hitting set, stuck-at fault

中图分类号: