# Reducing LUT Count for FPGA-Based Mealy FSMs
## 7 Conclusions  
Contemporary FPGA devices include a lot of look-up table elements. This allows implementing a very complex digital system using only a single chip. However, LUTs have rather small amount of inputs (for the vast majority of devices the value of \(S_{L}\) does not exceeds 6). This value is considered as optimal [26; 28]. To design rather complex FSMs, the methods of functional decomposition are used. As a rule, this leads to multi-level FSM circuits with complex systems of spaghetti-type interconnections. To optimize the LUT counts in FPGA-based FSM circuits, different methods of structural decomposition could be applied. As our researches [35] show, the structural decomposition can lead to FSM circuits having better characteristics than their counterparts based on the functional decomposition. They have regular system of interconnections and predicted number of logic levels. The current article is devoted to a novel approach aimed at optimization of LUT-based Mealy FSMs. The proposed approach is based on simultaneous use of such methods of structural decomposition as the replacement of inputs and encoding of collections of outputs. Till now, the methods of replacement of inputs and encoding of the collections of outputs were used separately in EMB-based Mealy FSM design. In this article, we propose to use them together in LUT-based Mealy FSMs. Furthermore, we encode the collections in a way minimizing the number of interconnections between other blocks and the block generating FSM outputs. The proposed approach leads to three-level Mealy FSM circuits with regular systems of interconnections. We compared the proposed approach with FSM circuits obtained using the Xilinx CAD tool Vivado 2019.1. These circuits were obtained using four different approaches: Auto by Vivado, One-hot by Vivado, JEDI and DEMAIN. The experiments clearly show that the proposed approach leads to reducing the number of LUTs in comparison with FSM circuits produced by other investigated methods. The results of experiments show that the proposed approach leads to reducing the LUT counts from 12% to 59% in average compared with known methods of synthesis of single-level FSMs. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Benchmark** & \(\mathbf{U_{5}}\) & \(\mathbf{U_{6}}\) & \(\mathbf{U_{7}}\) & \(\mathbf{U_{8}}\) & **Our Approach** & **Category** \\ \hline ex1 & 51 & 49 & 52 & 46 & 40 & 2 \\ kirkman & 38 & 37 & 40 & 37 & 33 & 2 \\ planet & 86 & 80 & 88 & 82 & 78 & 2 \\ planet1 & 86 & 80 & 88 & 82 & 78 & 2 \\ pma & 84 & 88 & 90 & 76 & 72 & 2 \\ s1 & 60 & 58 & 62 & 58 & 54 & 2 \\ s1488 & 98 & 90 & 87 & 94 & 89 & 2 \\ s1494 & 101 & 99 & 104 & 96 & 90 & 2 \\ s1a & 42 & 44 & 46 & 42 & 38 & 2 \\ s208 & 11 & 12 & 11 & 11 & 9 & 2 \\ styr & 79 & 76 & 80 & 72 & 70 & 2 \\ tma & 40 & 37 & 42 & 38 & 30 & 2 \\ sand & 119 & 109 & 124 & 108 & 99 & 3 \\ s420 & 10 & 11 & 11 & 10 & 8 & 4 \\ s510 & 35 & 30 & 37 & 28 & 22 & 4 \\ s820 & 67 & 64 & 70 & 61 & 52 & 4 \\ s832 & 61 & 57 & 64 & 54 & 50 & 4 \\ \hline Total & 1086 & 1021 & 1096 & 995 & 912 & \\ \hline Percentage,\% & 117.11 & 111.95 & 120.18 & 109.10 & 100 & \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Comparison of our approach with two-level FSMs. Furthermore, our approach provides better LUT counts as compared to methods of synthesis of two-level FSMs (from 9% to 20%). However, our approach leads to slower FSM circuits as compared to other investigated methods. Thus, our approach reduces the overall performance of a digital system including \(U_{4}\)-based FSMs. So, the proposed method can be used if the LUT count is the dominant characteristic of a digital system. There are two directions in our future research. The first is connected with development of design methods targeting FPGA chips of Intel (Altera). The second direction targets at EMB-based Mealy FSMs. Conceptualization, A.B., L.T. and K.K. ; methodology, A.B., L.T. and K.K. ; software, A.B., L.T. and K.K. ; validation, A.B., L.T. and K.K. ; formal analysis, A.B., L.T. and K.K. ; investigation, A.B., L.T.