Algorithmic differences of complete and partial algebraic synthesis of a finite state machine with datapath of transitions

Abstract

EN: Context. The problem of algorithmization the search for formal solutions of the problem of algebraic synthesis of a finite state ma-chine with datapath of transitions is considered. The concept of complete and partial solutions of this problem is proposed. The object of research is the automated synthesis of the finite state machine in the part of the function of transitions without taking into account the function of outputs. The basis of the algebraic implementation of the transition function is the author's approach to the transformation of state codes using a set of arithmetic and logical operations. The search for formal solutions to the problem of algebraic synthesis is a complex process that requires the use of appropriate methods and algorithms aimed at special coding of states and mapping of operations of transitions to individual state machine transitions. The use of partial solutions of the problem of algebraic synthesis can contribute to reducing the executing time of such algorithms and reducing the overall design time of digital control devices based on a finite state machine with an datapath of transitions. Objective. Development and research of algorithms for finding complete and partial solutions to the problem of algebraic synthesis of a finite state machine with datapath of transitions. Method. The research is based on the structure of a finite state machine with datapath of transitions. The synthesis of the circuit of the state machine involves the preliminary solution of the problem of algebraic synthesis. The result is the so-called formal solution of this problem, which contains two components. The first component is defined state codes, the second component is arithmetic and logic operations mapped to separate state machine transitions. Finite state machine can be synthesized in that case if transformation of given state codes in the process of making transitions is possible using a given set of operations. Verification of this possibility is carried out using the known matrix approach. It involves the formation and element-by-element mapping of two matrices – the matrix of transitions and the combined matrix of operations. As a result, a coverage matrix is formed, which reflects the possibility of implementing (covering) of state machine transitions by specified arithmetic and logic operations. Changing the way of encoding states or the set of operations can give different solutions to the problem of algebraic synthesis with a greater or lesser number of covered state machine transitions. Results. Using the example of an abstract graph-scheme of the control algorithm, it is demonstrated that the solution of the problem of algebraic synthesis of a finite state machine with datapath of transitions can be considered a situation when one or more state machine transitions cannot be implemented using a given set of operations. It is proposed to call such situation as a partial solution of the problem of algebraic synthesis. The implementation of all transitions by specified operations gives a complete solution of this problem, but the number of complete solutions is always much smaller than the number of partial solutions. Therefore, in the general case, the search for complete solutions takes much more time and, moreover, is not always possible. Conclusions. The design of a logical circuit of a finite state machine with datapath of transitions is possible in the case of a complete or partial solution of the problem of algebraic synthesis. In the case of a partial solution, those transitions that cannot be implemented by any of the available operations are implemented in a canonical way using a system of Boolean equations. The search for complete solutions generally takes more time than the search for partial solutions. This makes actual the development of algorithms and methods of synthesis of this class of finite state machine, based on the search for partial solutions of the problem of algebraic synthesis. UK: Актуальність. Розглянуто задачу алгоритмізації пошуку формальних розв’язків задачі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів. Запропоновано поняття повного та часткового розв’язків цієї задачі. Об’єктом дослідження є автоматизований синтез автомата в частині функції переходів без урахування функції виходів. В основі алгебраїчної реалізації функції переходів знаходиться авторський підхід до перетворення кодів станів за допомогою множини арифметико-логічних операцій. Пошук формальних розв’язків задачі алгебраїчного синтезу є складним процесом, що потребує використання відповідних методів і алгоритмів, спрямованих на спеціальне кодування станів та зіставлення операцій переходів окремим автоматним переходам. Використання часткових розв’язків задачі алгебраїчного синтезу може сприяти зменшенню часу роботи таких алгоритмів та зменшенню загального часу проектування цифрових пристроїв керування на базі мікропрограмного автомата з операційним автоматом переходів. Мета. Розробка і дослідження алгоритмів пошуку повного і часткового розв’язків задачі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів. Метод. В основу дослідження покладено структуру мікропрограмного автомата з операційним автоматом переходів. Синтез схеми автомата передбачає попереднє розв’язання задачі алгебраїчного синтезу. Результатом є так званий формальний розв’язок цієї задачі, який містить в собі дві складових. Першою складовою є визначені коди станів, другою складовою – арифметико-логічні операції, зіставлені окремим автоматним переходам. Автомат може бути синтезований в тому випадку, якщо при заданих кодах станів їх перетворення в процесі виконання переходів можливе за допомогою заданої множини операцій. Перевірка цієї можливості здійснюється за допомогою відомого матричного підходу. Від передбачає формування і поелементне зіставлення двох матриць – матриці переходів і об’єднаної матриці операцій. В результаті формується матриця покриття, яка відображає можливість реалізації (покриття) автоматних переходів за допомогою заданих арифметико-логічних операцій. Зміна способу кодування станів або набір операцій може давати інші розв’язки задачі алгебраїчного синтезу з більшою чи меншою кількістю покритих автоматних переходів. Результати. На прикладі абстрактної граф-схеми алгоритму керування продемонстровано, що розв’язком задачі алгебраїчного синтезу мікропрограмного автомата з операційним автоматом переходів може вважатись ситуація, коли один або більше автоматних переходів не можуть бути реалізовані за допомогою заданого набору операцій. Таку ситуацію запропоновано називати частковим розв’язком задачі алгебраїчного синтезу. Реалізація усіх без винятку переходів за допомогою заданих операцій дає повний розв’зок цієї задачі, однак кількість повних розв’язків завжди є значно меншою за кількість часткових розв’язків. Отже, в загальному випадку пошук повних розв’язків займає набагато більше часу і до того ж є не завжди можливим. Висновки. Проєктування логічної схеми мікропрограмного автомата з операційним автоматом переходів можливе у випадку наявності повного або часткового розв’язку задачі алгебраїчного синтезу. У випадку часткового розв’язку ті переходи, які не можуть бути реалізовані жодною з наявних операцій, реалізуються в канонічний спосіб за допомогою системи булевих рівнянь. Пошук повних розв’язків в загальному випадку потребує більше часу, ніж пошук часткових розв’язків. Це робить актуальним розробку алгоритмів і методів синтезу даного класу автоматів, основаних на пошуку часткових розв’язків задачі алгебраїчного синтезу.