A PERFORMANCE STUDY OF GENETIC ALGORITHM AND SIMULATED ANNEALING FOR ATPG

Abstract

Automatic Test Pattern Generation (ATPG) is the process of generating test vectors for a logic circuit in order to detect faults present in the circuit. The problem of generating test vectors is known to be NP-Complete. Hence for very large circuits (ex. VLSI Circuits) the computational resources required for ATPG are enormous. Therefore, new cost-effective concepts are imperative in order to efficiently test such circuits. This dissertation uses a neural network model for simulating the logic circuits. The constraints for test generation are incorporated by joining the neural network of the circuit-under-test and its faulty image (a fault-injected neural network representing the circuit-under-test) back to back at their primary inputs. The primary outputs of the two circuits are connected through an output interface in order to ensure that atleast one primary output of the faulty circuit will differ from the corresponding fault-free circuit output. The circuit under-test, its faulty image, and the output interface constitute the ATPG neural network. For generating the test vectors an energy relaxation algorithm must be used in order to optimize the energy associated with the ATPG neural network. So far the Simulated Annealing technique was considered as the best relaxation algorithm. In this work a new technique, known as genetic algorithm, is used for energy relaxation. The performance of both the techniques are evaluated and from empirical results the applicability of genetic algorithm for ATPG is demonstrated.