Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
-->


DOI 10.34229/KCA2522-9664.25.3.2
УДК 004.94:004.2

Р.М. БАБАКОВ
Донецький національний університет імені Василя Стуса, Вінниця, Україна,
newcpld@gmail.com

О.О. БАРКАЛОВ
Університет Зеленогурський, Зелена Гура, Польща, a.barkalov@imei.uz.zgora.pl


АЛГОРИТМ РОЗВ’ЯЗАННЯ ЗАДАЧІ АЛГЕБРАЇЧНОГО СИНТЕЗУ
МІКРОПРОГРАМНОГО АВТОМАТА З ОПЕРАЦІЙНИМ АВТОМАТОМ
ПЕРЕХОДІВ НА ОСНОВІ МАТРИЧНОГО ПІДХОДУ

Анотація. Для мікропрограмного автомата з операційним автоматом переходів запропоновано новий алгоритм розв’язання задачі алгебраїчного синтезу, що дає змогу знайти формальні розв’язки задачі для заданої множини операцій переходів. Алгоритм базується на представленні способу кодування станів у вигляді матриці переходів. Цій матриці зіставляється об’єднана матриця операцій, яка містить усі можливі варіанти перетворення кодів станів за допомогою заданої множини операцій переходів. Поелементне зіставлення матриць дає змогу виявити наявність формального розв’язку для вибраного набору кодів станів. Показано, що запропонований алгоритм знаходить усі можливі розв’язки за умови повного перебору способів кодування станів. Оцінено швидкодію запропонованого алгоритму у разі його реалізації на мові Python.

Ключові слова: мікропрограмний автомат, операційний автомат переходів, граф-схема алгоритму, алгебраїчний синтез, кодування станів.


повний текст

СПИСОК ЛІТЕРАТУРИ

  • 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.




© 2025 Kibernetika.org. All rights reserved.