Failures Guide Probabilistic Search for a Hard-to-Find Test

摘要

Previous research has firmly established the NPcomplete nature of the fault detection problem. Various algorithms and techniques have been developed to tackle the worst case computation time for test generation due to the increasing complexity of digital circuits. The development of these techniques over the past 50 years has improved a lot of commercial EDA tools. The efficiency of these tools coupled with the considerable long research period has led to claims that ATPG research may have reached itsr maturity. However, whenever traditional algorithms started hitting their limits, studies in non-traditional techniques have improved test coverage. This paper proposes a foray in the realm of quantum computing in order to find tests for hard to detect stuck-at faults. We were encouraged by a reduced complexity quantum search for an element in an unsorted database proposed by Grover and the similarity of that problem to the search for a test in the vector space. Thus, it may be possible to find tests for the last few difficult to detect stuck-at faults much faster than other contemporary algorithms. This paper presents results of various benchmark circuits by comparing the time taken for our algorithm to run with FastScan's ATPG tool. It is shown that for a difficult todetect fault with limited backtracking, FastScan struggles to finda test while our algorithm is able to efficiently find the test inreasonable time.