Synthesis of Moore FSMs with Two Blocks of Outputs

A new method of structural decomposition of FPGA-based Moore finite state machines (FSMs) is proposed, together with the resulting architecture of the FSM circuit. The main aim of the proposed method is to improve the spatial characteristics of FPGA-based Moore FSM circuits based on twofold state assignment (TSA). The main idea of this method is to divide the set of FSM outputs into two disjoint sets. Each set determines a block of the FSM circuit. For one block, the generated outputs depend on maximum binary state codes (MBCs). For the other block, the generated outputs are functions of partial state variables. These variables are necessary for creating partial state codes that determine partial input memory functions. Under certain conditions, the proposed method improves the spatial characteristics of FSM circuits. As in the case of TSA, each FSM state has two codes. The first is a maximum binary code with the minimum possible number of bits, while the second is a partial state code representing a state as an element of a class of compatible states. The method can be applied to improve the spatial characteristics of Moore FSMs based on look-up table (LUT) elements. To improve the characteristics of the resulting FSM circuits, classes of compatible states are used; this allows us to reduce the number of literals in sum-of-products representations of partial input memory functions. An example of synthesis is presented. The experiments are conducted using a known library of benchmark FSMs. For the fourteen FS-FSM benchmarks requiring decomposition, the proposed method reduces the LUT count by 7.57% compared with equivalent TSA-based Moore FSM circuits, while the propagation time increases by 5.06%.