Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.03.016

Upr. sist. maš., 2016, Issue 3 (263), pp. 16-22.

UDC 004.274

Barkalov A.A., Doctor (Eng.),Institute of Computer Engineering and Electronics, Institute of Informatics and Electronics Zielenogorski University, ul. Podgorna, 50, Zielona Gora, 65-246, POLAND, a.barkalv@imei.uz.zgora.pl,

Titarenko L.A., Doctor (Eng.), Professor, Institute of Computer Engineering and Electronics, Institute of Informatics and Electronics Zielenogorski University, ul. Podgorna, 50, Zielona Gora, 65-246, POLAND,

Vizor Y.E., PhD (Eng.), +38 (044) 526-25-04, V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 03187, Glushkov ave., 40, Ukraine, E-mail: yaviz@ukr.net,

Matvienko A.V., Researcher Associate, V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 03187, Glushkov ave., 40, Ukraine, +38 (044) 526-30-69, E-mail: matv@online.ua.

Gorina V.V., Assistant, Aircraft control systems Department, National Aviation University, Kyiv, Ukraine

Synthesis of Combined Finite State Machine with FPGAs

Introduction. A method for synthesis of combined finite state machine (CFSM) with FPGA is proposed. An analysis of CFSM’s peculiarities is given. The main feature of CFSM is an existence of two types of the output signals. Mealy outputs depend on the both inputs and states. Moore outputs depend only on the states. The known methods of CFSM design and conditions for their application and the method of the logical conditions replacement is thoroughly analyzed.

Methods. It allows using embedded memory locks (EMB) for implementing some part of CFSM circuit. It is shown that the situations are possible when not all address inputs of an EMB are used. The suggested method is based on using these free address inputs. It is proposed to connect a part of logical conditions with unused address inputs of EMB blocks. It allows diminishing for the number of look-up table (LUT) elements in the circuit of logical conditions replacement in comparison with known methods of CFSM design.

Results. It is proposed to replace some part of the logical conditions set by additional variables. A design method based on such partial replacement is proposed. The method allows obtaining a CFSM circuit with the minimum number of table elements LUTs and memory blocks EMBs. Some additional optimization are possible for the replacement block of the logical conditions due to a special state assignment.

The main idea of the special state assignment is reduced the assignment neighbor codes for states with transitions depending on the same logical conditions. It allows diminishing the number of the literals in functions implemented of the block of the logical conditions replacement. An example of the studied method application is shown.  

Conclusion. The proposed method allows obtaining a circuit required minimum chip space and consuming minimum power in comparison with the known design methods. The conducted researches are based on some library of standard GSAs. The investigations show that for the majority of standard GSAs the proposed method produces the circuits with a single EMB.

Download full text! (In Russian).

Keywords: combined FSM, FPGA, LUT, EMB, synthesis, graph-scheme of algorithm.

1. Baranov, S., 1994. Logic Synthesis for Control Automata. Dordrecht: Kluwer Acad. Publ., 312 p.
   https://doi.org/10.1007/978-1-4615-2692-6
2. DeMicheli, G., 1994. Synthesis and Optimization of Digital Circuits. N.Y.: McGraw-Hill, 636 p.
3. Solov’yev, V.V., 2001. Proyektirovaniye tsifrovykh skhem na osnove programmiruyemykh logicheskikh integral’nykh skhem. M.: Goryachaya liniya – TELEKOM, 636 p.
4. Skliarova, I., Sklyarov, V., Sudnitson, A., 2012. Design of FPGA-based circuits using Hierarchical Finite State Machines. Tallinn: TUT Press, 2012. 240 p.
5. Grushnitskiy, R.I., Mursayev, A.KH., Ugryumov, Ye.P., 2002. Proyektirovaniye sistem s ispol’zovaniyem mikroskhem programmiruyemoy logiki. SPb: BKHV. Peterburg, 608 p.
6. Sklyarov, V., Skliarova, I., Barkalov A. et al., 2014. Synthesis and Optimization of FPGA-based Systems. Berlin: Springer, 432p.
   https://doi.org/10.1007/978-3-319-04708-9
7. Cong, J., Yan, K., 2000. Synthesis for FPGAs with Embedded Memory Blocks. Proc. of the 2000 ACM/SIGDA 8th Int. Symp. on FPGAs, pp. 75–82.
   https://doi.org/10.1145/329166.329183
8. Garcia–Vargas, L., Senhadji–Navarro, R., Civit–Balcells M. et al., 2007. ROM-Based Finite State Machine Implementation in Low Cost FPGAs. IEEE Int. Simp. on Industrial Electronics, Vigo, pp. 2342–2347.
   https://doi.org/10.1109/ISIE.2007.4374972
9. Nowicka, M., Luba, T., Rawski, V., 1999. “FPGA-based decomposition of boolean functions: algorithms and implementations”. Advanced Comp. Syst., pp. 502–509.
10. Rawski, M., Selvaraj, H., Luba, T., 2005. “An application of functional decomposition in ROM-based FSM implementation in FPGA devices”. J. of System Architecture, 51(6–7), pp. 424–434.
    https://doi.org/10.1016/j.sysarc.2004.07.004
11. Rawski, M., Tomaszewicz, P., Borowski G. et al., 2005. “Logic Synthesis Method of Digital Circuits Designed for Implementation with Embedded Memory Blocks on FPGAs”. Design of Digital Systems and Devises. LNEE 70. Berlin: Springer, pp. 121–144.
12. Tiwari, A., Tomko, K., 2004. “Saving power by mapping finite state machines into embedded memory blocks in FPGAs”. Proc. of Design Automation and Test in Europe, 2, pp. 916–921.
    https://doi.org/10.1109/DATE.2004.1269007
13. Yang, S., 1991. Logic Synthesis and optimization benchmarks user guide. Microelectronics Center of North Carolina, 43 p.
14. Barkalov, A.A., 1998. “Printsipy optimizatsii logicheskoy skhemy mikroprogrammnogo avtomata Mura”. Kibernetika i sistemnyy analiz, 1, pp. 65–72.
15. Barkalov, A., Titarenko, L., Kolopenczyk, M., 2013. “EMB-based design of Mealy FSM”. 12th IFAC Conf. on programmable devices and embedded systems, pp. 215–220.
    https://doi.org/10.3182/20130925-3-CZ-3023.00012

Received 13.05.2016