Finite state machine decomposition for I/O minimization

In this paper, we consider the problem of decomposing a Finite State Machine (FSM) into communicating FSMs to minimize the number of inputs/outputs. We propose an FSM decomposition procedure based on partitioning the set of transitions that describes the behavior of an FSM. An extended FM-based partitioning algorithm is applied for transition partitioning. We also devise a state output encoding technique to further reduce the number of interconnections between the FSMs required for communication. Experimental results for MCNC benchmarks show that our algorithm has favorable results over circuit partitioning algorithms on the netlist level