Minimization of finite state machines by states merging

• Autorzy: Salauyou V.
• Języki publikacji: EN

Abstrakty

EN

The paper presents a method for minimization of finite state machines (FSMs) with unspecified values of output variables. The proposed method is based on merging of two states. In addition to reduction of the FSM states, the method also allows reducing the number of FSM transitions and FSM input variables. This method enables reducing the number of internal states of the initial FSM by 1.22 times on the average, and by 2.75 times on occasion. An average reduction of the number of FSM transitions makes up 1.32 times, and on occasion may amount to 2.27 times. The comparison of the method with the program STAMINA shows that the offered method allows decreasing the number of FSM transitions by 1.55 times on the average, and by 3.92 times on occasion.

Słowa kluczowe

EN

finite state machine; minimization; state merging; FSM transitions; FSM input variables; digital systems

• Wydawca: Wydawnictwo PAK
• Czasopismo: Measurement Automation Monitoring
• Rocznik: 2016
• Tom: Vol. 62, No. 5
• Strony: 179--181
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Salauyou V.

Bibliografia

• [1] Paull M. C., Unger S. H.: Minimizing the number of states in incompletely specified sequential switching functions. IRE Trans. on Electronic Computers, 1959, Vol. EC-8, No. 3, pp. 356-367.
• [2] Pfleeger C. P.: State reduction in incompletely specified finite-state machines. IEEE Trans. on Computers, 1973, Vol. C-22, No. 12, pp. 1099-1102.
• [3] Grasselli A., Luccio F.: A method for minimizing the number of internal states in incompletely specified sequential networks. IEEE Trans. on Electronic Computers, 1965, Vol. EC-14, No. 3, pp. 350-359.
• [4] De Micheli G.: Synthesis and optimization of digital circuits. New York: McGraw Hill, 1994.
• [5] Rho J. K., Hachtel G. D., Somenzi F., Jacoby R. M.: Exact and heuristic algorithms for the minimization of incompletely specified state machines. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1994, Vol.13, No. 2, pp. 167-177.
• [6] Kam T., Villa T., Brayton R., Sangiovanni-Vincentelli A.: Synthesis of FSMs: functional optimization. Norwell, MA: Kluwer Academic Publishers, 1997.
• [7] Pena J. M., Oliveira A. L.: A new algorithm for exact reduction of incompletely specified finite state machines. IEEE Trans. on Computer-Aided Design, 1999, Vol. 18, No. 11, pp. 1619-1632.
• [8] Ahmad I., Das A. S.: A heuristic algorithm for minimization of incompletely specified finite state machines. Computers and Electrical Engineering, 2001, Vol. 27, pp. 159-172.
• [9] Gören S., Ferguson F.: On state reduction of incompletely specified finite state machines. Computers and Electrical Engineering, 2007, Vol. 33, No. 1, pp. 58-69.
• [10] Salauyou V.: FSM state merging for low power. Measurement, Automation, Monitoring, 2015, Vol. 61, nr 7, s. 337-339.
• [11] Salauyou V., Klimowicz A., Grzes T., Bulatowa I., Dimitrowa-Grekow T.: Synthesis methods of finite state machines implemented in package ZUBR. Proc. of the Sixth International Conference Computer-Aided Design of Discrete Devices (CAD DD’7), Minsk, Belarus, November 14-15, 2007, pp. 53-56.

Uwagi

EN

Thee present study was supported by the grant S/W7/1/2013 from the Bialystok University of Technology and funded from the resources for research by the Ministry of Science and Higher Education.