ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2019, Vol. 56 ›› Issue (11): 2448-2457.doi: 10.7544/issn1000-1239.2019.20180754

Previous Articles     Next Articles

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

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

CLC Number: