# Improving Hardware in LUT-Based Mealy FSMs
## 5 Example of Synthesis  
We use the symbol \(U_{i}(S_{a})\) to show that the model \(U_{i}(i\in\{1,2,3\})\) of Mealy FSM is used to implement the circuit of an FSM \(S_{a}\). Let us consider an example of the synthesis of Mealy FSM \(U_{3}(S_{1})\) shown in Figure 7. We use 4-LUTs to implement the circuit. Using an STG, we can find the sets of states, inputs and outputs, as well as the number of interstate transitions. Using Figure 7, we can find the sets \(A=\{a_{1},\ldots,a_{5}\}\)  
Figure 7: STG of Mealy FSM \(S_{1}\). \(X=\{x_{1},x_{2},x_{3}\}\) and \(Y=\{y_{1},\ldots,y_{6}\}\). This gives the following values: \(M=3\), \(L=3\), and \(N=6\). The analysis of Figure 7 shows that there are \(H=9\) transitions between the states of FSM \(S_{1}\). Naturally, the state \(a_{1}\in A\) is the initial state. _Step 1_. The transformation of an STG into an equivalent STT is executed in the trivial way [16]. As follows from Figure 2, each arc of the STG is transformed in a row of the corresponding STT. In our case, Table 2 is an STT of Mealy FSM \(S_{1}\) corresponding to the STG shown in Figure 7.  
In the column \(Y_{h}\) of Table 2, we show the collections of outputs \(Y_{q}\subseteq Y\). As a rule, such information is not given in the classical STT [5]. _Step 2_. For FSM \(S_{1}\), there is \(M=5\). Using (1) gives \(R=3\). This determines the set of state variables \(T=\{T_{1},T_{2},T_{3}\}\). It is possible to encode the states in a way optimizing the system (7). For example, this can be done using the algorithm JEDI [44]. In our simple example, we use the trivial way of state assignment [5] with the following state codes: \(K(a_{1})=000\), \(K(a_{2})=001,\ldots,K(a_{5})=100\). _Step 3_. Using Table 2, we can find the following collections of outputs: \(Y_{0}=\emptyset\), \(Y_{1}=\overline{\{y_{1},y_{2}\}}\), \(Y_{2}=\{y_{3}\}\), \(Y_{3}=\{y_{2},y_{4}\}\), \(Y_{4}=\{y_{3},y_{5}\}\), and \(Y_{5}=\{y_{1},y_{3},y_{6}\}\). So, in our example, there is \(Q=6\). As shown in [13], it is necessary to encode the collections in a way that minimizes the number of literals in functions from (8). If the condition  
\[R_{Q}>I \tag{14}\]  
holds, then such an approach could minimize the LUT count for the block \(LY\)[13; 15; 37]. To encode the COs, we use the approach proposed in [55]. The outcome of encoding is shown in Figure 8. \begin{table}
\begin{tabular}{c c c c c c} \hline \(a_{m}\) & \(a_{T}\) & \(X_{h}\) & \(Y_{h}\) & \(h\) \\ \hline \(a_{1}\) & \(a_{2}\) & \(x_{1}\) & \(y_{1}y_{2}\) & \(Y_{1}\) & 1 \\  & \(a_{3}\) & \(\overline{x_{1}}\) & \(y_{3}\) & \(Y_{2}\) & 2 \\ \hline \(a_{2}\) & \(a_{3}\) & \(x_{1}\) & \(y_{2}y_{4}\) & \(Y_{3}\) & 3 \\  & \(a_{4}\) & \(\overline{x_{1}}x_{2}\) & \(y_{3}\) & \(Y_{2}\) & 4 \\  & \(a_{5}\) & \(\overline{x_{1}}\overline{x_{2}}\) & \(y_{3}y_{5}\) & \(Y_{4}\) & 5 \\ \hline \(a_{3}\) & \(a_{4}\) & \(1\) & \(y_{1}y_{3}y_{6}\) & \(Y_{5}\) & 6 \\ \hline \(a_{4}\) & \(a_{5}\) & \(x_{3}\) & \(y_{3}y_{5}\) & \(Y_{4}\) & 7 \\  & \(a_{1}\) & \(\overline{x_{3}}\) & – & \(Y_{0}\) & 8 \\ \hline \(a_{5}\) & \(a_{1}\) & \(1\) & – & \(Y_{0}\) & 9 \\ \hline \end{tabular}
\end{table} 
Table 2: State transition table of Mealy FSM \(S_{1}\). Figure 8: The outcome of encoding of COs for FSM \(S_{1}\). _Step 4._ Using the distribution of FSM outputs by COs and codes (Figure 8), we obtain the following SBF:  
\[ \begin{array}{l}y_{1}=Y_{1}\lor Y_{5}=z_{1}\overline{z_{2}};\\ y_{2}=Y_{1}\lor Y_{3}=z_{1}\overline{z_{3}};\\ y_{3}=Y_{2}\lor Y_{4}\lor Y_{5}=z_{3};\\ y_{4}=Y_{3}=z_{1}z_{2};\\ y_{5}=Y_{4}=z_{2}z_{3};\\ y_{6}=Y_{5}=z_{1}z_{3};\end{array}  \tag{15}\]  
The analysis of (15) shows that there are 11 literals in this system. So, there are 11 interconnections between the blocks \(LZ\) and \(LY\). As shown in [13], in the common case, there are \(NR_{Q}=21\) interconnections between these blocks. Therefore, using the approach [55] allows reducing the number of interconnections by 1.91 times. _Step 5._ The columns of a DST are shown in Figure 2c. We have modified the traditional DST.