# Improving Hardware in LUT-Based Mealy FSMs
## 3 Related Work  
This section provides a brief analysis of basic methods used for reducing the number of LUTs in FSM circuits. We show that this problem can be solved using either a certain state assignment or various methods of functional and structural decomposition. We show the disadvantages inherent in the methods from these three groups. The method proposed in this paper belongs to the group of structural decomposition methods. Under certain conditions, there is only one level of LUTs in the circuit of \(U_{1}\). To implement a single-level circuit, each function \(\phi_{k}\in\Phi\cup Y\) should depend on no more than \(I\) arguments. However, there are up to six address inputs in the present-day LUTs [19; 33; 34]. To balance the area-spatial-power characteristics of a LUT, it is necessary that the number of inputs does not exceed six [35]. Nevertheless, the total number of inputs and state variables of an FSM can significantly exceed the value of \(I\). This leads to an imbalance between a very large number of FSM inputs, outputs and states, on the one hand, and a very small number of LUT inputs, on the other hand. To reduce the negative impact of this imbalance, it is necessary to improve the design methods of FPGA-based FSMs. The required chip area can be reduced due to the optimizing of the system of interconnections for a particular circuit. Improving interconnections can reduce the power consumption because more than 70% of the power consumption is due to the interconnections [36]. Additionally, the interconnections are responsible for the value of maximum operating frequency of a resulting FSM circuit. As it is shown in [36], the complexity of the interconnection system is beginning to have an increasing negative impact on the propagation time of signals in the FSM circuits. As follows from [15], the regularization of interconnections results in reducing both the time and power consumption. To regularize the interconnection system, it is necessary to use the structural decomposition methods [13; 37]. If the condition  
\[NA(\phi_{k})\leq I \tag{4}\]  
holds for each function \(\phi_{k}\in\Phi\cup Y\), then there are \(L+R\)\(I\)-LUTs in a single-level circuit of the corresponding FSM \(U_{1}\). However, if the condition (4) does not hold for some functions \(\phi_{k}\in\Phi\cup Y\), then it becomes impossible to represent such an FSM with a single level of LUTs. To improve the characteristics of multi-level circuits, various methods can be applied. A significant number of optimization methods aimed at FPGA-based FSMs can be found in the literature [13; 17; 18; 21; 32; 38; 39; 40; 41]. As a rule, these methods can improve the value of one of the characteristics of the FSM circuit [39; 40]. Additionally, there are methods which simultaneously reduce the values of two characteristics (area and power consumption, or area and performance). In our current paper, a method is proposed which aims at reducing the LUT count of three-block circuits of Mealy FSMs [15]. Figure 3: Structural diagram of LUT-based FSM \(U_{1}\). The values of \(NA(\phi_{k})\) can be reduced with the help of a proper state assignment [41; 42; 43]. The number of FSM state memory elements is in the range from \(R=\lceil log_{2}M\rceil\) to \(R=M\). The upper limit of this amount (\(R=M\)) corresponds to a one-hot state assignment. Both of these extreme approaches can be found in many CAD tools, such as SIS [44], ABC [32; 45] or Sinthagate [46]. The manufacturers of FPGA chips also have their tools for implementing the technology mapping of LUT-based circuits. Examples of such systems are Vivado [47], Vitis [48], and Quartus [49]. The first two CAD systems were developed by AMD Xilinx, and the third one is a product of Intel (Altera). It is impossible to specify the approach that is optimal for any FSM. For example, in [50], there is given the comparison of the synthesis results for FSM circuits based on state codes with \(R=\lceil log_{2}M\rceil\) and one-hot state codes.