An automatic finite state machine synthesis using temporal logic decomposition

Since conventional methods to synthesize a finite state machine (FSM) assign binary codes to all the nonredundant states, they do not exploit delay latches which are sometimes effective in simplifying machine structure. The authors propose a novel method to synthesize an FSM by applying a time shift operation on both inputs and outputs of the FSM. Therefore, the FSM is decomposed into a smaller-scale FSM and two combinational logic circuits including the delay latches. One of the combinational logic circuits is attached to the input part of the FSM and the other is attached to its output part. The algorithm is evaluated for several benchmark examples of FSMs, from which it is concluded that the FSM can be synthesized with 5% less hardware by applying the proposed algorithm.<>