# Reducing LUT Count for FPGA-Based Mealy FSMs
## 5 Example of Synthesis
As follows from Figure 5, the code of \(a_{2}\) is equal to \(010\). Due to it, there is the symbol \(D_{2}\) in the column \(\Phi_{h}\). There is the symbol \(x_{1}\) in the row \(1\) of STT. As follows from Table 2, the input \(x_{1}\) is replaced by the variable \(p_{1}\) for the state \(a_{1}\in A\). Due to it, there is the symbol \(p_{1}\) in the first row of DST (Table 3). There is the collection of outputs \(Y_{2}=\{y_{1},y_{7}\}\) in the first row of Table 1. As follows from Figure 6, there is \(K(Y_{2})=0100\). Due to it, there is the symbol \(z_{2}\) in the row \(1\) of DST (Table 3). All other rows of Table 3 are filled in the same way. Figure 5: State codes of Mealy FSM \(U_{4}(S_{1})\). Figure 5.0 Codes of COs of Mealy FSM \(U_{4}(S_{1})\). Deriving SBFs representing the circuit of \(U_{4}(S_{1})\). During this step, the functions (7), (8), (12) and (14) should be found. It can be done using Tables 2 and 3, as well as codes from Karnaugh maps shown in Figures 5 and 6. We start from the SBF (7). We use the symbol \(A_{m}\) to denote a conjunction of state variables (or their complements) corresponding to the code \(K(a_{m})\). The following system can be derived from Figure 5.1  
\[ \begin{split} p_{1}&=A_{1}x_{1}\lor A_{2}x_{2}\lor A _{5}x_{6};\\ p_{2}&=A_{2}x_{3}\lor A_{3}x_{4}\lor A_{5}x_{3};\\ p_{3}&=A_{3}x_{5}\lor A_{5}x_{7}\lor A_{6}x_{8}. \end{split}  \tag{18}\]  
Using codes from Figure 5, we can get the following minimized functions:  
\[ \begin{split} p_{1}&=\overline{T_{1}}\ \overline{T_{2}}\ \overline{T_{3}}x_{1}\lor\overline{T_{1}}\ \overline{T_{2}}\ \overline{T_{3}}x_{2}\lor T_{2}T_{3}x_{6};\\ p_{2}&=\overline{T_{1}}\ \overline{T_{2}}x_{3}\lor T _{1}T_{2}x_{4};\\ p_{3}&=T_{1}T_{2}x_{5}\lor T_{2}T_{3}x_{7}\lor T _{1}\overline{T_{2}}\ x_{8}.\end{split}  \tag{19}\]  
In the discussed case, the system (19) represents \(LUTerP\). Each equation of (19) includes not more than six literals. Because \(S_{L}=6\), there are only \(G=3\) LUTs in the circuit of \(LUTerP\). Each row of DST of FSM \(U_{4}\) corresponds to the product term  
\[F_{h}=A_{m}B_{h}\quad(h\in\{1,\ldots,H\}). \tag{20}\]  
In (20), the symbol \(B_{h}\) denotes a conjuction of variables \(p_{g}\) (or their compliments) written in the column \(P_{h}\) of DST. The functions (8) and (14) depend on terms (20). For example, the following equations can be derived from Table 3:  
\[ \begin{split} D_{1}&=F_{2}\lor F_{8}\lor F_{11}\lor F _{12}=\overline{T_{1}}\ \overline{T_{2}}\ \overline{T_{3}}\ \overline{p_{1}}\\ \lor T_{1}T_{2}\overline{T_{3}}\ \overline{p_{3}}\ \overline{p_{3}} \overline{\gamma}\ \overline{T_{1}}T_{2}T_{3}p_{2}\ \overline{p_{1}}\lor\overline{T_{1}}T_{2}T_{3}\overline{p_{2}}p_{3}. \end{split}  \tag{21}\]  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \(a_{m}\) & \(K(a_{m})\) & \(a_{s}\) & \(K(a_{s})\) & \(P_{h}\) & \(Z_{h}\) & \(\Phi_{h}\) & \(h\) \\ \hline \multirow{2}{*}{\(a_{1}\)} & \multirow{2}{*}{000} & \(a_{2}\) & 010 & \(p_{1}\) & \(z_{2}\) & \(D_{2}\) & 1 \\  & & \(a_{3}\) & 110 & \(\overline{p_{1}}\) & \(z_{1}z_{4}\) & \(D_{1}D_{2}\) & 2 \\ \hline \multirow{3}{*}{\(a_{2}\)} & \multirow{3}{*}{010} & \(a_{4}\) & 001 & \(p_{1}\) & \(z_{2}z_{3}\) & \(D_{3}\) & 3 \\  & & \(a_{4}\) & 001 & \(\overline{p_{1}}p_{2}\) & \(z_{1}z_{4}\) & \(D_{3}\) & 4 \\  & & \(a_{5}\) & 011 & \(\overline{p_{1}}\overline{p_{2}}\) & \(z_{2}z_{4}\) & \(D_{2}D_{3}\) & 5 \\ \hline \multirow{3}{*}{\(a_{3}\)} & \multirow{3}{*}{110} & \(a_{2}\) & 010 & \(p_{2}\) & \(z_{1}z_{2}z_{3}\) & \(D_{2}\) & 6 \\  & & \(a_{5}\) & 011 & \(\overline{p_{2}}p_{3}\) & \(z_{2}\) & \(D_{2}D_{3}\) & 7 \\  & & \(a_{6}\) & 100 & \(\overline{p_{2}}\overline{p_{3}}\) & \(z_{4}\\[z_{1}=F_{2}\lor F_{4}\lor F_{6}\lor F_{10}\lor F_{12}\lor F_{14}= \tag{22}\] \[=T_{1}T_{2}\ \overline{T_{3}}\ \overline{p_{2}}\ \overline{p_{3}} \vee\ldots\lor T_{1}\ \overline{T_{2}}\ \overline{T_{3}}p_{3}.\]  
All other functions \(D_{r}\in\Phi\) and \(z_{r}\in Z\) are constructed in the same manner. In the discussed case, there is \(R+G=6\).