An architecture for synthesis of testable finite state machines

The authors present a hardware architecture for synthesizing finite state machines (FSM). This architecture is defined at the level of the state transition graph. It contains a test machine with the same number of state variables as the object machine to be synthesized. The state graph of the test machine is so defined that each state is uniquely set and observed by an input sequence no longer than [log_k n], where n is the number of states and the integer k is a design parameter. The state transition graph of the test machine is superposed on the given state graph of the object function. The logic implementation steps, namely, state assignment, minimization and technology mapping are carried out for the combined graph. By design, the embedded test machine is fully testable. Also, since the test machine can control all memory elements, the circuit is effectively tested by a combinational circuit test generator. Scan register is shown to be a special case of the presented methodology