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

• Autorzy: Klimowicz A.

Warianty tytułu

EN

Experiments on the method of Mealy state machine minimization based on two-states merging

• Języki publikacji: PL

Abstrakty

PL

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.

EN

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.

Słowa kluczowe

PL

automat skończony; minimalizacja liczby stanów; synteza logiczna; łączenie stanów

EN

finite state machine (FSM); state minimization; logic synthesis; state merging

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2014
• Tom: R. 60, nr 5
• Strony: 297--300
• Opis fizyczny: Bibliogr. 10 poz., tab.

Twórcy

autor

Klimowicz A.

• Politechnika Białostocka, ul. Wiejska 45a, 15-351 Białystok

Bibliografia

• [1] Paull M., Unger S.: Minimizing the number of states in incompletely specified state machines, IRE Trans. Electron. Comput., vol. EC-8, pp. 356–367, Sept. 1959.
• [2] Pfleeger C. F.: State reduction in incompletely specified finite state machines, IEEE Trans. Comput., vol. C-22, pp. 1099–1102, Dec. 1973.
• [3] Grasselli A., Luccio F.: A method for minimizing the number of internal states in incompletely specified sequential networks, IRE Trans. Electron. Comput., vol. EC-14, no. 3, pp. 350–359, June 1965.
• [4] Rho J.K., Hachtel G., Somenzi F., Jacoby R.: Exact and heuristic algorithms for the minimization of incompletely specified state machines, IEEE Trans. Computer-Aided Design, vol. 13, pp. 167– 177, Feb. 1994.
• [5] Kam T., Villa T., Brayton R., Sangiovanni-Vincentelli A.: Synthesis of FSM’s: Functional Optimization. Norwell, MA: Kluwer Academic, 1997.
• [6] Pena J.M., Oliveira A.L.: A new algorithm for exact reduction of incompletely specified finite state machines, IEEE Trans. Computer- Aided Design, vol. 18, pp. 1619-1632, Nov. 1999.
• [7] Ahmad I., Das A.S.: A heuristic algorithm for minimization of incompletely specified finite state machines, Computers and Electrical Engineering, vol. 27, issue 2, pp. 159-172, May 2001.
• [8] Gören S., Ferguson F.: On state reduction of incompletely specified finite state machines, Computers and Electrical Engineering, vol. 33, issue 1, pp. 58-69, Jan. 2007.
• [9] Klimovich А.S., Solov’ev V.V. Minimization of Mealy finite-state machines by internal states gluing, Journal of Computer and Systems Sciences International, 2012, Vol 51. No. 2, pp. 244-255.
• [10] Yang S.: Logic Synthesis and Optimization Benchmarks User Guide; Microelectronics Center of North Carolina, Research Triangle Park, NC, 1991.