Study On Algorithms Of Test Pattern Generation For Sequential Circuits

In order to solve the hard problem of testing for synchronous sequential circuits, improve the test generation efficiency of sequential circuits, this dissertation studies the algorithms of test pattern generation for sequential circuits. In recent years, with the rapid development of evolution algorithms, they have been used widely in the field of combination optimization. After comparing several kinds of evolution algorithms, this dissertation applies the ant algorithm, genetic algorithm and particle swarm algorithm into test pattern generation of sequential circuits, so as to obtain high-efficient test pattern generators of sequential circuits.This dissertation discusses the technique of automatic test pattern generation for sequential circuits, and the pre-processing technique of circuits, fault simulation technique for accelerating the test generation.Based on the basic theory of ant algorithm and genetic algorithm, combined with the structure characteristic,this dissertation presents the automatic test generation model of sequential circuits based on ant algorithm and genetic algorithm, and performs several kinds of experiment on international benchmark sequential circuits ISCAS'89 to verify the presented method. Compared with other similar test generation algorithms, this study can achieve higher fault coverages and more compact test sets and prove the combined method is successful. Besides, in order to get more compact test vectors, vector omission, a static compaction technique, is used to do post-processing to compact the sequences generated by ant-based.Because particle swarm optimization algorithm is simple, which can avoid complicated genetic operation, this dissertation, by using its specific memory function, applies it to the test generation of sequential circuits. Discrete PSO algorithm model for sequential circuits is created and experiments for ISCAS'89 are performed.Furthermore, in order to overcome the shortcomings of PSO algorithm, i.e., getting into logjam easily, low search precision, and slow convergence speed in the latter evolution period, this dissertation combines PSO algorithm with ant algorithm to achieve test generation. Experimental results for ISCAS'89 are listed to verify the method.Because simulation-based test generation can't identify untestable faults, the dissertation addresses the problem by combining it with deterministic algorithm. SAT algorithm is introduced into the test generation based on ant algorithm and genetic...