# Reducing LUT Count for FPGA-Based Mealy FSMs
## 5 Example of Synthesis  
If a Mealy FSM \(S_{j}\) is synthesized using a model \(U_{i}\), then we denote it by the symbol \(U_{i}(S_{j})\). Consider an example of synthesis for Mealy FSM \(U_{4}(S_{1})\). An FSM circuit will be implemented using LUTs with \(S_{L}=6\). Executing the replacement of inputs. We start from constructing sets \(X(a_{m})\subseteq X\). A set \(X(a_{m})\) includes inputs \(x_{l}\in X\) determining transitions from the state \(a_{m}\in A\). Using Table 1 gives the following sets: \(X(a_{1})=\{x_{1}\}\), \(X(a_{2})=\{x_{2},x_{3}\}\), \(X(a_{3})=\{x_{4},x_{5}\}\), \(X(a_{4})=\emptyset\), \(X(a_{5})=\{x_{3},x_{6},x_{7}\}\) and \(X(a_{6})=\{x_{8}\}\). Using (10) gives \(G=max(1,2,2,0,3,1)=3\). So, there is the set \(P=\{p_{1},p_{2},p_{3}\}\). Using (1) gives the number of state variables \(R=3\). We should construct a table of replacement of inputs [35]. This table has \(M\) columns marked by states \(a_{m}\in A\) and \(G\) rows marked by variables \(p_{g}\in P\). If an input \(x_{l}\in X\) is replaced by a variable \(p_{g}\in P\) in the state \(a_{m}\in A\), then there is the symbol \(x_{l}\) written at the intersection of the column \(a_{m}\) and the row \(p_{g}\)[64]. Inputs \(x_{l}\in X\) written in a row \(p_{g}\) form a set \(X(p_{g})\subseteq X\). If \(|X(p_{g})|\leq S_{L}-R\), then the circuit generating \(p_{g}\in P\) is implemented as a single LUT. In the discussed case, there is \(S_{L}-R=3\). To optimize the circuit of \(LUTerP\), we should distribute inputs \(x_{l}\in X\) in a way providing the relation \(|X(p_{g})|\leq 3\) (\(g\in\{1,\ldots,G\}\)). It could be done using the approach from [64]. One of the possible solutions is shown in Table 2. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \(p_{g}\)\(p_{g}\)\(p_{1}\) & \(x_{1}\) & \(x_{2}\) & \(-\) & \(-\) & \(x_{6}\) & \(-\) \\ \hline \(p_{2}\) & \(-\) & \(x_{3}\) & \(x_{4}\) & \(-\) & \(x_{3}\) & \(-\) \\ \hline \(p_{3}\) & \(-\) & \(-\) & \(x_{5}\) & \(-\) & \(x_{7}\) & \(x_{8}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Replacement of inputs. Executing the state assignment. To optimize the circuit of \(LUTerP\), it is necessary to diminish the number of literals in functions (7) [64]. It can be done due to a proper state assignment. These methods are based on results of the work [64]. Using (1) gives \(R=3\). So, there are the sets \(T=\{T_{1},T_{2},T_{3}\}\) and \(\Phi=\{D_{1},D_{2},D_{3}\}\). One of the possible outcomes of the state assignment is shown in Figure 5.  
Deriving the collections of outputs. This step is executed in the trivial way. The collections \(Y_{q}\subseteq Y\) are written in the column \(Y_{h}\) of an STT. Using Table 1, the following COs can be found: \(Y_{1}=\emptyset\), \(Y_{2}=\{y_{1},y_{7}\}\), \(Y_{3}=\{y_{2},y_{6}\}\), \(Y_{4}=\{y_{5}\}\), \(Y_{5}=\{y_{1},y_{4},y_{6}\}\), \(Y_{6}=\{y_{2},y_{3}\}\), \(Y_{7}=\{y_{4},y_{6}\}\), \(Y_{8}=\{y_{5},y_{7}\}\), \(Y_{9}=\{y_{2}\}\) and \(Y_{10}=\{y_{3},y_{4}\}\). To optimize the circuit of LUTerY, it is necessary to minimize the number of literals in functions (12). Furthermore, it allows minimizing the number of interconnections between the blocks \(LUTerZ\) and \(LUTerY\). Executing the encoding of COs. We start this process from a system representing outputs \(y_{n}\in Y\). as functions of collections \(Y_{q}\subseteq Y\). It is the following system in the discussed case:  
\[y_{1}=Y_{2}\lor Y_{5}; y_{2}=Y_{3}\lor Y_{6}\lor Y_{9};\] \[y_{3}=Y_{6}\lor Y_{10}; y_{4}=Y_{5}\lor Y_{7}\lor Y_{10};\] \[y_{5}=Y_{4}\lor Y_{8}; y_{6}=Y_{3}\lor Y_{5}\lor Y_{7}; \tag{17}\] \[y_{7}=Y_{2}\lor Y_{8}.\]  
There are \(Q=10\) collections of outputs in the discussed case. Using (11) gives \(R_{Q}=4\) and \(Z=\{z_{1},\ldots,z_{4}\}\). Using the method [64] allows obtaining codes of COs shown in Figure 6.  
Creating the DST of FSM \(U_{4}(S_{1})\). Having codes of states and COs, we can transform the initial STT (Table 1) into a DST of Mealy FSM \(U_{4}(S_{1})\) (Table 3). Consider the row \(h=1\) of Table 3. There is \(a_{m}=a_{1}\) and \(a_{s}=a_{2}\).