DOI
10.34229/KCA2522-9664.26.1.2
UDC 004.94:004.2
R.M. Babakov
Vasyl’ Stus Donetsk National University, Vinnytsia, Ukraine,
newcpld@gmail.com
A.A. Barkalov
University of Zielona Gora, Zielona Gora, Poland,
a.barkalov@imei.uz.zgora.pl
ALGORITHM FOR ALGEBRAIC SYNTHESIS OF A FINITE STATE
MACHINE BASED ON OPERATIONS ENUMERATION
Abstract. For a finite state machine with a datapath of transitions, a new algebraic synthesis algorithm is proposed that combines the enumeration of state coding ways with the enumeration of transition operations. The algorithm is based on the representation of any transition operation in the form of an arithmetic-logical operator over two operands, which are the code of the state machine’s current state and a constant of the corresponding format. This allows you to automate the enumeration of transition operations by enumerating the constants in the used operations within the range of values of the state codes of the finite state machine. The result of the algorithm is a set of solutions of the algebraic synthesis problem, each of which contains values of the state codes and a set of values of the constants of the used operations. The combination of enumeration of transition operations with enumeration of state coding ways expands the search area and increases the number of solutions found for the algebraic synthesis problem compared to the prototype algorithm that does not use enumeration of transition operations. A software implementation of the proposed algorithm was performed, confirming its correctness and effectiveness.
Keywords: finite state machine, datapath of transitions, graph-scheme of algorithm, algebraic synthesis, enumeration of transition operations.
full text
REFERENCES
- 1. Suh S.C., Tanik U.J., Carbone J.N., Eroglu A. (Eds.) Applied cyber-physical systems. New York: Springer, 2014. 253 p. https://doi.org/10.1007/978-1-4614-7336-7.
- 2. Marwedel P. Embedded system design: Embedded systems foundations of cyber-physical systems, and the internet of things. 4th ed. Cham: Springer International Publishing, 2021. 433 p. https://doi.org/10.1007/978-3-030-60910-8.
- 3. Bailliul J., Samad T. (Eds.) Encyclopedia of systems and control. 2nd ed. Cham: Springer International Publishing, 2021. 2469 p. https://doi.org/10.1007/978-3-030-44184-5.
- 4. Baranov S. Finite state machines and algorithmic state machines: Fast and simple design of complex finite state machines. Amazon.com, 2018. 185 p.
- 5. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
- 6. Minns P., Elliot I. FSM-based digital design using Verilog HDL. Hoboken: John Wiley and Sons, 2008. 408 p.
- 7. Czerwinski R., Kania D. Finite state machine logic synthesis for complex programmable logic devices. Berlin: Springer, 2013. LNEE. Vol. 231. 172 p. https://doi.org/10.1007/978-3-642-36166-1.
- 8. Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and optimization of FPGA-based systems. Cham: Springer International Publishing, 2014. LNEE. Vol. 294. 432 p. https://doi.org/10.1007/978-3-319-04708-9.
- 9. Kubica M., Kania D. Area-oriented technology mapping for LUT-based logic blocks. International Journal of Applied Mathematics and Computer Science. 2017. Vol. 27, Iss. 1. P. 207–222. https://doi.org/10.1515/amcs-2017-0015.
- 10. Gajski D. Principles of digital design. Hoboken: Prentice-Hall International, 1997. 447 p.
- 11. Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier Science, 2011. 784 p.
- 12. Garcia-Vargas I., Senhadji-Navarro R., Jimnez-Moreno G., Civit-Balcells A., Guerra-Gutierrez P. ROM-based finite state machine implementation in low cost FPGAs. Proc. 2007 IEEE International Symposium on Industrial Electronics (04–07 June 2007, Vigo, Spain). Vigo, 2007. P. 2342–2347. https://doi.org/10.1109/ISIE.2007.4374972.
- 13. Kubica M., Kania D., Kulisz J. A technology mapping of FSMs based on a graph of excitations and outputs. IEEE Access. 2019. Vol. 7. P. 16123–16131. https://doi.org/10.1109/ACCESS.2019.2895206.
- 14. Barkalov A.A., Titarenko L.A., Babakov R.M. Synthesis of the finite state machine with datapath of transitions according to the operational table of transitions. Radio Electronics, Computer Science, Control. 2022. N 3. P. 109–119. https://doi.org/10.15588/1607-3274-2022-3-11.
- 15. Barkalov A.A., Babakov R.M. An algorithm for solving the problem of algebraic synthesis of a finite-state machine with datapath of transitions based on a matrix approach. Cybernetics and Systems Analysis. 2025. Vol. 61, N 3. P. 347–353. https://doi.org/10.1007/s10559-025-00773-z.
- 16. Barkalov A.A., Babakov R.M. A matrix method for detecting formal solutions to the problem of algebraic synthesis of a finite-state machine with a datapath of transitions. Cybernetics and Systems Analysis. 2023. Vol. 59, N 2. P. 190-198. https://doi.org/10.1007/s10559--023-00554-6.
