Abstract
This article describes a method of synthesizing finite-state machines (FSMs) on programmable logic devices (PLDs) while using the values of the input variables for coding the internal states. For this purpose, it is suggested to combine the structural models of FSMs of class A and E. The method of synthesizing a combined FSM model of AE class, which consists of splitting the internal states for fulfilling the necessary conditions of synthesizing an E-class machine and coding the internal states of an AE-class machine, is discussed. It is shown that this method allows reducing the cost of implementing FSMs for various families of PLDs by up to factors of 1.57 to 2.33 for binary coding and 3.00 for unary coding. This method also allows increasing the operation speed by up to 1.22–1.59 factors for binary coding and 1.34–2.93 for unary coding. In conclusion, recommendations are given regarding the practical use of the method, and possible areas for further development are suggested.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
V. V. Solov’ev, “Minimization of mealy finite-state machines by using the values of the output variables for state assignment,” J. Comput. Syst. Sci. Int. 56, 96 (2017).
I. Garcia-Vargas and R. Senhadji-Navarro, “Finite state machines with input multiplexing: a performance study,” IEEE Trans. Comput Aided Des. 34, 867–871 (2015).
A. H. El-Maleh, “Majority-based evolution state assignment algorithm for area and power optimisation of sequential circuits,” IET Comput. Digital Tech. 10, 30–36 (2016).
A. C. Abdullah, C. Y. Ooi, N. B. Ismail, and N. B. Mohammad, “Power-aware through-silicon-via minimization by partitioning finite state machine with datapath,” in Proceedings of the International Symposium on Circuits and Systems ISCAS, Montreal, Canada (IEEE, 2016).
S. Pendyala and S. Katkoori, “State encoding based NBTI optimization in finite state machines,” in Proceedings of the 17th International Symposium on Quality Electronic Design ISQED, Santa Clara, USA (IEEE, 2016).
V. A. Pedroni, “Introducing deglitched-feedback plus convergent encoding for straight hardware implementation of asynchronous finite state machines,” in Proceedings of the International Symposium on Circuits and Systems ISCAS, Lisbon, Portugal (IEEE, 2015).
F. T. D. F. Barbosa, D. L. de Oliveira, T. S. Curtinhas, L. de Abreu Faria, and J. F. D. S. Luciano, “Implementation of locally-clocked XBM state machines on FPGAs using synchronous cAD tools,” IEEE Trans. Circuits Syst. I: Reg. Pap. 64, 1064–1074 (2017).
A. Nahiyan, K. **ao, K. Yang, Y. **, D. Forte, and M. Tehranipoor, “AVFSM: a framework for identifying and mitigating vulnerabilities in FSMs,” in Proceedings of the 53rd ACM/EDAC/IEEE Design Automation Conference DAC, Austin, USA (IEEE, 2016).
E. J. McCluskey, “Reduction of feedback loops in sequential circuits and carry leads in iterative networks,” Inform. Control 6, 99–118 (1963).
I. Pomeranz and K. T. Cheng, “STOIC: state assignment based on output/input functions,” IEEE Trans. Comput Aided Des. 12, 613–622 (1993).
J. Forrest, “ODE: output direct state machine encoding,” in Proceedings of the European Design Automation Conference EURO-DAC’95, Brighton, UK (IEEE, 1995).
V. Solovjev, “Synthesis of sequential circuits on programmable logic devices based on new models of finite state machines,” in Proceedings of the Euromicro Symposium on Digital Systems Design DSD'2001, Warsaw, Poland (IEEE, 2001).
K. Mielcarek, A. Barkalov, and L. Titarenko, “Designing LUT-based mealy FSM with transformation of collections of output functions,” in Proceedings of the 5th International Conference on Modern Circuits and Systems Technologies MOCAST, Thessaloniki, Greece (IEEE, 2016).
A. S. Klimovich and V. V. Solov’ev, “Transformation of a Mealy finite-state machine into a moore finite–state machine by splitting internal states,” J. Comput. Syst. Sci. Int. 49, 900 (2010).
S. Yang, “Logic synthesis and optimization benchmarks user guide, Version 3.0,” Tech. Report (Microelectronics Center of North Carolina, North Carolina, 1991).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © M. Ostapchuk, V.V. Solov’ev, 2018, published in Izvestiya Akademii Nauk, Teoriya i Sistemy Upravleniya, 2018, No. 5.
Rights and permissions
About this article
Cite this article
Ostapchuk, M., Solov’ev, V.V. Minimizing the Finite-State Machines by Using the Values of Input Variables for Coding the Internal States. J. Comput. Syst. Sci. Int. 57, 738–749 (2018). https://doi.org/10.1134/S1064230718050106
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064230718050106