# Reducing LUT Count for FPGA-Based Mealy FSMs
## 3 State of the Art  
The process of technology mapping is associated with necessity of the solution of some optimization problems [9; 35]. When designing FPGA-based FSMs, four optimization problems arise [35]: (1) the reduction of hardware amount, (2) the improvement of performance, (3) the reduction of power consumption, and (4) the improvement of testability. In this article, we propose a way for solution of the first problem. Denote as \(NL(f_{i})\) the number of literals [3] in sum-of-products (SOPs) of functions (2) and (3). If the condition  
\[NL(f_{i})\leq S_{L}\quad(i\in\{1,\ldots,N+R\}) \tag{4}\]  
takes place, then it is enough a single LUT to implement a circuit for any function \(f_{i}\in\Phi\cup Y\). If the condition (4) is violated for some function \(f_{i}\in\Phi\cup Y\), then the corresponding circuit is multi-level. In multi-level circuits, it is quite possible that the same inputs \(x_{i}\in X\) appear on several logic levels. It results in FSM circuits with the spaghetti-type interconnections. To improve the circuit characteristics, it is necessary to diminish the number of LUTs and make the system of interconnections more regular. It can be done using the following approaches:  
1. The functional decomposition of functions representing Mealy FSM logic circuits [8; 17; 19; 20; 24; 36]. 2. The optimal state assignment [3; 9; 37; 38; 39; 40; 41; 42; 43]. 3. The replacement of LUTs by embedded memory blocks (EMBs) [44; 45; 46; 47; 48; 49; 50; 51]. 4. The structural decomposition of FSM circuits [35; 43; 52]. The functional decomposition is a very powerful tool used in the process of technology mapping [19; 53]. If the condition (4) is violated, then a function is broken down into smaller and smaller components. The process is terminated when any component has no more than \(S_{L}\) arguments. If the condition (4) takes place, then a Mealy FSM logic circuit has exactly \(R+N\) LUTs. Otherwise, an FSM circuit is represented by \(R+N+|\Psi|\) functions, where \(\Psi\) is a set of additional functions different from (2) and (3). New functions correspond to components of initial functions obtained in the process of decomposition. A huge number of methods of functional decomposition are known. Some of them can be found, for example, in [19; 20; 23]. We do not discuss them in our article. All modern FPGA-based CAD  
Figure 1: Structural diagram of LUT-based Mealy FSM \(U_{1}\). systems include program tools for functional decomposition. These tools can be found in academic systems [33; 34; 54; 55], as well as in industrial packages [56; 57; 58]. The open system DEMAIN [54] includes powerful methods of functional decomposition. Due to this, we chose this system for comparison with our proposed approach. The optimal state assignment [9] is a process of obtaining state codes optimizing systems of Boolean functions (2) and (3). One of the best academic optimal state assignment algorithms is JEDI distributed with the system SIS [34]. The JEDI is aimed at reducing the numbers of arguments in functions representing a Mealy FSM logic circuit. In this article, we compare JEDI-based FSMs with FSMs based on our proposed approach  
Different state assignment strategies can be found in modern industrial CAD tools. For example, the design tool Vivado [57] uses the following approaches: the one-hot (\(R=M\)); compact; Gray codes; Johnson codes; speed encoding; automatic state assignment (auto). The same methods can be found in the package XST by Xilinx [56]. Because modern FPGAs include a lot of flip-flops, the one-hot state assignment is very popular in LUT-based design [41]. This approach allows producing less complicated combinational parts of FSM circuits than their counterparts based on the binary state encoding where \(R=\lceil log_{2}M\rceil\)[35]. As shown in [41], if \(M\leq 8\), then FSMs based on binary state codes have better characteristics than their counterparts based on one-hot codes. The one-hot codes are more preferable if there is \(M>16\).