# 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} \hline \hline  & \multicolumn{2}{c}{**Initial FSM**} & \multicolumn{3}{c}{**Power Direction**} & \multicolumn{3}{c}{**Speed Direction**} & \multicolumn{3}{c}{**Balanced**} \\  & \multicolumn{2}{c}{**Default Encoding**} & \multicolumn{2}{c}{**JEDI Encoding**} & \multicolumn{3}{c}{**One-Hot Encoding**} & \multicolumn{3}{c}{**Binary Encoding**} \\ \hline
**Name** & \(\mathbf{C_{0}}\) & \(\mathbf{F_{0}}\) & \(\mathbf{P_{0}}\) & \(\mathbf{C_{1}}\) & \(\mathbf{F_{1}}\) & \(\mathbf{P_{1}}\) & \(\mathbf{C_{2}}\) & \(\mathbf{F_{2}}\) & \(\mathbf{P_{2}}\) & \(\mathbf{C_{3}}\) & \(\mathbf{F_{3}}\) & \(\mathbf{P_{3}}\) \\ \hline BBSAR & 24 & 416.15 & 132.87 & 23 & 425.89 & 132.88 & 21 & 424.09 & 132.6 & 21 & 418.59 & 132.88 \\ BBSSE & 37 & 332.01 & 135.57 & 40 & 387.9 & 135.59 & 40 & 386.55 & 135.6 & 41 & 386.7 & 135.68 \\ BBSTAS & 9 & 680.27 & 131.98 & 9 & 693 & 131.98 & 10 & 657.03 & 131.98 & 11 & 657.89 & 131.99 \\ BEECOUNT & 31 & 392.62 & 131.71 & 28 & 471.92 & 133.07 & 25 & 472.81 & 134.07 & 22 & 471.48 & 133.93 \\ CSE & 108 & 225.02 & 135.46 & 94 & 191.2 & 135.48 & 97 & 215.56 & 133.18 & 118 & 201.09 & 131.64 \\ DK14 & 39 & 359.32 & 135.13 & 58 & 317.56 & 132.59 & 39 & 359.32 & 135.13 & 39 & 359.32 & 135.13 \\ DK16 & 66 & 420.88 & 132.1 & 66 & 423.73 & 132.11 & 64 & 418.06 & 133.99 & 70 & 360.36 & 132.12 \\ EX1 & 216 & 157.23 & 143.14 & 158 & 187.06 & 143.12 & 176 & 200.56 & 135.16 & 171 & 191.31 & 143.38 \\ EX4 & 27 & 513.61 & 134.12 & 24 & 534.76 & 136.34 & 25 & 460.62 & 136.35 & 28 & 577.37 & 136.36 \\ EX6 & 43 & 308.17 & 137.38 & 49 & 279.64 & 133.47 & 53 & 351.25 & 133.48 & 43 & 308.17 & 137.38 \\ LION9 & 20 & 490.2 & 132.1 & 13 & 500 & 131.06 & 11 & 506.33 & 131.06 & 7 & 526.87 & 131.04 \\ PLANET & 128 & 432.53 & 146.81 & 131 & 423.91 & 147.4 & 125 & 454.34 & 138.19 & 145 & 335.68 & 147.66 \\ S1 & 131 & 197.71 & 138.19 & 142 & 193.84 & 138.22 & 134 & 195.16 & 138.21 & 183 & 190.73 & 138.4 \\ S1488 & 364 & 168.8 & 147.58 & 443 & 152.95 & 148.14 & 346 & 169.87 & 147.61 & 432 & 151.91 & 148.27 \\ S1494 & 328 & 162.84 & 147.61 & 364 & 166.17 & 147.62 & 344 & 174.92 & 147.61 & 408 & 159.41 & 148.15 \\ S27 & 46 & 358.29 & 135.83 & 45 & 347.58 & 131.84 & 46 & 321.23 & 135.82 & 45 & 316.56 & 131.83 \\ S386 & 135 & 173.55 & 136.79 & 127 & 175.25 & 137.76 & 127 & 193.5 & 136.84 & 121 & 176.55 & 136.48 \\ S420 & 71 & 648.09 & 142.7 & 79 & 515.46 & 142.72 & 71 & 641.85 & 140.28 & 77 & 650.62 & 142.71 \\ S510 & 247 & 144.26 & 145.79 & 237 & 146.54 & 146.13 & 212 & 161.08 & 145.72 & 208 & 160.08 & 145.86 \\ S832 & 221 & 164.1 & 140.45 & 218 & 178.57 & 140.7 & 198 & 189.86 & 140.75 & 183 & 199.48 & 140.8 \\ SAND & 37 & 332.01 & 135.57 & 40 & 387.9 & 135.59 & 40 & 386.55 & 135.6 & 41 & 386.7 & 135.68 \\ SSE & 194 & 182.58 & 139.6 & 217 & 169.09 & 139.65 & 206 & 174.28 & 139.59 & 207 & 171.03 & 139.57 \\ TRAIN11 & 19 & 515.2 & 132.07 & 9 & 577.7 & 131.06 & 8 & 577.03 & 131.05 & 7 & 578.03 & 131.05 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: The example results after implementation using Quartus Prime tool for MS strategy. Figure 3: Comparison of average results after implementation using Quartus Prime tool. ## 4 Conclusions

The transformation of finite state machines is an important phase in the FSM synthesis process. Typically, state merging is used for the reduction of the number of memory elements, but state splitting can be useful for the minimization of the power dissipation and the critical path of the combinational part of FSM. In this paper, three different strategies for FSM transformations were presented. In addition, the offered approach allows to reduce not only the number of FSM states and optimize FSM key parameters, but also to minimize the number of FSM transitions and input variables due to the application of additional algorithms. The merge-then-split strategy is the best solution for speed and area optimization, and the speed-then-merge strategy is better for power optimization.