Search academic texts

Information × Registration Number 2125U003936, Article popup.category Опубліковано, Стаття Title PSEUDO-RANDOM ENCODING OF STATES IN THE ALGORITHM FOR ALGEBRAIC SYNTHESIS OF A FINITE STATE MACHINE popup.author Бабаков Р. М.Баркалов О. О.Тітаренко Л. О.Babakov R. M.Barkalov A. A.Titarenko L. A. popup.publication 24-12-2025 popup.source_user Журнал "Радіоелектроніка, інформатика, управління" (Національний університет "Запорізька політехніка") popup.source https://ric.zp.edu.ua/article/view/346009 popup.publisher National University "Zaporizhzhia Polytechnic" Description Актуальність. Розглянуто задачу алгебраїчного синтезу мікропрограмного автомата з операційним автоматомпереходів. Схема цього автомата може потребувати менших витрат апаратури і мати меншу вартість у порівнянні зі схемами інших класів цифрових пристроїв керування. Об’єктом дослідження є процес пошуку повних і частковихрозв’язків задачі алгебраїчного синтезу автомата із використанням спеціалізованих алгоритмів. Одним із таких алгоритмів є раніше відомий алгоритм повного послідовного перебору варіантів кодування станів при фіксованій множині операцій переходів. У переважній більшості випадків повний послідовний перебір виконується надто довго, щоунеможливлює його практичне застосування в процесі синтезу автоматів з операційним перетворенням кодів станів.В даній роботі пропонується новий підхід, який полягає у заміні повного послідовного перебору варіантів кодування станів на псевдовипадкове кодування. Це дозволяє збільшити кількість кодів станів, що змінюються у кожній ітерації алгоритму, і може сприяти більш швидкому пошуку задовільних розв’язків задачі алгебраїчного синтезу.Мета. Розробка і дослідження алгоритму пошуку розв’язків задачі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів на основі псевдовипадкового вибору кодів станів.Метод. В основу дослідження покладено структуру мікропрограмного автомата з операційним автоматом переходів. Синтез схеми автомата передбачає обов’язковий етап алгебраїчного синтезу, результатом якого є поєднання певного способу кодування станів із заставленням арифметико-логічних операцій автоматним переходам. Таке поєднання називається розв’язком задачі алгебраїчного синтезу. В загальному випадку для заданого автомата існує багато розв’язків, кожен з яких може бути як повним (коли операції зіставлені усім переходам) або частковим (коли частина переходів не може бути реалізована за допомогою жодної із заданих операцій). Чим більше переходів реалізуються заданими операціями, тим менше апаратурних витрат потребуватиме реалізація схеми автомата і тим кращим є знайдений розв’язок. Пошук кращих розв’язків потребує розгляду великої кількості можливих варіантів кодування станів. В роботі здійснено модифікацію раніше відомого алгоритму, яка полягає у заміні повного послідовного переборуваріантів кодування станів на псевдовипадкову генерацію кодів. Обидва алгоритми були реалізовані програмно за допомогою мови Python і протестовані на прикладі мікропрограмного автомата, що імплементує абстрактний алгоритм керування. У процесі експериментів досліджувалось, який із алгоритмів знайде кращий розв’язок задачі алгебраїчного синтезу за фіксований час. Експерименти повторювались для різних наборів операцій переходів. Метою експериментів було оцінити, яка із стратегій завдання кодів станів є більш ефективною: послідовний перебір кодів станів чи їх псевдовипадкова генерація.Результати. На прикладі абстрактного алгоритму керування продемонстровано, що загалом псевдовипадкове завдання кодів станів дозволяє за однаковий час знайти кращі розв’язки задачі алгебраїчного синтезу, ніж послідовний перебір кодів станів. Такі фактори, як швидкодія комп’ютера чи метод псевдовипадкової генерації кодів станів, не мають суттєвого впливу на результат експериментів. Перевага псевдовипадкової генерації кодів станів зберігається при використанні різних наборів операцій переходів.Висновки. В основі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів лежить алгоритм пошуку розв’язків задачі алгебраїчного синтезу. В роботі запропоновано алгоритм пошуку таких розв’язків, оснований на псевдовипадковому кодуванні станів автомата. Програмна реалізація цього алгоритму довела, що такий підхід в загальному випадку є кращим за послідовний перебір варіантів кодування станів, оскільки дозволяє знайти кращі розв’язки (розв’язки з меншою кількістю операційно нереалізованих переходів) за той самий час.Псевдовипадкове завдання кодів станів може бути покладене в основу майбутніх алгоритмів алгебраїчного синтезу мікропрограмних автоматів popup.nrat_date 2026-02-09 Close