# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 2 Materials and Methods
### General FSM Synthesis Method
\begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c c c c} \hline \hline \multicolumn{1}{c}{**Initial FSM**} & \multicolumn{6}{c}{**MS Strategy**} & \multicolumn{6}{c}{**SM Strategy**} & \multicolumn{6}{c}{**COMB Strategy**} \\ \hline \multirow{2}{*}{**Name**} & \(\text{\bf C_{0}}\) & \(\text{\bf S_{0}}\) & \(\text{\bf P_{0}}\) & \(\text{\bf C_{1}}\) & \(\text{\bf S_{1}}\) & \(\text{\bf P_{1}}\) & \(\text{\bf\#M_{1}}\) & \(\text{\bf\#S_{1}}\) & \(\text{\bf C_{2}}\) & \(\text{\bf S_{2}}\) & \(\text{\bf P_{2}}\) & \(\text{\For the MS strategy, the average results acquired using the presented method are in all cases better than the results obtained for the initial FSM regarding the parameters corresponding to the optimization direction (e.g., power to power direction) in all styles of encoding used. It can be also noticed that the encoding type, in many cases, has a major influence on the result obtained using a specific optimization variant. When the speed optimization is used, the estimated power consumption significantly increases in many cases. It confirms that these two directions contradict each other. Similar observations can be made for other two strategies, the results of which are shown in Table 3 (SM strategy) and Table 4 (COMB strategy). The proposed strategies were also compared to methods described in our previous works, where only the state merging procedure was considered. The results for the merging strategy (M) are presented in Table 5. Additionally, besides the three described optimization directions (power, speed and balanced), the state minimization direction [39] was examined. As it can be noticed, adding the state splitting procedure to the method in most cases increases the gain ratios for all examined parameters, i.e., power, speed, and area. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Parameter** & **Encoding** & **Power Direction** & **Speed Direction** & **Balanced** \\ \hline \multirow{3}{*}{Power} & Binary & 1.00/1.11/2.49 & 0.83/1.01/1.45 & 1.00/1.12/2.49 \\  & One-hot & 1.00/1.01/1.14 & 0.77/1.00/1.13 & 1.00/1.02/1.14 \\  & JEDI & 1.00/1.14/1.62 & 0.38/0.92/1.35 & 0.69/1.08/1.45 \\  & Sequential & 1.00/1.07/1.47 & 0.68/0.98/1.27 & 0.83/1.04/1.24 \\ \hline \multirow{3}{*}{Critical Path} & Binary & 1.00/1.02/1.50 & 1.00/1.03/2.00 & 1.00/1.05/2.00 \\  & One-hot & 1.00/1.09/2.00 & 1.00/1.08/2.00 & 1.00/1.09/2.00 \\ \cline{1-1}  & JEDI & 1.00/1.00/1.00 & 1.00/1.03/2.00 & 1.00/1.08/2.00 \\ \cline{1-1}  & Sequential & 0.67/0.98/1.00 & 1.00/1.03/2.00 & 1.00/1.08/2.00 \\ \hline \multirow{3}{*}{Area} & Binary & 0.89/1.01/1.25 & 1.00/1.03/1.67 & 0.89/1.03/1.67 \\ \cline{1-1}  & One-hot & 0.96/1.10/2.40 & 0.89/1.05/2.00 & 0.96/1.08/2.00 \\ \cline{1-1}  & JEDI & 0.89/1.00/1.25 & 1.00/1.03/1.67 & 0.89/1.03/1.67 \\ \cline{1-1}  & Sequential & 0.89/0.98/1.25 & 1.00/1.03/1.67 & 0.89/1.02/1.67 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: The gain/loss ratios of results for combined strategy. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Parameter** & **Encoding** & **Power Direction** & **Speed Direction** & **Balanced** \\ \hline \multirow{3}{*}{Power} & Binary & 1.00/1.15/2.30 & 0.82/1.02/2.05 & 1.00/1.16/2.28 \\  & One-hot & 1.00/1.01/1.14 & 0.86/1.00/1.14 & 1.00/1.02/1.14 \\ Min./Avg./Max. & JEDI & 1.00/1.17/1.64 & 0.38/0.96/1.22 & 0.69/1.13/1.45 \\  & Sequential & 1.00/1.07/1.47 & 0.77/0.99/1.13 & 0.99/1.06/1.24 \\ \hline \multirow{3}{*}{Critical Path} & Binary & 1.00/1.02/1.50 & 1.00/1.08/2.00 & 1.00/1.08/2.00 \\  & One-hot & 1.00/1.09/2.00 & 1.00/1.08/2.00 & 1.00/1.09/2.00 \\ Min./Avg./Max. & JEDI & 1.00/1.00/1.00 & 1.00/1.08/2.00 & 1.00/1.05/2.00 \\  & Sequential & 0.67/0.98/1.00 & 1.00/1.08/2.00 & 1.00/1.05/2.00 \\ \hline \multirow{3}{*}{Area} & Binary & 0.89/1.01/1.25 & 1.00/1.05/1.67 & 0.89/1.04/1.67 \\  & One-hot & 0.96/1.10/2.40 & 0.89/1.04/2.00 & 0.96/1.09/2.00 \\ \cline{1-1}  & JEDI & 0.89/0.99/1.25 & 1.00/1.05/1.67 & 0.89/1.00/1.67 \\ \cline{1-1}  & Sequential & 0.89/0.97/1.25 & 1.00/1.05/1.67 & 0.89/1.00/1.67 \\ \hline \hline \end{tabular}
\end{table}