METHOD OF REDUCING THE NUMBER OF LUT ELEMENTS IN THE CIRCUIT OF MOORE FSM
DOI:
https://doi.org/10.18372/2310-5461.53.16402Keywords:
Moore FSM, synthesis, FPGA, EMB, LUT, pseudo equivalent statesAbstract
In state-of-art digital systems the control device, which usually has a sequential structure, is one of the most important units. Moore finite state machine (FSM) is often used to implement such schemes. While implementing a digital system based on FPGA chips at the design stage of the FSM circuit there is a problem of optimizing the characteristics of its circuit. These characteristics include hardware costs (semiconductor element area occupied by the FSM circuit), speed, and power consumption. Methods of solving this problem depend on the features of the FSM and the circuitry. The features of the Moore FSM are 1) the presence of classes of pseudo-equivalent states and 2) the absence of direct dependence of outputs on inputs. Features of FPGA are: 1) the presence of embedded memory blocks EMB, that can be configured, and 2) a very limited number of inputs of the table type LUT (look-up table).
This work aims to develop a method for reducing the number of tabular elements in the circuit of Moore FSM, taking into account both the features of the Moore FSM and the circuitry on which the implementation of the digital system control device is realized.
A method for optimizing the cost of equipment in the circuit of the Moore FSM, which is implemented on a mixed basis of LUT and EMB elements, is proposed. The method is based on the use of classes of pseudo-equivalent states of the Moore FSM and it is advisable to use it if the developer of the circuit of the control device can use only a limited number of EMB blocks. It is proposed to present the state code in the form of a concatenation of state class codes and element codes of these classes. Such an approach reduces requirements for the number of EMB inputs. The conditions of application of the proposed method are shown. An example of the synthesis of the circuit of the FSM using the proposed method is given.
References
ЛІТЕРАТУРА
Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p. DOI: 10.1007/978-1-4615-2692-6_6
DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state machines. Tallinn: TUT Press, 2012. 240 p.
Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and optimization of FPGA-based systems. Berlin: Springer, 2014. 432 p. DOI: 10.1007/978-3-319-04708-9
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.
Kubica M., Opara A., Kania D. Technology Mapping for LUT- based. FPGA. Berlin: Springer, 2021 DOI: 10.1007/978-3-030-60488-2_1
Глушков В. М. Cинтез цифровых автоматов. – М.: Физматгиз, 1962 – 476 с.
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 System Analysis 2021, Vol. 57, No 2, pp. 173–184.
UG473 (v1.14) July 3, 2019. URL: www.xilinx.com.
Intel® FPGAs and Programmable Devices. https://www.intel.com/content/www/us/en/products/programmable.html
Kuon I., Tessier R., Rose J. FPGA Architecture: Survey and Challenges. Foundations and Trends in Electronic Design Automation. 2008. vol. 2. no. 2. pp. 135–253. DOI:10.1561/1000000005
Sass R., Schmidt A. Embedded System Design with platform FPGAs: Principles and Practices. - Amsterdam: Morgan Kaufmann Publishers, 2010 - 409 pp.
Barkalov A., Titarenko L., Mielcarek K. Improving characteristics of LUT–based Mealy FSMs. International Journal of Applied Mathematics and Computer Science, 2020, 30(4), pp. 745 – 759.
VC709 Evaluation Board for the Virtex-7 FPGA. User Guide; UG887 (v1.6); Xilinx, Inc.: San Jose, CA, USA, 2019.
Vivado Design Suite. https://www.xilinx.com/products/design-tools/vivado.html,2020, accede: January 2020
Quartus II, ://www.intel.com/content/www/us/en/software/programmable/quartus-prime/overview.html, acceded: January 2020.
Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep. Microelectronics Center of North Carolina, 1991. 43 p.
Barkalov A., Titarenko L., Mielcarek K., Chmielewski S. Logic Synthesis for FPGA–Based Control Units. – Structural Decomposition in Logic Design. vol. 636 of Lecture Notes in Electrical Engineering. Springer,2020.
