# Reducing LUT Count for FPGA-Based Mealy FSMs
## 3 State of the Art
However, the characteristics of LUT-based FSM circuits significantly depend on the number of inputs [35]. As it is shown in [42], if \(L\leq 10\), then it is better to use one-hot state codes. Otherwise, binary state encoding allows producing better FSM circuits. So, both approaches should be compared with our proposed method. We chose the method Auto of Vivado as a method of binary state encoding. This method allows choosing codes producing FSM circuits with the best possible characteristics. The main goal of both [PERSON] and [PERSON] state encoding approaches is the reducing switching activity of an FSM circuit. It allows reducing the dynamic power consumption [35]. We do not discuss these methods in detail. Such an analysis can be found, for example, in [42]. So, a large number of state assignment methods are currently known. They are usually focused on optimizing one or more characteristics of FSM circuits. Some of them mostly focus on area reduction. It is very difficult to say which method is the best for a particular FSM. It depends on both the features of FSM and FPGA, as well as on the accepted criteria of FSM circuit optimality. Each literal of SOP representing a function \(f_{i}\) corresponds to a wire in the FSM circuit. So, to diminish the number of interconnections, it is necessary to diminish the numbers of literals in Boolean functions (2) and (3). The fewer interconnections, the less power is consumed [28]. Therefore, the optimal state assignment must be performed regardless of whether the condition (4) is met or not. Modern FPGAs include a lot of configurable embedded memory blocks [10; 11; 12]. Replacement of LUTs by EMB allows significantly improve the characteristics of resulting FSM circuits [41]. Because of it, there are a lot of design methods for EMB-based FSMs [43; 44; 46; 47; 48; 49; 59]. The survey of different methods of EMB-based design can be found in [60]. Unfortunately, these methods can be used only if there are \"free\" EMBs, which are not used to implement other parts of a digital system. To optimize a LUT-based FSM circuit, it is necessary to eliminate a direct dependence of functions \(y_{n}\in Y\) and \(D_{r}\in\Phi\) on inputs \(x_{l}\in X\). It is a main goal of different methods of a structural decomposition [35]. To eliminate this dependence, new functions \(f_{i}\in\Psi\) are introduced to eliminate this dependence. These new functions depend on inputs and/or state variables. To optimize an FSM circuit, the following condition should take place:  
\[|\Psi|\ll N+R. \tag{5}\]  
Each system of new functions determines a separate block LUTer with its unique input and output variables. These blocks can be viewed as \"hardware subroutines\" by analogy with subroutines in programming [61; 62]. If the relation (5) takes place, then the total number of LUTs implementing functions \(f_{i}\in\Psi\) is significantly less than their total number in blocks \(\mathit{LUTer\Phi}\) and \(\mathit{LUTerY}\) of an equivalent FSM \(U_{1}\). Using hardware subroutines allows structuring an FSM circuit. The functions \(f_{i}\in\Psi\) are used as arguments of functions (2) and (3). If the condition  
\[|\Psi|\ll L+R \tag{6}\]  
is true, then the total number of LUTs in an FSM circuit is significantly less than it is for an equivalent FSM \(U_{1}\). If (6) takes place, then the structural decomposition leads to reduced number of literals in SOPs of functions \(f_{i}\in\Phi\cup Y\) as compared to initial functions (2) and (3). In turn, it reduces the total number of LUTs in blocks \(LUTer\Phi\) and \(LUTerY\) (as compared to \(U_{1}\)). If condition (4) is violated for some functions \(f_{i}\in\Phi\cup Y\cup\Psi\), then the methods of functional and structural decomposition should be used together in the process of technology mapping. A survey of different methods of structural decomposition can be found in [35]. In this article, we discuss two methods of structural decomposition. They are the methods of replacement of inputs and encoding of outputs.