Structural Decomposition in FSM Design: Roots, Evolution, Current State—A Review

Using Codes of Output Collections for Hardware Reduction in Circuits of LUT-Based Finite State Machines

A method is proposed which aims to reduce the hardware in FPGA-based circuits of Mealy finite state machines (FSMs). The proposed method is a type of structural decomposition method. Its main goal is the reducing the number of look-up table (LUT) elements in FSM circuits compared to the three-block FSM circuit. The main idea of the proposed method is the using codes of collections of FSM outputs for replacing the FSM inputs and state variables. The interstate transitions are defined using collections of outputs generated in two adjacent cycles of synchronization. One, of output collection codes, is kept into a register. To optimize block-generating FSM outputs, a new type of state codes is proposed. A state is encoded as an element of some class of states. This approach allows both the number of logic levels and inter-level interconnections in LUT-based FSM circuit to be diminished. An example of an LUT-based Mealy FSM circuit with the proposed method applied is shown. Moreover, the results of our research are represented. The research was conducted using the CAD tool Vivado by Xilinx. The experiments prove that the proposed approach allows the reduction of hardware compared with such known methods as Auto and One-hot of Vivado, and JEDI. Moreover, the proposed approach gives better results than a method based on the simultaneous replacement of inputs and encoding collections of outputs. Compared to circuits of the three-block FSMs, the LUT counts are reduced by an average of 10.07% without significant reduction in the value of operating frequency. The gain in LUT counts increases with the increasing the numbers of FSM states and inputs.

Improving Characteristics of LUT-Based Sequential Blocks for Cyber-Physical Systems

A method is proposed for optimizing circuits of sequential devices which are used in cyber-physical systems (CPSs) implemented using field programmable gate arrays (FPGAs). The optimizing hardware is a very important problem connected with implementing digital parts of CPSs. In this article, we discuss a case when Mealy finite state machines (FSMs) represent behaviour of sequential devices. The proposed method is aimed at optimization of FSM circuits implemented with look-up table (LUT) elements of FPGA chip. The method aims to reduce the LUT count of Mealy FSMs with extended state codes. The method is based on finding a partition of the set of internal states by classes of compatible states. To reduce LUT count, we propose a special kind of state codes named composite state codes. The composite codes include two parts. The first part includes the binary codes of states as elements of some partition class. The second part consists of the code of corresponding partition class. Using composite state codes allows us to obtain FPGA-based FSM circuits with exactly two levels of logic. If some conditions hold, then any FSM function from the first level is implemented by a single LUT. The second level is represented as a network of multiplexers. Each multiplexer generates either an FSM output or input memory function. An example of synthesis is shown. The experiments prove that the proposed approach allows us to reduce hardware compared with two methods from Vivado, JEDI-based FSMs, and extended state assignment. Depending on the complexity of an FSM, the LUT count is reduced on average from 15.46 to 68.59 percent. The advantages of the proposed approach grow with the growth of FSM complexness. An additional positive effect of the proposed method is a decrease in the latency time.

Improving Characteristics of LUT-Based Three-Block Mealy FSMs’ Circuits

One of the very important problems connected with FPGA-based design is reducing the hardware amount in implemented circuits. In this paper, we discuss the implementation of Mealy finite state machines (FSMs) by circuits consisting of look-up tables (LUT). A method is proposed to reduce the LUT count of three-block circuits of Mealy FSMs. The method is based on finding a partition of set of internal states by classes of compatible states. To reduce the LUT count, we propose a special kind of state code, named complex state codes. The complex codes include two parts. The first part includes the binary codes of a state as the element of some partition class. The second part consists of the code of corresponding partition class. Using complex state codes allows obtaining FPGA-based FSM circuits with exactly four logic blocks. If some conditions hold, then any FSM function from the first and second blocks is implemented by a single LUT. The third level is represented as a network of multiplexers. These multiplexers generate either additional variable encoding collections of outputs or input memory functions. The fourth level generates FSM outputs. An example of synthesis and experimental results is shown and discussed. The experiments prove that the proposed approach allows reducing hardware compared to such methods as auto and one-hot of Vivado, JEDI. Further, the proposed approach produces circuits with fewer LUTs than for three-level Mealy FSMs based on joint use of several methods of structural decomposition. The experiments show that our approach allows reducing the LUT counts on average from 11 to 77 percent. As the complexity of an FSM increases, the gain from the application of the proposed method grows; the same is true for both the FSM performance and power consumption.