Parametrization of graph-schemes of algorithms for digital control units
DOI:
https://doi.org/10.31558/2786-9482.2024.2.1Keywords:
graph-scheme of algorithm, digital control units, circuit optimization, parameters, pseudo-random generationAbstract
The paper considers the scientific and practical problem of determining the set of parameters of graphschemes of algorithms in the context of further pseudo-random generation of graph-schemes in order to study the effectiveness of methods for synthesizing and optimization of digital control units. Structural components are considered and general parameters of graph-schemes of algorithms are determined, which are traditionally used to describe algorithms for digital control units. The main classes of digital control units are analyzed, such as microprogram finite state machine (automated state machine with hardware logic implementation), microprogram control unit (automated state machine with programmable logic) and compositional microprogram control unit. For these classes, the main methods of optimizing hardware expenses are considered, including encoding sets of microoperations, replacing input variables, operational transformation of state codes, etc. For each of the considered classes of control units and optimization methods, sets of graph-schemes of algorithms parameters are proposed, which affect the effectiveness of applying the corresponding structures and methods and characterize both the transition function and the function of the outputs of control unit. For individual parameters, the permissible range of changes, correlation or mutual exclusivity with other parameters of graph-schemes are determined. Illustrative examples of determining individual parameters for a given graph-scheme are given. Recommendations are given on the use of the proposed parameters for pseudo-andom generation of graph-schemes of algorithms. General requirements for correct pseudo-random generation of graph-schemes of algorithms are determined. Such requirements are: the possibility of reaching the final node from any other node; the absence of nodes whose input is not connected with the output of another node; the absence of repetition of logical conditions in consecutive conditional nodes; the presence of at least one operational node, etc.
References
Bailliul, J., Samad, T. (2015). Encyclopedia of Systems and Control. Springer: London, UK, 1554 p. https://doi.org/10.1007/978-1-4471-5058-9
Suh, S. C., Tanik, U. J., & Carbone, J. N. (2013). Applied Cyber-Physical Systems. New York, USA: Springer, 253 p. https://doi.org/10.1007/978-1-4614-7336-7
Kam, T., Villa, T., Brayton, R., & Sangiovanni-Vincentelli, A. (1997). A Synthesis of Finite State Machines: Functional Optimization. Boston, MA, USA: Springer, 282 p. https://doi.org/10.1007/978-1-4757-2622-0
Baranov, S. (1994). Logic Synthesis for Control Automata. Dordrecht: Kluwer Academic Publishers, 312 p.
Hartmanis, J., Stearns, R. E. (1966). Algebraic Structure Theory of Sequential Machines. New Jersey: Prentice-Hall, 211 p.
Czerwinski, R., Kania, D. (2013). Finite State Machine Logic Synthesis for Complex Programmable Logic Devices. Berlin: Springer, 172 p. https://doi.org/10.1007/978-3-642-36166-1
Sklyarova, I., Sklyarov, V., & Sudnitson, A. (2012). Design of FPGA-based Circuits using Hierarchical Finite State Machines. Tallin: TUT Press, 240 p.
Nelson, V., Nagle, H., Irwin, J., & Carroll, B. (1995). Digital logic circuit analysis and design. New Jersey: Prentice Hall, 842 p.
DeMicheli, G. (1994). Synthesis and Optimization of Digital Circuits. NY: McGraw-Hill, 576 p.
Baranov, S. (2008). Logic and System Design of Digital Systems. TUTPress: Tallinn, Estonia, 267 p.
Scholl, C. (2001). Functional Decomposition with Application to FPGA Synthesis. Boston, MA, USA: Kluwer Academic, 264 p. https://doi.org/10.1007/978-1-4757-3393-8
Barkalov, A. A., Titarenko, L. A., Babakov, R. M., & Baiev, A. V. (2016). Logic synthesis for FPGA-based finite state machines: monograph. Vinnytsia: DonNU Vasyl' Stus, 195 p.
Baranov, S. (2018). Finite State Machines and Algorithmic State Machines. Seattle, WA, USA: Amazon, 185 p.
Yang, S. (1991). Logic synthesis and optimization benchmarks User Guide Version 3.0. Tech. rep. Microelectronics Center of North Carolina, P. O. Box 12889, Research Triangle Park, NC 27709.
Minns, P., Elliot, I. (2008). FSM-Based Digital Design Using Verilog HDL. New Jersey: J. Wiley & Sons, 408 p.
Barkalov, A., Titerenko, L. (2009). Logic synthesis for FSM-based control units. Berlin: Springer, 233 p.
Barkalov, A., Wegrzyn, M. (2006). Design of control units with programmable logic. Zielona Gora: University of Zielona Gуra Press, 150 p.
Barkalov, A., Titerenko, L. (2008). Logic synthesis for compositional microprogram control units. Berlin: Springer, 272 p.
Babakov, R. M. (2019). Development and Hardware Optimization of Control Units for IOT Devices in Industry Systems. Internet of Things for Industry and Human Applications. Vol. 1. Assessment and Implementation / V. S. Kharchenko (ed.). Ministry of Education and Science of Ukraine, National Aerospace University KhAI, p. 834–865.
Barkalov, A. A., Titarenko, L. A., & Babakov, R. M. (2023). Synthesis of VHDL-Model of a Finite State Machine with Datapath of Transitions. Radio Electronics, Computer Science, Control. Volume 4, p. 135–147. https://doi.org/10.15588/1607-3274-2023-4-13
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
