# State Merging and Splitting Strategies for Finite State Machines Implemented in FPGA
## 2 Materials and Methods
### General FSM Synthesis Method
It can be noticed that all strategies produce better results than initial FSMs, not only in terms of speed and power, but also taking into consideration the cost of implementation. The most important objective of this approach is not to find the FSM representation with a minimal number of states, but to find such a form of the FSM that has the optimal value of the considered parameter, e.g., speed, power consumption or transformation quality ratio (weights sum of the speed and power parameters). One of the most significant conclusions from the research is that the finite state machine with a minimum number of states is not, in many cases, the finest result in regard to the power consumption and speed. The implemented method can be successfully used with commercial EDA tools, such as Intel Quartus Prime and Xilinx (AMD) Vivado. These tools have their own implementation optimization techniques, but they do not perform the equivalent transformations of FSMs; they only can change the style of the state assignment or minimize the logic functions (output and transition functions) at the stage of logic synthesis. Most of the optimization work in EDA industrial software is performed at post-synthesis stages, such as fitting and routing, so it will be also used for state machines transformed with the proposed method. In the proposed approach, only the merging of a couple of states is considered, and states are split into only two states. The algorithm can be reworked to merge a larger group of states and to split a state to two or more states. Moreover, the additional perfection of the offered method can be achieved by taking into account incompletely specified values for the transition functions as supplementary conditions for the merging or splitting possibility of the FSM internal states. The application of the automatic selection of strategy and weights for balanced variant is also considered in such a way as to find the FSM that is optimal in terms of all criteria taken into account. For that purpose, the using of some artificial intelligence methods, e.g., neural networks, could be useful. Figure 4: Comparison of average results after implementation using Vivado tool. **Author Contributions:** Conceptualization, A.K. and V.S. ; methodology, A.K. ; software, A.K. ; validation, A.K. and V.S. ; formal analysis, V.S. ; investigation, A.K. ; writing--original draft preparation, A.K. ; supervision, V.S. All authors have read and agreed to the published version of the manuscript. **Funding:** The work was supported by the WZ/WI-IIT/4/2020 grant from Bialystok University of Technology and funded with resources for research by the Ministry of Education and Science in Poland. **Institutional Review Board Statement:** Not applicable. **Informed Consent Statement:** Not applicable. **Data Availability Statement:** The address of benchmark data set used in this paper is as follows: [[https://ddd.fit.cvut.cz/www/prj/Benchmarks/MCNC.7z](https://ddd.fit.cvut.cz/www/prj/Benchmarks/MCNC.7z)]([https://ddd.fit.cvut.cz/www/prj/Benchmarks/MCNC.7z](https://ddd.fit.cvut.cz/www/prj/Benchmarks/MCNC.7z)) (accessed on 1 July 2022). **Conflicts of Interest:** The authors declare no conflict of interest. ## References

* [PERSON] (1973) [PERSON] State reduction in incompletely specified finite state machines. _IEEE Trans. Comput._**1973**, _C_-22, 1099-1102. [CrossRef]
* [PERSON] and [PERSON] (1999) [PERSON]; [PERSON] A new algorithm for exact reduction of incompletely specified finite state machines. _IEEE Trans. Comput.-Aided Des._**1999**, _18,_ 1619-1632. [CrossRef]
* [PERSON] and [PERSON] (2007) [PERSON]; [PERSON] On state reduction of incompletely specified finite state machines. _Comput. Electr. Eng._**2007**, _33,_ 58-69. [CrossRef]
* [PERSON] et al. (1994) [PERSON]; [PERSON]; [PERSON]; [PERSON] Exact and heuristic algorithms for the minimization of incompletely specified state machines. _IEEE Trans. Comput. Aided Des._**1994**, _13,_ 167-177. * [PERSON] et al.