A genetic algorithm for automatic generation of test logic for digital circuits

Testing is a key issue in the design and production of digital circuits: the adoption of BIST (Built-in Self-Test) techniques is increasingly popular, but sometimes requires efficient algorithms for the automatic generation of the logic which generates the test vectors applied to the unit under test. This paper addresses the issue of identifying a cellular automaton able to generate input patterns to detect stuck-at faults inside a finite state machine (FSM). A suitable hardware structure is first identified. A genetic algorithm is then proposed, which directly identifies a cellular automaton able to reach a very good fault coverage of the stuck-at faults. The novelty of the method consists in combining the generation of test patterns with the synthesis of a cellular automaton able to reproduce them. Experimental results are provided, which show that in most of the standard benchmark circuits the cellular automaton selected by the genetic algorithm is able to reach a fault coverage close to the maximum one. Our approach is the first attempt of exploiting evolutionary techniques for identifying the hardware for input pattern generation in BIST structures.