# Reducing LUT Count for FPGA-Based Mealy FSMs
## 3 State of the Art
They have been proposed to minimize the control memory size in microprogram control units (MCU) [63]. Next, they were applied in PLA-based FSMs [64]. Each of these methods was used separately in EMB-based FSM design [44; 45; 48; 60]. However, they have never been used in LUT-based FSM design. In this article, we propose to combine these methods together to optimize characteristics of LUT-based Mealy FSMs. The first method is a replacement of inputs \(x_{l}\in X\) by additional variables \(p_{g}\in P=\{p_{1},\ldots,p_{G}\}\) where \(G\ll L\)[64]. To do it, it is necessary to create an SBF  
\[P=P(T,X). \tag{7}\]  
In MCUs, SBF (7) is implemented using a multiplexer. The additional variables are used as arguments of functions \(f_{i}\in\Phi\cup Y\). These functions are represented as  
\[\Phi=\Phi(T,P); \tag{8}\]  
\[Y=Y(T,P). \tag{9}\]  
The functions (8) and (9) have a regular nature [35]. So, they can be implemented as a memory block having \(G+R\) address inputs and \(N+R\) outputs. Using this approach leads to FSM \(U_{2}\) shown in Figure 2. It includes a multiplexer implementing SBF (7) and a memory block implementing systems (8) and (9). In the classical MCU [63], only a single input is checked in each cycle of operation (\(G=1\)). This results in rather slow control units. To decrease the number of cycles required for implementing  
Figure 2: Structural diagram of FSM \(U_{2}\). a control algorithm, it is necessary to increase the value of \(G\). To optimize an MCU performance, the value of G is determined as [64]:  
\[G=max(|X(a_{1})|,\ldots,|X(a_{M})|). \tag{10}\]  
In (10), the symbol \(X(a_{m})\) stands for the set of inputs determining transitions from the state \(a_{m}\in A\). The model \(U_{2}\) was used in the FPGA-based design. Different \(U_{2}\)-based approaches are discussed, for example, in [60]. In all discussed cases, EMBs implement systems (8) and (9). The system (7) is implemented with LUTs. Collections of outputs (COs) \(Y_{q}\subseteq Y(q\in\{1,\ldots,Q\})\) are generated during interstate transitions. The minimum number of bits in the code \(K(Y_{q})\) is determined as  
Figure 1:0  
To encode COs by codes \(K(Y_{q})\), some additional variables \(z_{r}\in Z=\{z_{1},\ldots,z_{R_{Q}}\}\) are used. If COs are encoded, then the system of outputs is represented as  
Figure 1:1  
In the case of MCU, the system (12) is implemented using two blocks, namely, a decoder and a coder [35]. To generate the additional variables \(z_{r}\in Z\), it is necessary to find an SBF  
Figure 1:2  
In the case of MCU, both systems (13) and (2) are implemented by a memory block. In the case of FPGA-based design, a memory block is represented as a network of EMBs. Using the encoding of COs in FPGA-based design leads to Mealy FSM \(U_{3}\) shown in Figure 1:3  
In FSM \(U_{3}\), the block EMBer implements systems (2) and (13). The block LUTer implements the system (12). So far, these methods have been used separately to improve characteristics of circuits of FPGA-based FSMs. Moreover, some parts of FSM circuits have been implemented using EMBs [45; 47]. In this article, we propose to use these methods together. Moreover, all functions are implemented by LUTs. This approach leads to Mealy FSM logic circuits having three levels of logic. The circuit for each level of logic can be viewed as a hardware subroutine. This approach allows structuring a resulting  
Figure 1:4 Structural diagram of FSM \(U_{3}\). FSM circuit and makes the system of interconnections more regular. We denote the proposed Mealy FSM by the symbol \(U_{4}\).