ГлавнаяАрхивDecomposition of a parallel automaton into a net of sequential automata

Decomposition of a parallel automaton into a net of sequential automata | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/2

Описан способ построения сети из последовательных автоматов, реализующей заданный параллельный автомат. При декомпозиции используется отношение параллельности частичных состояний заданного параллельного автомата. Множество состояний каждого из компонентных последовательных автоматов образуется на основе множества взаимно непараллельных частичных состояний заданного параллельного автомата. Кодирование состояний компонентного автомата предусматривает уменьшение энергопотребления проектируемого устройства на основе снижения интенсивности переключений элементов памяти. При совместном энергосберегающем кодировании состояний компонентных автоматов учитывается условная совместимость состояний. Компонентные автоматы обмениваются двоичными сигналами. Число межкомпонентных связей минимизируется.
  • Title Decomposition of a parallel automaton into a net of sequential automata
  • Headline Decomposition of a parallel automaton into a net of sequential automata
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 70
  • Date:
  • DOI 10.17223/20710410/70/2
Ключевые слова
параллельный автомат, частичное состояние, декомпозиция автоматов, энергосберегающее кодирование состояний автоматов, задача взвешенного покрытия
Авторы
Ссылки
Zakrevskiy A. D. Parallel’nye Algoritmv Logicheskogo Upravleniva [Parallel Algorithms for Logical Control], Moscow, URSS, 2003, 304p. (in Russian).
Peterson J. L. Petri Net Theory and the Modeling of Systems. Englewood Cliffs, N.J., Prentice-Hall Inc., 1981.
Piguet C. Low-power and low-voltage CMOS digital design. Microelectronic Eng., 1997, vol.39, no. 1-4, pp. 179-208.
Muroga S. VLSI System Design. When and How to Design Verv-Large-Scale Integrated Circuits. N.Y., John Wiley к Sons, 1982.
Pedram M. Power minimization in IC design: Principles and applications. ACM Trans. Design Automat. Electron. Svst., 1996, vol. 6, pp.3-56.
Zakrevskij A., Pottosin Yu., and Cheremisinova L. Design of Logical Control Devices. Tallinn, TUT Press, 2009.
Pottosin Yu. V. Sovmestnoe energosberegavushchee kodirovanie sostovaniv posledovatel’nvkh avtomatov seti, realizuyushchev parallel’nvy avtomat [Joint low power state assignment of sequential automata of a net implementing a parallel automaton]. Informatika, 2023, vol. 20, no. 1, pp. 75-90. (in Russian).
Pottosin Yu. V. Dekompozitsiva parallel’nogo avtomata v set’ posledovatel’nvkh avtomatov i energosberegavushchee kodirovanie ikh sostovaniv pri asinkhronnov realizatsii [Decomposition of a parallel automaton into a net of sequential automata and low power state assignment of them at asynchronous implementation]. Informatika, 2024, vol. 21, no. 3, pp. 7-22. (in Russian).
Hartmanis J. and Stearns R. E. Algebraic Structure Theory of Sequential Machines. Englewood Cliffs, N.J., Prentice Hall Inc., 1966.
Keevallik A. E. Teorema dekompozitsii konechnvkh avtomatov [A theorem of decomposition of finite automata]. Avtomatika i Vychislitel’nava Tekhnika, 1974, no. 1, pp. 17-24. (in Russian).
Pottosin Yu. V. Kombinatornve Zadachi v Logicheskom Proektirovanii Diskretnvkh Ustrovstv [Combinatorial Problems in Logical Design of Discrete Devices]. Minsk, Belaruskaja Navuka, 2021, 175 p. (in Russian).
Zakrevskiy A. D. Raskraska grafov pri dekompozitsii bulevvkh funktsiv [Coloring graphs in decomposition of Boolean functions]. Logicheskoe Proektirovanie, 2000, iss.5, pp. 83-97. (in Russian).
Macii E., Pedram M., and Somenzi F. High-level power modeling, estimation and optimization. IEEE Trans. CADICS, 1998, vol. 17, no. 11, pp. 1061-1079.
Pottosin Yu. V. Low power assignment of partial states of a parallel automaton. Prikladnava Diskretnava Matematika, 2022, no. 56, pp. 113-122.
Pottosin Yu. V. and Shestakov E. A. Dekompozitsiva avtomata v dvukhkomponentnuvu set’ s ogranicheniem na vnutrennie svvazi [Decomposition of an automaton into a two-component net with restrictions on internal communication]. Avtomatika i Vychislitel’nava Tekhnika, 1982, no. 6, pp. 25-32. (in Russian).
Zakrevskij A., Pottosin Yu., and Cheremisinova L. Optimization in Boolean Space. Tallinn, TUT Press, 2009.
Zakrevskij A., Pottosin Yu,., and Cheremisinova L. Combinatorial Algorithms of Discrete Mathematics. Tallinn, TUT Press, 2008.
Pottosin Yu. V., Toropov N. R., and Shestakov E. A. Metod minimizatsii sistemv ne polnost’vu opredelennvkh bulevvkh funktsiv [A method for minimization of a system of incompletely specified Boolean functions]. Informatika, 2009, no. 3(23), pp. 16-26. (in Russian).
Pottosin Yu. Race-free state assignment for low power asynchronous automaton. Further Improvements in the Boolean Domain. Ed. B. Steinbach. Cambridge Scholars Publ., 2018, pp.253-267.
Zakrevskiy A. D. Optimizatsiva pokrvtiv mnozhestv (Optimization of set covering]. Logicheskiv Yazvk diva Predstavleniva Algoritmov Sinteza Relevnvkh Ustrovstv (Logical Language for Representation of Algorithms for Relay Devices Synthesis]. Ed. M. A. Gavrilov. Moscow, Nauka, 1966, pp. 136-148. (in Russian).
Decomposition of a parallel automaton into a net of sequential automata | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/2
Decomposition of a parallel automaton into a net of sequential automata | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/2