C&SA | Contents

Volume 59 >>> № 1 JANUARY — FEBRUARY 2023

-->

UDC 004.274

Barkalov A.A.¹, Titarenko L.A.², Baev A.V.³, Matviienko A.V⁴

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

A.Barkalov@iie.uz.zgora.pl

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

L.Titarenko@iie.uz.zgora.pl

³ Vasyl’ Stus Donetsk National University,
Vinnytsia, Ukraine

a.baev@donnu.edu.ua

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

avmatv@ukr.net

TWOFOLD STATE ASSIGNMENT FOR MOORE FINITE STATE MACHINES

Abstract. A method is proposed for reducing hardware in circuits of Moore finite-state machines (FSMs) implemented with EMB and LUTs. The method divides a set of states into classes, each corresponding to one block of logical elements. Moreover, each state has two codes. This approach leads to the three-level circuit of the Moore FSM. An example of the Moore FSM synthesis using the proposed method and the application conditions for this method are considered. Studies based on standard benchmark FSMs have shown that the proposed method reduces the hardware amount compared to other known solutions.

Keywords: Moore FSM, synthesis, EMB, LUT, structural decomposition, partition.

full text

REFERENCES

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

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

С Solovyov V.V. Designing digital circuits based on programmable logic integrated circuits [in Russian]. Moscow: Hotline – TELECOM, 2001. 636 p.

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.

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

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

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

Kuon I., Tessier R., Rose J. FPGA аrchitecture: Survey and challenges. Foundations and Trends in Electronic Design Automation. 2008. Vol. 2, N 2. P. 135–253.

Sass R., Schmidt A. Embedded system design with platform FPGAs: Principles and practices. Amsterdam: Morgan Kaufmann Publishers, 2010. 409 p.

Ruiz-Rosero J., Ramirez-Gonzalez G., Khanna R. Field programmable gate array applications — a scientometric review. Computation. 2019. Vol. 7(3). P. 63.

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

Rafla N.I., Gauba I. A reconfigurable pattern matching hardware implementation using on-chip ram-based FSM. 53rd IEEE International Midwest Symposium on Circuits and Systems. 2010. P. 49–52.

Sklyarov V. Synthesis and implementation of RAM-based finite states maсhines in FPGAs. Proc. of Field-Programmable Logic and Applications: The Roadmap to Reconfigurable Computing. Villach: Springer-Verlag, 2000. P. 718–727.

Senhaji-Navarro R., Garcia-Vargas I., Jimenes-Moreno G., Civit-Balcells A., Guerra-Gutierres P. ROM-based FSM implementation using input multiplexing in FPGA devices. Electronics Letters. 2004. Vol. 40, N 20. P. 1249–1251.

Senhaji-Navarro R., Garcia-Vargas I., Guisado L.J. Performance evaluation of RAM-based implementation of finite states machines in FPGAs. 19th IEEE International Conference on Electronics, Circuits, and Systems (ICECS 2012). (Seville, Spain, Dec., 2012). 2012. P. 225–228.

Kubica M., Opara A., Kania D. Technology mapping for LUT- based. FPGA. Berlin: Springer, 2021. P. 216.

Barkalov O., Titarenko L., Barkalov Jr. A structural decomposition as a tool for the optimization of an FPGA–based implementation of a Mealy FSM. Cybernetics and Systems Analysis. 2012. Vol. 48, N 2. P. 313–322.

Barkalov A.A., Titarenko L.A., Baiev A.V., Matviienko A.V. Joint use of methods of structural decomposition for optimizing the circuit of moore FSM. Cybernetics and Systems Analysis. 2021. Vol. 57, N 2. P. 173–184.

Barkalov A., Titarenko L., Mielcarek K. Hardware reduction for LUT-based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2018. Vol. 28, N 3. Р. 595–607.

Barkalov A., Titarenko L., Mielcarek K. Improving characteristics of LUT-based Mealy FSMs. International Journal of Applied Mathematics and Computer Science. 2020. Vol. 30, N 3. P. 745–759.

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

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

Glushkov V.M. Synthesis of digital automata [in Russian]. Moscow: Fizmatgiz, 1962. 476 p.

Intel® FPGAs and Programmable Devices. URL: https://www.intel.com/content/www/us/en/products/programmable.html .

VC709 Evaluation Board for the Virtex-7 FPGA. User Guide; UG887 (v1.6); Xilinx, Inc.: San Jose, CA, USA, 2019.

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

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, N 6–7. P. 424–434.

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

Machado L., Cortadella 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.

Wilkes M., Stringer J. Microprogramming and the design of the control circuits in electronic digital computer. Proc. of Cambridge Philosofical Society. 1953. Vol. 49. P. 230–238.

Achasova S.M. Algorithms for the synthesis of automata on programmable matrices [in Russian]. Moscow: Radio i svyaz', 1987. 136 p.

Barkalov A., Titarenko L., Mielcarek K., Chmielewski S. Logic synthesis for FPGA-based control units. Structural Decomposition in Logic Design. Lecture Notes in Electrical Egineering. Springer, 2020. Vol. 636. P. 247.

Vivado Design Suite. URL: https://www.xilinx.com/products/design-tools/vivado.html.

Quartus II. URL: https//www.intel.com/content/www/us/en/software/programmable/quartus-prime/overview.html .

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. Lecture Notes in Electrical Engineering. Berlin: Springer, 2011. Vol. 79. P. 121–144.

Barkalov A.A., Titarenko L.A. Transformation of codes in composite microprogram control devices. Kibernetika i sistemnyj analiz. 2011. N 5. P. 107–118.

Barkalov A.A., Titarenko L.A., Efimenko K.N. Optimization of circuits of composite microprogram control devices. Kibernetika i sistemnyj analiz. 2011. N 1. P. 179–188.

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