DOI
10.34229/KCA2522-9664.25.3.2
UDC 004.94:004.2
ALGORITHM FOR SOLVING THE PROBLEM OF ALGEBRAIC SYNTHESIS
OF A FINITE STATE MACHINE WITH DATAPATH OF TRANSITIONS
BASED ON A MATRIX APPROACH
Abstract. A new algorithm for solving the problem of algebraic synthesis is proposed for a finite state machine
with a datapath of transitions, which allows finding formal solutions to the problem for a given set of transition operations. The algorithm is based on the presentation of states encoding in the form of a transition matrix. This matrix is associated with a combined matrix of operations, which contains all possible options for the transformation of state codes using a given set of transition operations. The element-by-element comparison of matrices allows revealing the availability of a formal solution for the selected set of state codes. It is shown that the proposed algorithm makes it possible to find all possible solutions using a complete enumeration of the ways of state encoding. The speed of the proposed algorithm was evaluated when it was implemented in the Python language.
Keywords: finite state machine, datapath of transitions, graph-scheme of algorithm, algebraic synthesis, states encoding.
full text
REFERENCES
- 1. Baranov S. Logic and system design of digital systems. Tallinn: TUTPress, 2008. 276 p.
- 2. Bailliul J., Samad T. Encyclopedia of systems and control. London: Springer, 2015. 1554 p.
- 3. DeMicheli G. Synthesis and optimization of digital circuits. NY: McGraw-Hill, 1994. 576 p.
- 4. Baranov S. Finite state machines and algorithmic state machines. Seattle: Amazon, 2018. 185 p.
- 5. Gajski D.D., Abdi S., Gerstlauer A., Schirner G. Embedded system design: Modeling, synthesis and verification. 1st ed. New York: Springer, 2009. http://doi.org/10.1007/978-1-4419-0504-8.
- 6. Marwedel P. Embedded system design: Embedded systems foundations of cyber-physical systems, and the Internet of things. 3d ed. New York: Springer, 2021. 433 p. https://doi.org/10.1007/978-3-030-60910-8.
- 7. Suh S.C., Tanik U.J., Carbone J.N. Applied cyber-physical systems. New York: Springer, 2013. 253 p. https://doi.org/10.1007/978-1-4614-7336-7.
- 8. Kubica M., Opara A., Kania D. Technology mapping for LUT-based FPGA. Cham: Springer, 2021. 207 p. https://doi.org/10.1007/978-3-030-60488-2.
- 9. Scholl C. Functional decomposition with application to FPGA synthesis. Boston: Kluwer Academic, 2001. 264 p. https://doi.org/10.1007/978-1-4757-3393-8.
- 10. Machado L., Cortadella J. Support-reducing decomposition for FPGA mapping. IEEE Transaction on Computer-Aided Design of Integrated Circuits Systems. 2020. Vol. 39, Iss. 1. P. 213–224. https://doi.org/10.1109/.
- 11. Chattopadhyay S. Area conscious state assignment with flip-flop and output polarity selection for finite state machine synthesis — A genetic algorithm approach. The Computer Journal. 2005. Vol. 48, Iss. 4. P. 443–450. https://doi.org/10.1093/comjnl/.
- 12. Opara A., Kubica M., Kania D. Decomposition approaches for power reduction. IEEE Access. 2023. Vol. 11. P. 29417–29429. https://doi.org/10.1109/ACCESS.2023.3260970.
- 13. Barkalov A.A., Babakov R.M. Operational formation of state codes in microprogram automata. Cybernetics and Systems Analysis. 2011. Vol. 47, N 2. P. 193–197. https://doi.org/10.1007/s10559-011-9301-y.
- 14. Barkalov A.A., Babakov R.M. determining the area of efficient application of a microprogrammed finite-state machine with datapath of transitions. Cybernetics and Systems Analysis. 2018. Vol. 54, N 3. P. 366–375. https://doi.org/10.1007/s10559-018-0038-8.
- 15. 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 (109). P. 109–119. https://doi.org/10.15588/1607-3274-2022-3-11.
- 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.
