Control Systems and Computers

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

Upr. sist. maš., 2016, Issue 6 (266), pp. 34-39.

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.

An Optimal State Assignment for the Combined Automation

Introduction. An offer in-process method allows to decrease the number of EMB blocks and LUT elements in the chart of the combined microprogram automat. It is arrived at due to the corresponding encryption of the states. Thus, the optimal encryption of the states is primery, allowing to decrease the number of address entrances of EMB. The optimization of LUT block is needed at violation of corresponding terms. The codes of the states can be changed without the change of code of class of K (Bi ). The codes of the states have got the specified features.

Purpose. The analysis of the used library showed that this method allows to get charts with one block of EMB for 82% of all examples. Thus, corresponding condition is violated in 46% of all examples. Transposition of the codes of the state allows to decrease the number of LUT elements for 60% of these examples.

Conclusion.  Further direction of researches is related to adaptation of the new features of the combined automat. It allows to decrease the number of LUT elements in the block of replacement of the logical terms as compared to  the well-known replacement methods.

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. – New York: McGraw-Hill, 636 p.
3. Solovyev, V.V., 2001. Proyektirovaniye tsifrovykh skhem na osnove programmiruyemykh logicheskikh integral’nykh skhem. M.: TELEKOM, 636 p. (In Russian).
4. Skliyarova, I.,  Sklyarov, V.,  Sudnitson, A., 2012.  Design of FPGA–based circuits using Hierarchical Finite State Machines. Tallinn: TUT Press, 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. (In Russian).
6. V. Sklyarov, I. Skliarova, A. Barkalov et al., 2014. Synthesis and Optimization of FPGA-based Systems. Berlin: Springer, 432 p.
   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. L. Garcia–Vargas, R. Senhadji–Navarro, M. Civit–Balcells A. et al., 2007. ROM–Based Finite State Machine Implementation in Low Cost FPGAs. IEEE Int. Simp. on Industrial Electronics. Vigo, pp. 2342–2347.
9. Nowicka, M., Luba, T., Rawski, V., 1999. FPGA–based decomposition of boolean functions: algorithms and implementations. Advanced Computer Systems, 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.  M. Rawski, P. Tomaszewicz, G. Borowski et al., 2011. 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. (In Russian). A.A. Barkalov, YA.Ye. Vizor, A.V. Matviyenko et. al., 2016. Realizatsiya skhemy sovmeshchennogo avtomata v bazise FPGA. Kompyuterni zasoby, merezhi ta systemy: Zb. naukovykh prats. Instytut kibernetyky im. V.M. Hlushkova NAN Ukrayiny. K., 15, pp. 32–40. (In Russian).
15. Barkalov, A.,  Titarenko, L.,  Kolopenczyk, M., 2013. EMB-based design of Mealy FSM. Proc. of 12th IFAC Conf. on programmable devices and embedded syst., pp. 215–220.

Received 09.04.2016