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