Badania metody minimalizacji nie w pełni określonych automatów skończonych realizowanej w oparciu o sklejanie dwóch stanów

摘要

W pracy opisano badania eksperymentalne metody minimalizacji nie w pełni określonych automatów skończonych. Proponowana metoda bazuje na operacji sklejania dwóch stanów. W pracy pokazano warunki konieczne łączenia dwóch stanów oraz przypadek tworzenia się stanów oczekiwania. Opisana metoda pozwala na redukcję liczby stanów średnio 1,16 razy i liczby przejść automatu 1,27 razy. Pozwala także na redukcję liczby przejść w stosunku do programu STAMINA średnio 1,40 razy. Przedstawiono także wyniki implementacji zminimalizowanych automatów w strukturach CPLD i FPGA, które potwierdziły skuteczność metody.%This paper presents experiments on a heuristic method for minimization of an incompletely specified finite state machine with unspecified values of output variables. The proposed method is based on two states merging. In addition to reduction of the finite state machine (FSM) states, the method also allows reducing the number of FSM transitions and input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then from the set there is selected the pair of states which best matches the criteria of minimizing. In the paper, the conditions of state equivalence are presented. Two FSM states can be merged only if they are equivalent. It should be noted that the wait states can be formed at the merging of FSM states. This method allows reducing the number of internal states of the initial FSM by 1.16 times on the average, and by 2.75 times on occasion. An average reduction of the number of FSM transitions makes up 1.27 times. The comparison of the proposed method with the program STAMINA shows that the offered method does not reduce the number of FSM states, however it allows reducing the number of FSM transitions by 1.40 times on the average. The results of implementation of the minimized FSMs in programmable devices showed that the proposed method allowed building FSMs at lower cost and higher speed than the STAMINA program for CPLD and FPGA devices.