PSEUDO-RANDOM ENCODING OF STATES IN THE ALGORITHM FOR ALGEBRAIC SYNTHESIS OF A FINITE STATE MACHINE

Abstract

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