Fault based test minimization using genetic algorithm for two stage combinational circuits

The field of digital systems has undergone a major revolution in recent decades. Circuits are shrinking in physical size while growing both in speed and range of capabilities. This rapid advancement is not without serious problems, however. Especially worrisome are verification and testing, which become more important as the system complexity increases and time-to-market decreases. Genetic algorithms have been very effective when combined with deterministic algorithm for test pattern generation in digital circuits. In this paper, single output logic circuits composed of AND, OR and XOR gates are experimented with the proposed algorithm. Time complexity is polynomial to generate the tests that detect all the stuck-at-faults in these circuits. Electronic industry is spending considerable amount of time in the diagnosis of VLSI chips. This time factor dominates in determining the overall cost of the chip. In this paper, the authors present a new genetic algorithm to minimize test patterns for combinational circuits. The fault-detection problem in combinational circuits is formulated in a new framework. In the proposed work, evolutionary principles are employed in test minimization stage alone. Test minimization stage is cumbersome in deterministic and heuristic methods. Results show that test sets generated using the evolutionary approach are more compact than those generated by earlier approaches for many circuits. The proposed genetic algorithm uses boolean functions in Sum-of-Products form. The authors implemented this algorithm in C programming code. The test patterns generated for boolean functions with considerable number of gates are found to be compact and the results are encouraging.