Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
Volume 57 >>> № 2 MARCH — APRIL 2021
-->

UDC 004.274
A.A. Barkalov1, L.A. Titarenko2, A.V. Baiev3, A.V. Matviienko4


1 University of Zielona Gora, Zielona Gora, Poland, and
Vasyl’ Stus Donetsk National University, Vinnytsia, Ukraine

 A.Barkalov@iie.uz.zgora.pl

2 University of Zielona Gora, Zielona Gora, Poland, and
Kharkiv National University of Radio Electronics, Kharkiv, Ukraine

 L.Titarenko@iie.uz.zgora.pl

3 Vasyl’ Stus Donetsk National University and Peoly, LLC,
Vinnytsia, Ukraine

 a.baev@donnu.edu.ua

4 V.M. Glushkov Institute of Cybernetics, National Academy
of Sciences of Ukraine, Kyiv, Ukraine

 avmatv@ukr.net

JOINT USING METHODS OF STRUCTURAL DECOMPOSITION
FOR OPTIMIZING CIRCUIT OF MOORE FSM

Abstract. A method is proposed for optimizing hardware amount in the circuit of Moore FSM implemented with FPGA. The method is based on joint using replacement of inputs and transformation of state codes into codes of classes of pseudoequivalent states. This approach leads to a three-level circuit of FSM. There is shown an example of synthesis of Moore FSM with application of the proposed method. Analysis of positive and negative features of the proposed method is conducted. The researches on the base of standard benchmark FSM show that the proposed method allows reducing hardware amount and consumed power with insignificant degradation of FSM performance.

Keywords: Moore FSM, synthesis, FPGA, LUT, structural decomposition.



FULL TEXT

REFERENCES

  1. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p.

  2. Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and optimization of FPGA-based systems. Berlin: Springer, 2014. 432 p.

  3. Barkalov A., Titarenko L., Mazurkiewicz M. Foundations of еmbedded systems. Springer Nature Switzerland, 2019. 180 р.

  4. Marwedel P. Embedded systemdesign: Embedded systems, foundations of cyber-physical systems and the Internet of things. Berlin: Springer, 2018. 423 p.

  5. Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Berlin: Springer, 2013. 172 p.

  6. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.

  7. Barkalov A.A., Titarenko L.A., Baiev A.V., Matviienko A.V. Mixed Encoding of Collections of Microoperations for a Microprogram Finite-State Machine. Kibernetika i sistemnyj analiz. 2020. Vol. 56, N 3. P. 3–16.

  8. Soloviev V.V. Design of digital circuits based on programmable logic integrated circuits [in Russian]. Moscow: Goryachaya liniya - TELECOM, 2001. 636 p.

  9. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state machines. Tallinn: TUT Press, 2012. 240 p.

  10. Machado L., Cjrtadella J. Support - reducing decomposition for FPGA mapping. IEEE Transactions on Computer — Aided Design of Integrated Circuits and Systems. 2020. Vol. 39, N 1. P. 213–224.

  11. Barkalov A., Titarenko L. Logic synthesis for FSM-based control units. Berlin: Springer, 2009. 233 p.

  12. Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier, 2008. 784 p.

  13. Barkalov A., Titarenko L., Mielcatek K., Chmielewski S. Logic synthesis for FPGA-based control units: Structural decomposition in Logic design. Berlin: Springer, 2020. 247 p.

  14. Grushnitsky R.I., Mursaev A.Kh., Ugryumov E.P. Designing systems using programmable logic chips [in Russian]. SPb: BHV-Petersburg, 2002. 608 p.

  15. Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press, 2004. 542 p.

  16. Barkalov A. A., Titarenko L.A. Code conversion in compositional microprogram control units. Kibernetika i sistemnyj analiz. 2011. N 5. P. 107–118.

  17. Kubica M., Kania D. Area-oriented technology mapping for LUT-based logic blocks. Int. Journal of Applied Mathematics and Computer Science. 2017. Vol. 27, N 1. P. 207–222.

  18. Kolopienczyk M., Titarenko L., Barkalov A. Design of EMB-based Moore FSMs. Journal of Circuits, Systems and Computers. 2017. Vol. 21, N 7. P. 1–23.

  19. Tiwari A., Tomko K. Saving power by mapping finite state machines into embedded memory blocks in FPGAs. Proc. Design, Automation and Test in Europe Conference and Exhibition (Paris, France, 6–20 Feb. 2004). 2004. Vol. 2. P. 916–921.

  20. White paper FPGA architecture. URL: www.altera.com.

  21. UG473 (v1.14) July 3, 2019. URL: www.xilinx.com.

  22. Rawski M., Tomaszewicz P., Borowski G., Luba T. Logic synthesis method of digital circuits designed for implementation with embedded memory blocks on FPGAs. Design of Digital Systems and Devises. Adamski M., Barkalov A., Wegrzyn M. (Eds.). Lecture Notes in Electrical Engineering. Vol. 79. Berlin: Springer, 2011. P. 121–144.

  23. Rawski M., Selvaraj H., Luba T. An application of functional decomposition in ROM-based FSM implementation in FPGA devices. Journal of System Architecture. 2005. Vol. 51, Iss. 6–7. P. 424–434.

  24. Nowicka M., Luba T., Rawski M. FPGA-based decomposition of boolean functions: Algorithms and implementations. Proc. of the 6th International Conference on Advanced Computer Systems (Szczecin, 1999). P. 502–509.

  25. Barkalov A., Titarenko L., Chmielewski S. Mixed encoding of collections of output variables for LUT-based FSMs. Journal of Circuits, Systems and Computers. 2019. Vol. 28, N 8. P. 1–21.

  26. Garcia-Vargas I., Senhadji-Navarro R., JimБnez-Moreno G., Civit-Balcells A., Guerra-Gutierrezz P. ROM-based finite state machines implementation in low cost FPGAs. IEEE Intern. Simp. on Industrial Electronics (ISIE’07) (Vigo, 2007). 2007. P. 2342–2347.

  27. Garcia-Vargas L., Senhaji-Navarro R. Finite state machines with input multiplexing: A performance study. IEEE Transactions on CAD of Integrated Circuits and Systems. 2015. Vol. 34, Iss. 5. P. 867–871.

  28. Barkalov A.A., Titarenko L.A., Efimenko K.N. Optimization of circuits of compositional microprogram control units implemented on FPGA. Kibernetika i sistemnyj analiz. 2011. N 1. P. 179–188.

  29. ABC System (n.d.). URL: https://people.eecs.berkeley.edu/~alanmi/abc/. Accessed: January, 2020.

  30. Sentowich E.M., Singh K.J., Lavango L., Moon C., Murgai R., Saldanha A., Savoj H., Stephan P.R., Bryton R.K., Sanjiovanni-Vincentelli A. SIS: A system for sequential circuit synthesis. Technical Report. Berkely: University of California, 1992.

  31. Michalski T., Kokosinski Z. Functional decomposition of combionational logic circuits with PKmin, Technical Transactions. Electrical Engeneering = Czasopismo Technicze. Elektrotechnika (Iss 2-E). 2016. P. 191–202.

  32. DEMAIN. URL: www.zpt.tele.pw.edu.pl/oprogramowanie/demain.html.

  33. Vivado (2020). URL: https://www.xilinx.com/design sub tools/vivado.html. Accessed January, 2020.

  34. QuartusII (2020). URL: https://www.intel.com/content/www/us/en/programmable/downloads/software/ quartus-ii-we/121.html. Accessed January, 2020.

  35. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.

  36. Xilinx (2020). Virtex-5 Family Overview, PDF, Xilinx Corporation. URL: https://www.xilinx.com/ support/documentation/data sub sheets/ds100.pdf/.

  37. Palagin A.V., Opanasenko V.N., Kryvyi S.L. Resource and energy optimization oriented development of FPGA-based adaptive logical networks for classification problem. Green IT Engineering: Components, Networks and Systems Implementation. 2017. Vol. 105. P. 195–218. DOI: 10.1007 978-3-319-55595-9_10.

  38. Opanasenko V.N., Kryvyi S.L. Synthesis of neural-like networks on the basis of conversion of cyclic Hamming codes. Cybernetics and Systems Analysis. 2017. Vol. 53, N 4. P. 627–635. https://doi.org/10.1007/s10559-017-9965-z.




Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2021 Kibernetika.org. All rights reserved.