# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 2 Materials and Methods
### General FSM Synthesis Method

Table 3: The gain/loss ratios of results for speed-then-merge strategy. To compare three distinct aspects considered in experiments (strategy, optimization direction and encoding), the average values of all parameters were calculated in dependance on the different point of view. In Figure 1, we can see that the MS strategy is best for speed and area optimization, and the SM strategy for power optimization. We can also see that all strategies produce better results than for the initial FSMs, not only in the cases of speed and power, but also for the area parameter. Figure 1 shows a comparison of the results for different optimization directions. It confirms that the power direction gives better results in the power aspect, and speed direction, in the speed aspect. It can be also noticed that balanced optimization gives satisfactory results in all three aspects (power, speed, and area). In the case of the M strategy (from previous works), the results in terms of speed and area were significantly worse than those obtained from the MS, SM and COMB strategies. Only the average power dissipation was similar to the value obtained using the COMB strategy (Figure 1). The state minimization direction gives the best results for the area parameter and comparable results for power and speed parameters (Figure 1). Figure 2 shows a comparison of the results for different encoding methods. It shows that one-hot encoding style gives the best results in terms of speed, as predicted. The most suitable encoding methods for power optimization are the binary and JEDI methods. The sequential assignment, which was designed especially for power optimization, gives moderate results in terms of power consumption. Using all encoding types, the average results for the transformed FSM are always better than those of the initial FSM. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Parameter** & **Encoding** & **Power Direction** & **Speed Direction** & **Balanced** & **State min.** \\ \hline \multirow{4}{*}{Power} & Binary & 1.00/1.07/2.28 & 1.00/1.05/2.05 & 1.00/1.06/2.28 & 1.00/1.06/2.05 \\  & One-hot & 1.00/1.01/1.14 & 0.99/1.00/1.07 & 1.00/1.01/1.14 & 0.92/1.01/1.14 \\ Min./Avg./Max. & JEDI & 1.00/1.07/1.58 & 0.99/1.05/1.26 & 0.91/1.05/1.26 & 0.99/1.05/1.26 \\  & Sequential & 1.00/1.01/1.13 & 0.90/1.00/1.13 & 0.83/1.00/1.13 & 0.90/1.00/1.13 \\ \hline \multirow{4}{*}{Critical Path} & Binary & 1.00/1.05/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 \\  & One-hot & 1.00/1.09/2.00 & 1.00/1.09/2.00 & 1.00/1.09/2.00 & 1.00/1.09/2.00 \\ Min./Avg./Max. & JEDI & 1.00/1.02/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 \\  & Sequential & 1.00/1.02/1.50 & 1.00/1.08/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 \\ \hline \multirow{4}{*}{Area} & Binary & 1.00/1.04/1.67 & 1.00/1.05/1.67 & 1.00/1.05/1.67 & 1.00/1.05/1.67 \\  & One-hot & 1.00/1.02/40 & 1.00/1.07/2.00 & 1.00/1.10/2.40 & 1.00/1.11/2.40 \\ Min./Avg./Max. & JEDI & 1.00/1.03/1.67 & 1.00/1.05/1.67 & 1.00/1.05/1.67 & 1.00/1.05/1.67 \\ \cline{1-1}  & Sequential & 1.00/1.02/1.25 & 1.00/1.05/1.67 & 1.00/1.05/1.67 & 1.00/1.05/1.67 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: The gain/loss ratios of results for merging only strategy. Figure 1: Comparison of average results: (**a**) for different strategies; (**b**) for different optimization directions. To check the effectiveness of the proposed strategies, the benchmarks converted by the proposed synthesis method were also synthesized and implemented using Intel Quartus Prime and Xilinx (AMD) Vivado tools. Four scenarios were chosen:

* Initial FSM with default encoding (provided by Quartus Prime or Vivado);
* Power direction with JEDI encoding;
* Speed direction with one-hot and binary encoding;
* Balanced variant with binary encoding. All scenarios were performed for all three considered strategies (MS, SM and COMB). All benchmarks were synthesized using the same design flow parameters (balanced mode).