C&SA | Contents

Volume 60 >>> № 4 JULY — AUGUST 2024

-->

UDC 004.274

A.A. Barkalov¹, L.A. Titarenko², O.M. Golovin³, A.V. Matviienko⁴

¹ University of Zielona Gora, Zielona Gora, Poland

A.Barkalov@iie.uz.zgora.pl

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

L.Titarenko@iie.uz.zgora.pl

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

o.m.golovin.1@gmail.com

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

avmatv@ukr.net

OPTIMIZATION OF MEALY FSM CIRCUIT IN MIXED ELEMENT BASIS

Abstract. A method of reducing LUT count in the FPGA-based circuit of Mealy finite state machine (FSM). A part of the circuit is implemented using embedded memory block (EMB). The method is based on the twofold state assignment and encoding collections of microoperations. An example of the synthesis of FSM circuit using the proposed method is given. When certain conditions are met, there are exactly three levels of logic elements in the FSM circuit. Methods for improving the characteristics of a circuit based on optimal coding of states and collections of microoperations are considered.

Keywords: Mealy FSM, synthesis, FPGA, EMB, LUT, encoding.

full text

REFERENCES

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

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

Kubica M., Opara A., Kania D. Technology mapping for LUT-based FPGA. Cham: Springer, 2021. 207 p. doi.org/10.1007/978-3-030-60488-2 .

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.

BarkalovA., Titarenko L., Mielcarek K., Chmielewski S. Logic synthesis for FPGA-based control units. Lecture Notes in Electrical Egineering. 2020. Vol. 636. 247 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 (6–20 Feb, 2004, Paris, France). 2004. Vol. 2. P. 916–921.

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. Р. 1249–1251.

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.

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 — as cientometric review. Computation. 2019. Vol. 7, Iss. 4. P. 63. doi.org/10.3390/computation7040063 .

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

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.A., Titarenko L.A., Barkalov A.A., Jr. A structural decomposition as a tool for the optimization of an FPGA-based implementation of a Мealy FSM. Cybernetics and Systems Analysis. 2012. Vol. 48, N 2. P. 313–322. doi.org/10.1007/s10559-012-9410-2 .

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

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

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

Glushkov V.M. Synthesis of digital automata. Moscow: Fizmatgiz, 1962. 476 p.

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

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. Р. 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. Р. 718–727.

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

Vivado design suite. 2020. URL: https: //www.xilinx.com/products/design-tools/vivado.html (Acceed: January, 2020).

Quartus II. URL: www.intel.com/content (Acceed: January, 2020).

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.

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

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

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

Barkalov A.A., Titarenko L.A., Baiev A.V., Matviienko A.V. Optimizing the combined automation schemein the asis basis. Cybernetics and Systems Analysis. 2020. Vol. 56, N 6. P. 863–871. doi.org/10.1007/s10559-020-00306-w .

Kryvyi S.L., Opanasenko V.N., Zavyalov S.B. Logical оperations over fuzzy sets and relations in automaton interpretation. Cybernetics and Systems Analysis. 2020. Vol. 56, N 6. P. 1012–1020. doi.org/10.1007/s10559-020-00321-x .