Pseudo-random encoding of states in the algorithm for algebraic synthesis of a finite state machine

Abstract

EN: Context. The problem of algebraic synthesis of finite state machine with datapath of transitions is considered. The circuit of this state machine may require less hardware expenses and have a lower cost compared to circuits of other classes of digital control units. The object of research is the process of finding complete and partial solutions of the problem of algebraic synthesis of finite state machine using specialized algorithms. One of such algorithms is the previously known algorithm of complete sequential enumeration of state coding variants with a fixed set of transition operations. In the vast majority of cases, complete sequential enumeration is performed too long, which makes its practical application in the process of synthesizing of finite state machines with operational transformation of state codes impossible. This paper proposes a new approach, which consists in replacing complete sequential enumeration of state coding variants with pseudo-random coding. This allows you to increase the number of state codes that change in each iteration of the algorithm and can contribute to a faster search for satisfactory solutions to the algebraic synthesis problem. Objective. Development and research of an algorithm for finding solutions to the algebraic synthesis problem of a finite state machine with datapath of transitions based on pseudo-random selection of state codes. Method. The research is based on the structure of finite state machine with datapath of transitions. The synthesis of the finite state machine circuit involves a mandatory stage of algebraic synthesis, the result of which is the combination of a certain way of states encoding with the assignment of arithmetic-logical operations to state machine transitions. Such combination is called the solution to the algebraic synthesis problem. In the general case, there are many solutions for a given finite state machine, each of which can be either complete (when operations are mapped to all transitions) or partial (when part of transitions cannot be implemented using any of the given operations). The more transitions are implemented by given operations, the less hardware expenses will be required to implement the state machine circuit and the better solution found. The search for the best solution requires consideration of a large number of possible variants of states encoding. The paper includes a modification of a previously known algorithm, which consists in replacing the complete sequential enumeration of variants of states encoding with pseudo-random code generation. Both algorithms were implemented in the form of software using the Python language and tested on the example of a finite state machine that implements an abstract control algorithm. In the course of the experiments, it was investigated which of the algorithms would find the best solution to algebraic synthesis problem in a fixed time. The experiments were repeated for different sets of transition operations. The purpose of the experiments was to evaluate which of state code assignment strategies is more effective: sequential enumeration of state codes or their pseudo-random generation. Results. Using the example of an abstract control algorithm, it is demonstrated that in general, pseudo-random assignment of state codes allows finding better solutions to the algebraic synthesis problem in the same time than sequential enumeration of state codes. Factors such as computer speed or the method of pseudo-random generation of state codes do not have a significant impact on the results of the experiments. The advantage of pseudo-random generation of state codes is preserved when using different sets of transition operations. Conclusions. The basis of the algebraic synthesis of finite state machine with datapath of transitions is an algorithm for finding solutions to the algebraic synthesis problem. The article proposes an algorithm for finding such solutions based on pseudo-random encoding of finite state machine states. The software implementation of this algorithm has proven that such approach is generally better than sequential enumeration for state encoding variants, since it allows finding better solutions (solutions with fewer operationally unimplemented transitions) in the same time. The pseudo-random assignment of state codes can be the basis of future algorithms for the algebraic synthesis of finite state machines. UK: Актуальність. Розглянуто задачу алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів. Схема цього автомата може потребувати менших витрат апаратури і мати меншу вартість у порівнянні зі схемами інших класів цифрових пристроїв керування. Об’єктом дослідження є процес пошуку повних і часткових розв’язків задачі алгебраїчного синтезу автомата із використанням спеціалізованих алгоритмів. Одним із таких алгоритмів є раніше відомий алгоритм повного послідовного перебору варіантів кодування станів при фіксованій множині операцій переходів. У переважній більшості випадків повний послідовний перебір виконується надто довго, що унеможливлює його практичне застосування в процесі синтезу автоматів з операційним перетворенням кодів станів. В даній роботі пропонується новий підхід, який полягає у заміні повного послідовного перебору варіантів кодування станів на псевдовипадкове кодування. Це дозволяє збільшити кількість кодів станів, що змінюються у кожній ітерації алгоритму, і може сприяти більш швидкому пошуку задовільних розв’язків задачі алгебраїчного синтезу. Мета. Розробка і дослідження алгоритму пошуку розв’язків задачі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів на основі псевдовипадкового вибору кодів станів. Метод. В основу дослідження покладено структуру мікропрограмного автомата з операційним автоматом переходів. Синтез схеми автомата передбачає обов’язковий етап алгебраїчного синтезу, результатом якого є поєднання певного способу кодування станів із заставленням арифметико-логічних операцій автоматним переходам. Таке поєднання називається розв’язком задачі алгебраїчного синтезу. В загальному випадку для заданого автомата існує багато розв’язків, кожен з яких може бути як повним (коли операції зіставлені усім переходам) або частковим (коли частина переходів не може бути реалізована за допомогою жодної із заданих операцій). Чим більше переходів реалізуються заданими операціями, тим менше апаратурних витрат потребуватиме реалізація схеми автомата і тим кращим є знайдений розв’язок. Пошук кращих розв’язків потребує розгляду великої кількості можливих варіантів кодування станів. В роботі здійснено модифікацію раніше відомого алгоритму, яка полягає у заміні повного послідовного перебору варіантів кодування станів на псевдовипадкову генерацію кодів. Обидва алгоритми були реалізовані програмно за допомогою мови Python і протестовані на прикладі мікропрограмного автомата, що імплементує абстрактний алгоритм керування. У процесі експериментів досліджувалось, який із алгоритмів знайде кращий розв’язок задачі алгебраїчного синтезу за фіксований час. Експерименти повторювались для різних наборів операцій переходів. Метою експериментів було оцінити, яка із стратегій завдання кодів станів є більш ефективною: послідовний перебір кодів станів чи їх псевдовипадкова генерація. Результати. На прикладі абстрактного алгоритму керування продемонстровано, що загалом псевдовипадкове завдання кодів станів дозволяє за однаковий час знайти кращі розв’язки задачі алгебраїчного синтезу, ніж послідовний перебір кодів станів. Такі фактори, як швидкодія комп’ютера чи метод псевдовипадкової генерації кодів станів, не мають суттєвого впливу на результат експериментів. Перевага псевдовипадкової генерації кодів станів зберігається при використанні різних наборів операцій переходів. Висновки. В основі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів лежить алгоритм пошуку розв’язків задачі алгебраїчного синтезу. В роботі запропоновано алгоритм пошуку таких розв’язків, оснований на псевдовипадковому кодуванні станів автомата. Програмна реалізація цього алгоритму довела, що такий підхід в загальному випадку є кращим за послідовний перебір варіантів кодування станів, оскільки дозволяє знайти кращі розв’язки (розв’язки з меншою кількістю операційно нереалізованих переходів) за той самий час. Псевдовипадкове завдання кодів станів може бути покладене в основу майбутніх алгоритмів алгебраїчного синтезу мікропрограмних автоматів.