Scientific and Technical Journal


ISSN Print 2221-3937
ISSN Online 2221-3805

The model of finite state machine (FSM) is used in a lot of cases of control unit design. In this article a short review of the control unit models is given. The attention is paid to the model of combined finite state machine (CFSM), which is considered in detail. The main feature of the CFSM model is to combine the Mealy and Moore models, which means the ability to form two corresponding types of output functions in one cycle.

There is some optimization problem connected with CFSM synthesis, and choice of its solution depends on the hardware base of implementation.

The modern hardware platform is represented by chips of programmable logic FPGA and CPLD. CPLD type circuits are popular due to their availability. CPLD, like any other structure, has certain design parameters, so the control algorithms that are implemented on CPLD, can be optimized for these parameters.

The criteria of optimization may be different: reducing the power consumption of the FSM circuit, productivity increasing, etc. The choice of a priority criterion depends on the overall concept and the ultimate goal of the project. In this article we discuss the methods of logic circuit optimization of CFSM type control unit. In our case the main criterion of optimization is the reduction of hardware amount.

The main task of this research is to reduce the hardware amount of combined FSM realization on the CPLD. The architectural features of complex programmable logic device are analyzed. Based on the analysis, the basic model of the implementation of combined finite state machine in CPLD is proposed. The reduction of hardware amount of the CFSM scheme is directly related to the decreasing of terms number in the Boolean functions system describing an automaton. The optimization methods for basic CFSM model are proposed, such as: the method of decreasing the number of optimized terms relative to the output function; the method of decreasing the number of terms relative to the classes of pseudoequivalence; the method of output variables sets encoding.

Studies have been conducted to evaluate the effectiveness of each method. For the each discussed model of CFSM, the states of the automaton have been encoded trivially, a direct structured table and functional systems are developed. The resulting systems are represented by synthesized VHDL constructs and implemented in Altera MAX V chips, as well as Xilinx CoolRunner 2 and XC9500XL.

Based on the results of the study, it is clear that the most optimal combined FSM schemes are implemented in microcircuits Xilinx XC9500XL, and the most effective method is the method of combined FSM synthesis with the output variable sets encoding.


DOI 10.15276/eltecs.28.104.2018.19
  1. Sunggu, Lee. (2005), Advanced Digital Logic Design Using VHDL, State Machines, and Synthesis for FPGA's, Thomson-Engineering, 488 pp.
  2. Czerwinski, R., Kania,D. (2013), Finite State Machine Logic Synthesis for Complex Programmable Logic Devices, Springer Science & Business Media, 172 pp. doi:10.1007/978-3-642-36166-1
  3. Baranov, S. (2008), Logic and System Desing of Digital Systems, TUT Press, Tallinn, 267 pp.
  4. Sklyarov, V., Sklyarova, I., Barkalov, A., Titarenko,L. (2014), Synthesis and Optimization of FPGA-Based Systems, Springer International Publishing, 432 pp. doi: 10.1007/978-3-319-04708-9
  5. Micheli, G. (1994), Synthesis and Optimization of Digital Circuits, Mc Graw-Hill, New York, 636 pp.
  6. Zeleneva, I. J., Hrushko, S.S., Arapin, D.V. (2017), “Experimental study of methods of optimization of hardware costs in the implementation of the Moore control automaton on CPLD” [“Eksperimentalnoe issledovanie metodov optimizatsii apparaturnyih zatrat pri realizatsii upravlyayuschego avtomata Mura na CPLD”]Collection of scientific works "Systems of information processing", Issue 2 (148), Kharkiv,    pp. 34-41
  7. Barkalov, A. A., Matvienko, A.V., Tsololo, S.A. (2008), “Reduction of hardware costs in the Moore FSM circuit using the CPLD basis features” [“Umenshenie apparaturnyih zatrat v sheme avtomata Mura s ispolzovaniem osobennostey bazisa CPLD”], Computer tools, networks and systems, No. 7, pp. 86-94.


  1. Barkalov, А. А., Malcheva R. V., Soldatov K. A. (2012), “Optimization of the Moore FSM scheme realized in the FPGA basis”, Radio Electronics, Computer Science, Control, no. 1 (26), pp. 44-47.
  2. Barkalov, A. A., Titarenko, L. A.,  Zeleneva, I. J., Hrushko, S. S. (2016), “The method of decreasing the number of terms when implementing a scheme of a combined firmware in CPLD basis” [“Metod umensheniya chisla termov pri realizatsii shemyi sovmeschennogo mikroprogrammnogo avtomata v bazise CPLD”] Bulletin of the NTU "KhPI", №49 (1221), pp. 25-31.
  3. Villa, T., Sangiovanni-Vincentelli A. (1990), “NOVA: state assignment of finite state mashines for optimal two-level implementation” IEEE Transactions on CAD of Integrated Circuits and Systems, №9, 34-48 pp. doi: 10.1109/43.59068
  4.  Yang, S., Ciesielski, M. “Optimum and suboptimum algorithms for input encoding and its relationships to logic minimization”, IEEE Transactions on CAD of Integrated Circuits and Systems, №10, 117-131 pp. doi: 10.1109/43.62787
  5. Barkalov, А. А. (1998), “Principles of optimizing the logic circuit of the Moore FSM” [Printsipyi optimizatsii logicheskoy shemyi mikroprogrammnogo avtomata Mura], Cybernetics and system analysis, №1, pp. 65-72.
  6. Barkalov, A., Titarenko, L., Zeleneva, I., Hrushko S. (2017) “Implementing combined FSM with CPLDs”, International Journal of Software Engineering and Computer Systems (IJSECS), Paper 006, Volume 4, Universiti Malaysia Pahang.
  7. Barkalov, A. Titarenko, L., Zeleneva I., Hrushko, S. “Encoding of output signal sets in the scheme of the combined FSM on the CPLD”, In press.
Last download:
17 Aug 2019

[ © KarelWintersky ] [ All articles ] [ All authors ]
[ © Odessa National Polytechnic University, 2014-2018. Any use of information from the site is possible only under the condition that the source link! ]