Development of new algorithms for test generation and simulation of stuck at faults in logic circuits

Abstract

Testing is an integral part of integrated circuits manufacturing process and is essential to screen defective parts before shipping the product to the customers. In view ofthe increasing circuit complexity ofthe integrated circuits there is a need for computer-aided design (CAD) tools to automate the various steps in the design process. Automatic Test Pattern Generation (ATPG) is one of the most difficult problems for electronic design automation and has been a popular research topic for more than thirty years. Test generation for sequential circuits is a search problem over large vector space proportional to the number of inputs and number of states and is a NPcomplete problem. Genetic Algorithms are very powerful for many search and optimisation problems and have shown promise in solving NP-complete problems using reasonable CPU time. Often a fault simulation procedure is integrated within an automatic test pattern generation system. Delay models used during the simulation greatly affect the quality of the simulation results, typically, when the circuit has asynchronous parts. The delay of a logic gate and interconnect is affected by various fabrication process parameters and it is difficult to model the process uncertainties. Fuzzy logic can deal with the vagueness and uncertainty inherent in natural language and human thinking. Fuzzy systems have been successfully applied to many problems in decision-making. This thesis presents algorithms for test generation and simulation of single stuck-at faults in sequential circuits. Genetic Algorithms and Fuzzy Logic are used as the tools for test generation and fault simulation. Experimental results are presented for standard benchmark circuits. Two new crossover operators for GA based test generation are proposed. The effectiveness of the proposed operators and adaptive genetic algorithm for testing sequential circuits are analysed. A two-phase automatic test pattern generation algorithm using Guided Genetic Algorithm is proposed and investigated. The distributed version ofthe Guided Genetic Algorithm based ATPG is developed and tested. A simulation algorithm, FDSIM, is presented for asynchronous sequential circuits. A novel fuzzy delay model that can handle uncertainty, which is implicit in the design and manufacturing flow, is used as the delay model during simulation. The applicability of FDSIM for testing a class of asynchronous sequential circuits using synchronous test model has been studied. Test results for embedded asynchronous sequential circuits are also reported. Test generation algorithms in Genetic Algorithms and Guided Genetic Algorithm frameworks are formulated and investigated for asynchronous sequential circuits. Fault simulator based on the proposed FDSIM is used for computing the fitness function.