Research On SAT-based Test Generation Algorithm For Integrated Circuits

As the scale and complexity of integrated circuit increase at a rapid rate, the integratedcircuit testing becomes much more complex and important. The generated speed anddistribution of test vector are crucial to test convergence speed. Digital circuit includessequential logic and combinational logic, and the sequential circuits test vector generationproblem can be transformed into the combinational circuits test generation vector problem byfull-scan design technology. So, the automated test pattern generation (ATPG) problem ofcombination circuit becomes focus.Due to the recent results of SAT solver algorithm, the research on automated test patterngeneration for combinational circuits is paid attention to. This paper introduces fault modelsof digital circuit, test generation technology and how to change digital circuit fault testingproblem into SAT problem. In this paper,we investigate the classical algorithm of SATsolving (DPLL), local search algorithm and SAT solving process based on genetic algorithm,and analyze two problems come from the combination of genetic algorithm and SAT. One isprematurity phenomena appeared in the solving process, and the other is the local optimumand the convergence rate of the genetic algorithm. This paper proposes the SAT solver basedon the improved genetic algorithm, streamlines the fitness function of genetic algorithm, theselection operator, crossover operator and mutation operator for the features of SAT solvingproblem, and improves ameliorated prematurity phenomena of the local SAT solvingalgorithm.To verify the performance of the SAT solver based on improved genetic algorithm, thecorresponding simulations are performed. The simulation results show that the improvedalgorithm is more efficiency, can reduce the conflict between convergence speed and localoptimal, and determines whether there is a prematurity phenomena and then processes asearly as possible.