# Improving Hardware in LUT-Based Mealy FSMs
## 3 Related Work
Note that both of these approaches are widely used in most modern CAD tools. As follows from the comparison, the one-hot codes are the best choice for FSMs with more than 16 states. However, in addition to the value of R, the number of input variables also has a very strong influence on the characteristics of LUT-based FSM circuits. For example, the experiments [51] definitely show the following: if the number of FSM inputs exceeds 10, then it is better to use the codes with a minimum number of bits. As follows from this analysis, it is necessary to check which method leads to the best results for a specific combination of characteristics of a particular FSM. In this paper, we compared the results produced by our new approach with the characteristics of FSM circuits produced using the algorithm JEDI [44], and the methods auto (\(R=\lceil log_{2}M\rceil\)) and one-hot (\(R=M\)) of Vivado [47] by Xilinx [19]. Our choice of JEDI is due to the fact that it is considered one of the best deterministic methods of the state encoding [44]. If condition (4) is violated, then various methods of functional decomposition should be applied to implement an FSM circuit [29; 39]. All these methods are based on splitting the original SOP into sub-SOPs for which the number of arguments does not exceed the number of LUT inputs. Each sub-SOP corresponds to a partial function which differs from the initial function \(\phi_{k}\in\Phi\cup Y\)[39]. This splitting should be executed in a way that increases the number of logic levels of the final FSM circuit as little as possible [29]. Practically, the methods of FD are included in each academic and industrial CAD tool dealing with the LUT-based design. The main disadvantage of FD-based methods: they produce the FSM circuits with spaghetti-type interconnections [13]. It is known that such circuits lose in all three main characteristics to their counterparts with a regular interconnection system [52]. The methods of structural decomposition [13] are an alternative to the methods of FD. The main idea of these methods is the elimination of the direct connection between FSM inputs and state variables, on the one hand, and FSM outputs and IMFs, on the other hand. In the case of SD, an FSM circuit is represented as a composition of unique logic blocks. This leads to an increase in the number of implemented functions, but these partial functions are much simpler than functions (2) and (3). The analysis of these methods can be found, for example, in [13]. The first known methods of SD are the replacement of inputs (RI) and the encoding of the collections of outputs (ECO). They were proposed in the mid-twentieth century by [PERSON] for the optimization of microprogram control units [53]. In [15], we proposed the joint use of these methods for the optimization of LUT-based Mealy FSMs' circuits. Let us briefly describe these two methods. In the case of \(RI\), the set \(X=\{x_{1},\ldots,x_{L}\}\) is replaced by a set of additional variables \(B=\{b_{1},\ldots,b_{J}\}\), where \(J\ll L\). The replaced inputs are represented by an SBF  
\[B=B(T,X). \tag{5}\]  
Each function of (5) represents a multiplexor. Its control inputs are connected with the state variables, and the data inputs are connected with the replaced inputs. In the case of CLB-based solutions, these multiplexors are implemented using LUTs and dedicated multiplexors [54]. There are Q different COs. Each collection \(Y_{q}\subseteq Y\) includes FSM outputs generated during a particular interstate transition. As a rule, the condition \(Q<H\) holds, where \(H\) is a number of interstate transitions. The COs are encoded by binary codes \(K(Y_{q})\). The bits of \(K(Y_{q})\) are represented by elements of an additional set \(Z=\{z_{1},\ldots,z_{\text{R}Q}\}\). The cardinality number of the set \(Z\) is determined as  
\[R=\lceil log_{2}Q\rceil. \tag{6}\]  
To encode COs, two additional SBFs should be constructed:  
\[Z=Z(T,X); \tag{7}\]  
\[Y=Y(Z). \tag{8}\]  
The SBFs (7) and (8) are implemented using LUTs.