TEST PATTERN GENERATION FOR VLSI CIRCUITS

Abstract

Test pattern generation problem is known to be ./VP-complete and conventionally, au tomatic generation of test patterns for circuits with N number of primary inputs is characterized as a search of A-dimensional 0-1 state space. Several Automatic Test Pattern Generation (ATPG) algorithms have been developed in the past. But, in spite of considerable progress in the development of these algorithms, the computational re sources required for ATPG are still enormous because the efficiency of these algorithms has not kept pace with the increasing complexity of VLSI circuits which is of the or der of several tens of thousands of gates. Furthermore, these algorithms are targeted for serial computers. However, massively parallel computers and distributed network of powerful workstations, available in most of the VLSI-CAD environments, present a promising paradigm for solving such compute-intensive ATPG problems for combi national as well as sequential circuits. With the availability of these paradigms, new approaches and cost-effective methods, are therefore, imperative in order to efficiently solve the ATPG problem. Efforts have been made to investigate new test generation algorithms so that they could be easily extended to parallel and distributed computing paradigms. Recently, two different ATPG approaches have been developed in which the problem of test pattern generation is formulated either as aBoolean satisfiability (SAT) or an optimization problem. These approaches are radically different from the conven tional methods of generating test patterns for circuits from their gate level description. In these approaches, the generation of test patterns is done in two steps. In the first step, a formula is constructed which will be either an energy function or a Boolean truth (false) function representing Boolean difference between the fault-free and faulty circuits. In the second step, energy minimization techniques are applied to minimize the energy function or the Boolean false function and SAT algorithms are applied to satisfy the Boolean truth function. Although energy minimization and SAT problems are as hard as ATPG problem itself, these approaches have two significant advantages. First, since the function of the circuit is mathematically expressed, several new tech niques may be investigated to solve the ATPG problem. Second, the non-causal form of the model would allow the use of parallel processing. New techniques for the ATPG approaches as described above have been at tempted in this thesis. In the optimization based approach, a new quadratic 0-1 pro gramming technique to minimize the energy function, which is of the form of pseudo- Boolean quadratic function: E(x) = xTQx + cTx, has been developed and applied to obtain test patterns. Other test generation methods developed are based on Genetic Algorithms (GAs). In these methods, an objective function is derived from either an energy function or a Boolean false function. In order to apply GAs, the constrained ATPG problem has been transformed into the unconstrained one by modifying the ob jective function with the help of a penalty method which is developed by using schema design. The objective function so obtained has been mapped into fitness form which is then maximized to generate test patterns. The above ATPG process has been further accelerated by incorporating a transitive closure algorithm to reduce the Boolean false function to be minimized by GAs. Finally, the proposed ATPG methods have been implemented by developing a CAD tool to run on a Sun Sparc 10 UNIX workstation. This tool has been exercised by generating test patterns for a set of stuck-at faults in several practical example circuits. Experimental results in terms of average CPU time per fault for the example circuits are reported in the thesis. The results obtained by the proposed ATPG methods have also been compared to the results published in the literature for the same example circuits which shows the efficiency and effectiveness of the proposed methods.