# Reducing LUT Count for FPGA-Based Mealy FSMs
## Main Idea of the Proposed Method  
Consider some Mealy FSM \(S_{i}\) represented by an STT. We assume that the following procedures have been executed: (1) the replacement of inputs; (2) the encoding of COs; (3) the encoding of states and (4) the transformation of initial STT into the DST of FSM \(U_{1}\). To get SBFs representing \(U_{4}\), we should transform the DST of FSM \(U_{1}\) into a DST of Mealy FSM \(U_{4}\).  
To obtain the arguments of functions (8) and \(Z(T,P)\), it is necessary to replace the column \(X_{h}\) of the DST of FSM \(U_{1}\) by the column \(P_{h}\). It is executed in the following way: if an additional variable \(p_{g}\in P\) replaces an input \(x_{l}\in X\) for a state \(a_{m}\in A\), then the variable \(x_{l}\) (or its negation) from the column \(X_{h}\) is replaced by the variable \(p_{g}\) (or its negation) in the column \(P_{h}\) for all transitions from the state \(a_{m}\in A\).  
To obtain functions \(Z(T,P)\), it is necessary to replace the column \(Y_{h}\) of the DST of FSM \(U_{1}\) by the column \(Z_{h}\). The filling of the column \(Z_{h}\) is executed in the following manner. If the \(h\)-th row of DST includes a CO \(Y_{q}\subseteq Y\) such that the \(r\)-th bit of \(K(Y_{q})\) is equal to 1, then the symbol \(z_{r}\) should be written in the \(h\)-th row of the column \(Z_{h}\) of DST of FSM \(U_{4}\).  
Using a DST of FSM \(U_{4}\), we can derive the systems (8) and  
\[Z=Z(T,P). \tag{14}\]  
Using the table of replacement of inputs, we can get the system (7). Next, using the content of collections of outputs, we can obtain the system (12).  
Until 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. There are three levels of logic blocks in the proposed Mealy FSM \(U_{4}\). Its structural diagram is shown in Figure 4.  
In FSM \(U_{4}\), the first level of logic is represented by a block \(LUTerP\), the second level includes blocks \(LUTerZ\) and \(LUTerT\), the third level includes a block \(LUTerY\). The blocks implement the following SBFs: the \(LUTerP\) implements the system (7), the \(LUTerZ\) the system (14), the \(LUTerT\) the system (8), and the \(LUTerY\) the system (12).  
Figure 4: Structural diagram of Mealy FSM \(U_{4}\).  
If the condition  
\[G+R\leq S_{L} \tag{15}\]  
If the condition  
\[R_{Q}\leq S_{L} \tag{16}\]  
takes place, then there are exactly \(N\) LUTs in the circuit of the \(LUTerY\). If this condition is violated, then it is necessary to apply the methods of functional decomposition for some functions from SBF (12).  
In this article, we propose a design method for Mealy FSM \(U_{4}\). We assume that an FSM is represented by an STT. The method includes the following steps:  
1. Executing the replacement of inputs by additional variables \(p_{g}\in P\).
2. Executing the state assignment in a way optimizing the SBF \(P=P(X,T)\).
3. Deriving the collections of outputs \(Y_{q}\subseteq Y\) from the STT.
4. Executing the encoding of COs in a way optimizing the SBF \(Y=Y(Z)\).
5. Creating the DST of FSM \(U_{4}\) on the base of initial STT.
6. Deriving the SBFs (7), (8), (12) and (14) from the DST.
7. Implementing circuit of FSM using particular LUTs.  
Some steps of the proposed method are connected with solution of optimization problems. We discuss these problems in the following Section.