vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-204Research ArticleИНФОРМАТИКАINFORMATICSПОИСК РАЗРЕЗА ГРАФА В РЕШЕНИИ НЕКОТОРЫХ ЗАДАЧ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯSEARCH OF A CUT IN A GRAPH USED IN LOGICAL DESIGNПОТТОСИНЮ. В.POTTOSINYu. V.pott@newman.bas-net.byПОТТОСИНАС. А.POTTOSINAS. A.s.pottosina@gmail.comОбъединенный институт проблем информатики Национальной академии наук БеларусиUnited Institute of Informatics Problems of the National Academy of Sciences of BelarusБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and Radioelectronics20162211201603110118Copyright © ПОТТОСИН Ю.В., ПОТТОСИНА С.А., 20162016ПОТТОСИН Ю.В., ПОТТОСИНА С.А.POTTOSIN Y.V., POTTOSINA S.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/204

Рассматриваются две задачи логического проектирования дискретных устройств: декомпозиция булевых функций и кодирование состояний конечного автомата. Предлагается общий подход к решению этих задач, который связан с поиском максимального разреза в графе со взвешенными ребрами. На основе указанного метода предложены эвристические методы решения рассматриваемых задач.

Two optimization problems in logical design are considered: decomposition of Boolean functions and state assignment of a finite automaton. A common approach to those problems is suggested. This approach is connected with the search of a maximal cut in a graph with weighted edges. Heuristic methods based on this approach to solve the problems are suggested.

логическое проектированиедекомпозиция булевых функцийкодирование состояний конечного автоматаразрез графаlogical designdecomposition of Boolean functionsstate assignment of finite automatoncut in graphReferencesКристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978.Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. – М.: Мир, 1978.Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. – Минск: Белорус. наука, 2006.Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. – Минск: Белорус. наука, 2006.Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М.: Физматлит, 2007.Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М.: Физматлит, 2007.Benini, L. State assignment for low power dissipation / L. Benini, G. de Micheli. // IEEE J. of Solid State Circuits. – 1995. – Vol. 30, no. 3. – P. 32–40.Benini, L. State assignment for low power dissipation / L. Benini, G. de Micheli. // IEEE J. of Solid State Circuits. – 1995. – Vol. 30, no. 3. – P. 32–40.Perkowski, M. A. A Survey of Literature on Functional Decomposition. Version IV (Technical report) / M. A. Perkowski, S. Grygiel. – Portland: Portland State University, Department of Electrical Engineering, 1995.Perkowski, M. A. A Survey of Literature on Functional Decomposition. Version IV (Technical report) / M. A. Perkowski, S. Grygiel. – Portland: Portland State University, Department of Electrical Engineering, 1995.Taghavi Afshord, S. A new suboptimal decomposition algorithm based on the tabular method / S. Taghavi Afshord, Yu. V. Pottosin // Танаевские чтения: докл. Шестой междунар. науч. конф. (27–28 марта 2014 г., Минск). – Минск: ОИПИ НАН Беларуси, 2014. – С. 161–165.Taghavi Afshord, S. A new suboptimal decomposition algorithm based on the tabular method / S. Taghavi Afshord, Yu. V. Pottosin // Танаевские чтения: докл. Шестой междунар. науч. конф. (27–28 марта 2014 г., Минск). – Минск: ОИПИ НАН Беларуси, 2014. – С. 161–165.Поттосин, Ю. В. Метод минимизации системы полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2008. – № 2 (18). – С. 102–110.Поттосин, Ю. В. Метод минимизации системы полностью определенных булевых функций / Ю. В. Поттосин, Н. Р. Торопов, Е. А. Шестаков // Информатика. – 2008. – № 2 (18). – С. 102–110.Мурога, С. Системное проектирование сверхбольших интегральных схем: в 2 кн. / С. Мурога. – М.: Мир, 1985. – Кн. 1.Мурога, С. Системное проектирование сверхбольших интегральных схем: в 2 кн. / С. Мурога. – М.: Мир, 1985. – Кн. 1.Pedram, M. Power minimization in IC design: Principles and applications / M. Pedram // ACM Trans. Design Automat. Electron. Syst. – 1996. – Vol. 1. – P. 3–56.Pedram, M. Power minimization in IC design: Principles and applications / M. Pedram // ACM Trans. Design Automat. Electron. Syst. – 1996. – Vol. 1. – P. 3–56.Macii, E. High-level power modeling, estimation and optimization / E. Macii, M. Pedram, F. Somenzi // IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems. – 1998. – Vol. 17, no. 11. – P. 1061–1079.Macii, E. High-level power modeling, estimation and optimization / E. Macii, M. Pedram, F. Somenzi // IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems. – 1998. – Vol. 17, no. 11. – P. 1061–1079.Закревский, А. Д. Алгоритмы энергосберегающего кодирования состояний автомата / А. Д. Закревский. – Информатика. – 2011. – № 1 (29). – С. 68–78.Закревский, А. Д. Алгоритмы энергосберегающего кодирования состояний автомата / А. Д. Закревский. – Информатика. – 2011. – № 1 (29). – С. 68–78.Закревский, А. Д. Раскраска графов при декомпозиции булевых функций / А. Д. Закревский // Логич. проектирование. – Минск: ИТК НАН Беларуси, 2000. – Вып. 5. – С. 83–97.Закревский, А. Д. Раскраска графов при декомпозиции булевых функций / А. Д. Закревский // Логич. проектирование. – Минск: ИТК НАН Беларуси, 2000. – Вып. 5. – С. 83–97.

The authors declare that there are no conflicts of interest present.