ALGORITHMIC DIFFERENCES OF COMPLETE AND PARTIAL ALGEBRAIC SYNTHESIS OF A FINITE STATE MACHINE WITH DATAPATH OF TRANSITIONS

Abstract

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.