DOI
10.34229/KCA2522-9664.26.5.1
UDC 004.94:004.2
R.M. Babakov
Vasyl' Stus Donetsk National University, Vinnytsia, Ukraine,
newcpld@gmail.com
A.A. Barkalov
Institute of Control and Computation Engineering, University of Zielona Gora,
Zielona Gora, Poland, a.barkalov@imei.uz.zgora.pl
ALGORITHMS FOR ALGEBRAIC SYNTHESIS OF A FINITE STATE MACHINE
BASED ON STATE CODE SELECTION
Abstract. For a finite state machine with datapath of transitions, two modifications of known algebraic synthesis algorithms are proposed, combining the enumeration of state coding variants with a special algorithm for selecting codes for each state of the state machine. The algorithm for selecting state codes is based on the analysis of a set of codes that are not currently used to encode any state of the state machine, although they are admissible for use. For each state of the state machine, a code is selected from the set of unused codes that allows to minimize the number of transitions not covered by a given set of operations. Studies have shown that the combination of the enumeration of state coding variants with the selection of state codes allows to find formal solutions to the algebraic synthesis problem that have a smaller number of uncovered transitions and lead to lower hardware expenses in the logic circuit of a finite state machine with datapath of transitions. A software implementation of the proposed algorithms was performed, which confirmed their correctness and effectiveness.
Keywords: finite state machine, datapath of transitions, graph-scheme of algorithm, algebraic synthesis, state code selection.
full text
REFERENCES
- Alur R. Principles of cyber-physical systems. Cambridge: MIT Press, 2015. 464 p.
- Gajski D., Abdi S., Gerstlauer A., Schirner G. Embedded system design: Modeling, synthesis and verification. Berlin; Heidelberg: Springer Science & Business Media, 2009. 352 p. https://doi.org/10.1007/978-1-4419-0504-8.
- Arora M. Embedded system design: introduction to SîC system architecture. Islamabad, Pakistan: Learning Bytes Publishing, 2016. 214 p.
- Baranov S. Finite state machines and algorithmic state machines. Seattle: Amazon, 2018. 185 p.
- DeMicheli G. Synthesis and optimization of digital circuits. NY: McGraw-Hill, 1994. 576 p.
- Salauyou V. Area and performance estimates of finite state machines in reconfigurable systems. Applied Sciences. 2024. Vol. 14, N 24. Article number 11833. https://doi.org/10.3390/app142411833.
- Baranov S. High level synthesis of digital systems: For data path and control dominated systems. Ottawa, ON, Canada: ISBN Canada, 2018. 207 p.
- Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state machines. Tallinn: TUT Press, 2012. 240 p.
- Kubica M., Kania D. Area-oriented technology mapping for LUT-based logic blocks. International Journal of Applied Mathematics and Computer Science. 2017. Vol. 27. P. 207–222. https://doi.org/10.1515/amcs-2017-0015.
- Gajski D. Principles of digital design. Hoboken: Prentice-Hall International Editions; Prentice-Hall International, 1997. 447 p.
- Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier Science, 2011. 784 p.
- Garcia-Vargas I., Senhadji-Navarro R., JimÁnez-Moreno G. et al. ROM-based finite state machine implementation in low cost FPGAs. Proc. of the IEEE International Symposium on Industrial Electronics ISIE 2007. (Vigo, Spain, 4–7 June 2007). IEEE, 2007. P. 2342–2347. https://doi.org/10.1109/ISIE.2007.4374972.
- Das N., Priya A. Reset: A reconfigurable state encoding technique for FSM to achieve security and hardware optimality. Microprocessors and Microsystems. 2020. Vol. 77. Article number 103196. https://doi.org/10.1016/j.micpro.2020.103196.
- 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. Vol. 109, N 3. P. 109–119. https://doi.org/10.15588/1607-3274-2022-3-11.
- 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.
- Babakov R.M., Barkalov A.A., Titarenko L.A. Pseudo-random encoding of states in the algorithm for algebraic synthesis of a finite state machine. Radio Electronics, Computer Science, Control. 2025. Vol. 109, N 4. P. 31–40. https://doi.org/10.15588/1607-3274-2025-4-3.
- Barkalov A.A., Titarenko L.A., Babakov R.M., Voitenko M.O. Algorithmic differences of complete and partial algebraic synthesis of a finite state machine with datapath of transitions. Radio Electronics, Computer Science, Control. 2024. N 4. P. 143–152. https://doi.org/10.15588/1607-3274-2024-4-14.
