Database Search and ATPG -- Interdisciplinary Domains and Algorithms
Muralidharan Venkatasubramanian, Vishwani D. Agrawal · 2016
A circuit with n primary inputs (PIs) has N = nth-power-of-2 possible input vectors. A test vector to correctly detect a fault in that circuit must be among those N n-bit combinations. Clearly, this problem can be rephrased as a database search problem. Classic algorithms like the D-algorithm, PODEM and FAN have long been foundations other algorithms have built upon to vastly improve the search time for test vectors Since, all testing algorithms can be interpreted as unsorted database search methods, it is to our benefit if we choose to create a testing algorithm based on an efficient solution to database search. Currently, it has been shown that Grover's quantum computing algorithm is the best solution to search a database of N elements with sub-linear square root-N complexity, while most other algorithms are linear. Hence, it is clear that creating a testing algorithm that emulates Grover's algorithm for finding test vectors could be a faster solution for VLSI Testing. This review paper attempts to explain the relationship between testing algorithms and database search problems, how there is currently a best solution for database search, and the need to attempt to create a solution based on Grover's algorithm.