THEORY AND APPLICATION OF NONGROUP CELLULAR-AUTOMATA FOR SYNTHESIS OFEASILY TESTABLE FINITE-STATE MACHINES

This paper reports some of the interesting properties and relationship s of a nongroup Cellular Automata (CA) and its dual. A special class o f nongroup Cellular Automata denoted as D1CA is analytically investig ated. Based on such analysis, D1CA has been proposed as an ideal test machine which can be efficiently embedded in a finite state machine t o enhance the testability of the synthesized design. A state encoding algorithm has been formulated to embed the D1CA based test machine in the synthesized FSM while minimizing the hardware overhead. The Uniqu e state transition properties of D1CA are then used in designing an e asy testing scheme for the FSM. Experiments on FSM benchmarks have sho wn that the scheme achieves 100% coverage of all single stuck-at fault s at the cost of hardware overhead and circuit delay that are comparab le, ii not better, to that incurred for scan path based designs. Howev er, the major advantage of the scheme is the significant reduction of test time overhead due to integration of an embedded test machine in t he design at the synthesis phase.