Research On Automatic Test Generation Of Sequential Circuits Based On Ant Algorithm

As the increasing of the complexity and density of integrated circuits, test has become the neck bottle for the application of LSI/VLSI. Although some scholars have done lots of work on the test generation of the digital circuits, it is still a well-known puzzle to test sequential circuits. Base on the existing synchronous sequential circuits fault simulator-HOPE, the test vector generation method of sequential circuits based on ant algorithm is systematically researched firstly.The automatic test vector generation method based on fault simulation is described, and the whole procedure of ATPG of sequential circuits is analyzed, fault simulator-HOPE as an example.The basic principle of ant algorithm is discussed, ant algorithm for sequential circuits initialization is presented, and the pheromone computation formula for sequential circuits initialization and status transfer rules are given. Due to the parallel global optimization characteristics of the genetic algorithm, the crossover using ant algorithm and genetic algorithm is adapted to generate the initialization vector of the sequential circuit, for avoiding the local optimization of ant algorithm. The international standard sequential circuits ISCAS'89 (Addendum'93 included) is used to verify the algorithm, and the results are better than other algorithms'.Test vector generation based on ant algorithm is presented and implemented, the pheromone computation formula for sequential circuits and status transfer rules are given, and the test results are compared with the results of the other existing test generators - HITEC, GATEST, CRIS, DIGATE and STRATEGATE,based on standard sequential circuits ISCAS'89 and other synchronous sequential circuits. The conclusion is that by using ant algorithm, the fault coverage about near half standard circuits is best; and the generation speed is very higher than STRATEGATE's.To compensate the shortage of the bigger test set of pure ant algorithm, the method of crossing ant algorithm and genetic algorithm is presented. Meanwhile, the implementation methods of the objective function, selection operator, crossover operator, and mutation operator are given, and the test results are compared with the results of ant algorithm, based on standard sequential circuits ISCAS'89.The results indicate that ant algorithm has the simple, general, robust features, and also has the fast global optimization feature that improves the efficiency of generation, further has important research value and application prospect.Besides, neural network models are firstly established for resolving the problem of MCM interconnect test. And the validity of the models has been verified. Meanwhile, principal methods of applying neural network to MCM interconnect testing are discussed.