# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 2 Materials and Methods
### General FSM Synthesis Method
The example experimental results for binary encoding and power oriented optimization are presented in Table 1, where _Name_ is a benchmark filename, \(C_{0}\), \(S_{0}\) and \(P_{0}\) are, respectively, the number of used logic elements (cost), maximum critical path described by a number of logic levels (speed), and dissipated power in milliwatts of the initial FSM before synthesis; \(C_{1}\), \(S_{1}\) and \(P_{1}\) are, respectively, the cost, speed and dissipated power after synthesis using the MS strategy; and \(C_{2}\), \(S_{2}\) and \(P_{2}\) are, respectively, the cost, speed and dissipated power after synthesis using the SM strategy. Finally, \(C_{3}\), \(S_{3}\) and \(P_{3}\) are the same parameters obtained using the COMB strategy. A power dissipation was evaluated using the following values: output capacitance \(C\) = 3 pF, frequency \(f\) = 5 MHz, supply voltage \(\text{V}_{CC}=5\) V, input probability \(P(x_{i}=1)=0.5\). Values of \(\#M_{X}\) and \(\#S_{X}\) are the numbers of merges and splits performed during the procedure. Similar tables were made for other variants, but only the statistical parameters are presented in this section. It can be seen in Table 1 that for power-oriented optimization in all investigated cases, we have lesser or equal power consumption for the transformed FSMs than for the initial FSM. It also can be noticed that the number of merges and splits depends on the used strategy. It has the lowest average values for the MS strategy and significantly higher values for the SM and COMB strategies. To examine the efficiency of strategies with the application of different state assignments and optimization directions, the gain/loss ratios were calculated. The gain/loss ratio is a relation of value of the considered parameter for the initial FSM to value of the considered parameter for the transformed FSM. The minimum, average and maximum ratios for MS strategy are presented in Table 2. All values are the geometric mean of all ratios calculated for each benchmark. \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}{**Parameter**} & \multicolumn{2}{c}{**Encoding**} & \multicolumn{2}{c}{**Power Direction**} & \multicolumn{2}{c}{**Speed Direction**} & \multicolumn{2}{c}{**Balanced**} \\ \hline \multirow{3}{*}{Power Min./Avg./Max.} & Binary & 1.00/1.15/2.28 & 0.65/1.02/2.05 & 1.00/1.15/2.28 & One-hot & 1.00/1.01/1.14 & 0.99/1.00/1.07 & 1.00/1.02/1.14 \\  & One-hot & 1.00/1.13/1.58 & 0.38/0.92/1.21 & 0.69/1.08/1.45 & 1.00/1.07/1.47 & 0.90/1.00/1.18 & 0.83/1.04/1.24 \\ \hline \multirow{3}{*}{Critical Path Min./Avg./Max.} & 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.08/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 \\ \cline{1-1}  & \multirow{2}{*}{JEDI Sequential} & 1.00/1.00/1.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 & 1.00/1.08/2.00 \\ \cline{1-1}  & & Binary & 0.89/1.03/1.67 & 1.00/1.05/1.67 & 0.89/1.04/1.67 \\ \cline{1-1}  & One-hot & 0.96/1.10/2.40 & 0.89/1.03/2.00 & 0.89/1.04/2.00 \\ \cline{1-1} Min./Avg./Max. & JEDI & 0.89/1.00/1.25 & 1.00/1.05/1.67 & 0.89/1.03/1.67 \\ \cline{1-1}  & Sequential & 0.89/0.97/1.25 & 1.00/1.05/1.67 & 0.89/1.02/1.67 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: The gain/loss ratios of results for merge-then-speed strategy.