Abstract
Digital systems based on programmable logic devices and systems on chip often use register buffers for the transmission of signals between functional units. In this paper, structural models of finite state machines (FSMs) that allow the use of input and output buffer triggers as memory elements of the finite state machine are considered. To this end, a new classification of structural models of finite state machines is proposed in which all finite state machines are divided into six classes A, B, C, D, E, and F. In the models C and D, output buffer triggers are used as memory elements; in the models E and F, input buffer triggers are used for this purpose. A definition of the set of internal states of FSMs in each class is given and synthesis methods for the FSMs of the classes C-F are proposed. The results of experiments showed that the use of FSM models of the classes C-F reduces the number of internal memory elements by 2.22% to 25.83% on the average and sometimes even by 100%.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
G. H. Mealy, “Method for synthesizing sequential circuits,” Bell Syst. Tech. J. 34, 1045–1079 (1955).
E. F. Moore, “Gedanken-experiments on sequential machines,” in Automata Studies, Ed. by C. Shannon and J. McCarthy (Princeton Univ. Press, Princeton, 1956), pp. 129–153.
L. D. Coraor, P. T. Hulina, and O. A. Morean, “A general model for memory-based finite-state machines,” IEEE Trans. on Computers C-36, 175–184 (1987).
R. Senhadji-Navarro, I. Garcia-Vargas, and J. L. Guisado, “Performance evaluation of RAM-based implementation of finite state machines in FPGAs,” Proc. of the 19th IEEE Int. Conf. on Electronics, Circuits and Systems (ICECS), Seville, Spain, 2012, pp. 225–228.
V. Sklyarov, “Hierarchical finite-state machines and their use for digital control,” IEEE Trans. Very Large Scale Integration Syst. 7, 222–228 (1999).
V. Sklyarov and I. Skliarova, “Synthesis of parallel hierarchical finite state machines,” in Proc. of the 21st Iranian Conf. of Electrical Engineering (ICEE), Mashhad, Iran, 2013, pp. 1–8.
A. Barkalov, L. Titarenko, and S. Chmielewski, “Reduction in the number of PAL macrocells in the circuit of a Moore FSM,” Int. J. Appl. Math. Comput. Sci. 17, 565–575 (2007).
A. Barkalov, L. Titarenko, and J. Bieganowski, “Reduction in the number of LUT elements for control units with code sharing,” Int. J. Appl. Math. Comput. Sci. 20, 751–761 (2010).
A. Barkalov, L. Titarenko, R. V. Malhava, and K. A. Soldatov, “Hardware reduction in FPGA-based Moore FSM,” J. Circuits, Syst. Comput. 22(3), 1–20 (2013).
V. Sklyarov, “FPGA-based implementation of recursive algorithms,” Microprocessors and Microsystems, Special Issue on FPGAS: Applications and Designs 28(5–6), 197–211 (2004).
S. Ninos and A. Dollas, “Modeling recursion data structures for FPGA-based implementation,” in Proc. of the Int. Conf. on Field Programmable Logic and Applications (FPL), Heidelberg, Germany, 2008, pp. 11–16.
D. Mihhailov, V. Sklyarov, I. Skliarova, and A. Sudnitson, “Hardware implementation of recursive algorithms,” in Proc. of the 53rd IEEE Int. Midwest Symposium on Circuits and Systems (MWSCAS), Seattle, 2010, pp. 225–228.
M.-D. Shieh, C.-L. Wey, and P. D. Fisher, “Model of asynchronous finite state machines and their pipelined structures,” Proc. of the 35th Midwest Symposium on Circuits and Systems, Washington, 1992, Vol. 1, pp. 659–662.
M. Koster and J. Teich, “(Self-)reconfigurable finite state machines: theory and implementation,” in Proc. of the Design, Automation and Test in Europe Conference and Exhibition (DATE 2002), Paris, 2002, pp. 559–566.
P. P. Chu, FPGA Prototyping by VHDL Examples (Wiley-InterScience, Hoboken, USA, 2008).
I. Pomeranz and K.-T. Cheng. “STOIC: state assignment based on output/input functions,” IEEE Trans. on CAD 12, 613–622 (1993).
J. Forrest, “ODE: output direct state machine encoding,” in Proc. of the European Design Automation Conference (EURO-DAC’95), Brighton, Great Britain, 1995, pp. 600–605.
S. Mitra, L. J. Avra, and E. J. McCluskey, “An output encoding problem and a solution technique,” IEEE Trans. on CAD 18, 761–768 (1999).
V. Solovjev and M. Chyzy, “Models of the finite state machines,” in Proc. of the Sixth Int. Conf. on Methods and Models in Automation and Robotics (MMAR 2000), Miedzyzdroje, Poland, 2000, Vol. 2, pp. 909–914.
V. V. Solov’ev, Designing Digital Systems Based on Programmable Logic Devices (Goryachaya liniya-Telekom, Moscow, 2001) [in Russian].
V. Solov’ev, “Synthesis of sequential circuits on programmable logic devices based on new models of finite state machines,” in Proc. of the EUROMICRO Symp. on Digital Systems Design (DSD’2001), Poland, Warsaw, 2001, pp. 170–173.
A. Klimowicz and Solovjev, “Synthesis of sequential circuits on programmable logic devices based on common model of finite state machine,” in Proc. of East-West Design & Test Conference (EWDTC’03), Alushta, Ukraine, 2003, pp. 136–139.
V. V. Solov’ev and A. Klimowicz, Logical Design of Digital Systems Based on Programmable Logic Devices (Goryachaya liniya-Telekom, Moscow, 2008) [in Russian].
A. Klimowicz and V. Salauyou, “The synthesis of combined Mealy and Moore machines structural model using values of output variables as codes of states,” in Proc. of the 15th EUROMOCRO Symp. on Digital System Design (DSD 2012), Izmir, Turkey, 2012, pp. 789–794.
V. V. Solov’ev, “Implementation of finite-state machines based on programmable logic ICs with the help of the merged model of Mealy and Moore machines,” J. Commun. Technol. Electron. 58, 172–177 (2013).
Programmable Logic (Intel, Santa Clara, 1994).
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–908 (2010).
S. Yang, “Logic synthesis and optimization benchmarks user guide. Version 3.0, Technical Report of the Microelectronics Center of North Carolina (1991).
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © A.S. Klimowicz, V.V. Solov’ev, 2015, published in Izvestiya Akademii Nauk. Teoriya i Sistemy Upravleniya, 2015, No. 2, pp. 68–80.
Rights and permissions
About this article
Cite this article
Klimowicz, A.S., Solov’ev, V.V. Structural models of finite-state machines for their implementation on programmable logic devices and systems on chip. J. Comput. Syst. Sci. Int. 54, 230–242 (2015). https://doi.org/10.1134/S1064230715010074
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1064230715010074