DOI
10.34229/KCA2522-9664.26.1.2
УДК 004.94:004.2
Р.М. БАБАКОВ
Донецький національний університет імені Василя Стуса, Вінниця, Україна,
newcpld@gmail.com
О.О. БАРКАЛОВ
Зеленогурський університет, Зелена Гура, Польща,
a.barkalov@imei.uz.zgora.pl
АЛГОРИТМ АЛГЕБРАЇЧНОГО СИНТЕЗУ МІКРОПРОГРАМНОГО
АВТОМАТА НА ОСНОВІ ПЕРЕБОРУ ОПЕРАЦІЙ
Анотація. Для мікропрограмного автомата з операційним автоматом переходів запропоновано новий алгоритм алгебраїчного синтезу, що поєднує перебiр способів кодування станів з перебором операцій переходів. Алгоритм ґрунтується на представленні будь-якої операції переходів у вигляді арифметико-логічного оператора над двома операндами, якими є код поточного стану автомата і константа відповідного формату. Це дає змогу автоматизувати процес перебору операцій переходів за допомогою перебору констант у використовуваних операціях у діапазоні значень кодів станів автомата. Результатом роботи алгоритму є множина розв’язків задачі алгебраїчного синтезу, кожен з яких містить значення кодів окремих станів та набір значень констант використовуваних операцій. Поєднання перебору операцій переходів з перебором способів кодування станів розширює область пошуку та збільшує кількість знайдених розв’язків задачі алгебраїчного синтезу порівняно з алгоритмом-прототипом, що не використовує перебір операцій переходів. Виконано програмну реалізацію запропонованого алгоритму, яка підтвердила його коректність і результативність.
Ключові слова: мікропрограмний автомат, операційний автомат переходів, граф-схема алгоритму, алгебраїчний синтез, перебір операцій переходів.
повний текст
СПИСОК ЛІТЕРАТУРИ
- 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.
