Study On Automatic Test Pattern Generation For Digital Circuit Based On Ant Colony Algorithm

The goal of Automatic Test Pattern Generation(ATPG) is to reduce generation time and improve quality of test pattern, and the two key steps of ATPG are generation and optimization of test pattern set. As complexity of digital circuit is increasing, test generation is becoming more difficult. Ant Colony Algorithm(ACA) is a novel evolutionary algorithm with the characteristics of positive feedback, robustness and parallel distributed computation, and has shown its advantage in a serials of combinatorial optimization problems. The nature of test generation is a combinatorial optimization problem, thus introduction of ACA into ATPG can reduce complexity of the difficult problem. With the project issued by China Aerospace Science and Industry Corporation, Study of Automatic Test Pattern Generation and Development Environment for Digital Test, in the background, Aimed at test pattern generation problem in test and fault diagnosis for digital circuit, based on the basic ACA, generation and optimization of test patterns for digital circuit is studied in this paper. Detail research contents are as follows: Search mechanism and colony intelligence of original ACA are analyzed, and the feasibility for introducing ACA into ATPG is argumented. Aimed at its shortage of easiness to be traped by local optimization value and needing transcendent knowledge to set some parameters, several problems needing to be specially considered for using in ATPG is pointed out. On the basis of improvement of pheromone updating rule of basic ACA, an ATPG method based on improved ACA is presented, resolving the two hard problems within ATPG for synchronous sequential circuit, state initialization of registers and fault detection. Contrasted with ATPG method based on Genetic Algorithm, the algorithm presented has the excellence of much more adaptability and higher fault coverage. On the basis of modification of such controlling parameters as volatilization coefficient of pheromone, ACA is introduced into test set optimization, and test set optimization method based on ACA is presented. Contrast of simulation data with some other test set optimization methods reveals its better performance.