informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-104Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNИССЛЕДОВАНИЕ СВОЙСТВ РАЗЛОЖИМОСТИ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙINVESTIGATION OF DECOMPOSABILITY OF A SYSTEM OF BOOLEAN FUNCTIONSТагави АфшордС. Х.Taghavi AfshordS. H.ПоттосинЮ. В.PottosinYu. V.pott@newman.bas-net.byОбъединенный институт проблем информатики НАН БеларусиBelarus2013011020160494103Copyright © Тагави Афшорд С.Х., Поттосин Ю.В., 20162016Тагави Афшорд С.Х., Поттосин Ю.В.Taghavi Afshord S.H., Pottosin Y.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/104

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

A computer program is described which analyzes the decomposability of a system of Boolean functions and searches for an appropriate partition of the argument set. Three tasks linked with a system of Boolean functions are given: producing all solutions, searching for the best solution from the circuit complexity point of view, and finding a solution as quickly as possible, if the system is decomposable. The results of computer experiment for determining decomposability of systems of Boolean functions are given.

ReferencesHassoun, S. Logic Synthesis and Verification. The Springer International Series in Engineering and Computer Science / S. Hassoun, T. Sasao. – Kluwer Academic Publishers, 2001. – 472 p.Hassoun, S. Logic Synthesis and Verification. The Springer International Series in Engineering and Computer Science / S. Hassoun, T. Sasao. – Kluwer Academic Publishers, 2001. – 472 p.Perkowski, M.A. A Survey of Literature on Functional Decomposition, Version IV /M.A. Perkowski, S. Grygiel ; Portland State University, Department of Electrical Engineering. – Portland, USA, 1995. – 188 p.Perkowski, M.A. A Survey of Literature on Functional Decomposition, Version IV /M.A. Perkowski, S. Grygiel ; Portland State University, Department of Electrical Engineering. – Portland, USA, 1995. – 188 p.Muthukumar, V. An efficient variable partitioning approach for functional decomposition of circuits / V. Muthukumar, R.J. Bignall, H. Selvaraj // Journal of Systems Architecture. – 2007. – Vol. 53, no. 1. – P. 53–67.Muthukumar, V. An efficient variable partitioning approach for functional decomposition of circuits / V. Muthukumar, R.J. Bignall, H. Selvaraj // Journal of Systems Architecture. – 2007. – Vol. 53, no. 1. – P. 53–67.An improved functional decomposition method based on FAST and the method of removal and operation / F. Yu [et al.] // International Conference on System Science and Engineering (ICSSE), Dalian, China, Jun. 2012. – Dalian, 2012. – P. 487–492.An improved functional decomposition method based on FAST and the method of removal and operation / F. Yu [et al.] // International Conference on System Science and Engineering (ICSSE), Dalian, China, Jun. 2012. – Dalian, 2012. – P. 487–492.Закревский, А.Д. Логические основы проектирования дискретных устройств /А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Закревский, А.Д. Логические основы проектирования дискретных устройств /А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Бибило, П.Н. Декомпозиция булевых функций на основе решения логических уравнений / П.Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.Бибило, П.Н. Декомпозиция булевых функций на основе решения логических уравнений / П.Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.Jóźwiak, L. An effective and efficient method for functional decomposition of boolean functions based on information relationship measures / L. Jóźwiak, A. Chojnacki // 3rd Design and Diagnostics of Electronic Circuits and Systems Workshop (DDECS), Bratislava, Slovakia, Apr. 2000. – Bratislava, 2000. – P. 242–249.Jóźwiak, L. An effective and efficient method for functional decomposition of boolean functions based on information relationship measures / L. Jóźwiak, A. Chojnacki // 3rd Design and Diagnostics of Electronic Circuits and Systems Workshop (DDECS), Bratislava, Slovakia, Apr. 2000. – Bratislava, 2000. – P. 242–249.Закревский, А.Д. Декомпозиция частичных булевых функций – проверка на разделимость по заданному разбиению / А.Д. Закревский // Информатика. – № 1(13). – 2007. – С. 16–21.Закревский, А.Д. Декомпозиция частичных булевых функций – проверка на разделимость по заданному разбиению / А.Д. Закревский // Информатика. – № 1(13). – 2007. – С. 16–21.Files, C.M. New mutivalued functional decomposition algorithms based on MDDs /C.M. Files, M.A. Perkowski // IEEE Transactions on Computer-Aided Design of Integrated Ciruits and Systems. – 2000. – Vol. 19, no. 9. – P. 1081–1086.Files, C.M. New mutivalued functional decomposition algorithms based on MDDs /C.M. Files, M.A. Perkowski // IEEE Transactions on Computer-Aided Design of Integrated Ciruits and Systems. – 2000. – Vol. 19, no. 9. – P. 1081–1086.Rawski, M. Input variable partitioning method for decomposition-based logic synthesis targeted heterogeneous FPGAs / M. Rawski // International Journal of Electronics and Telecommunications. – 2012. – Vol. 58, no. 1. – P. 15–20.Rawski, M. Input variable partitioning method for decomposition-based logic synthesis targeted heterogeneous FPGAs / M. Rawski // International Journal of Electronics and Telecommunications. – 2012. – Vol. 58, no. 1. – P. 15–20.Поттосин, Ю.В. Табличные методы декомпозиции систем полностью определе нных булевых функций / Ю.В. Поттосин, Е.А. Шестаков. – Минск : Белорус. наука, 2006. –327 с.Поттосин, Ю.В. Табличные методы декомпозиции систем полностью определе нных булевых функций / Ю.В. Поттосин, Е.А. Шестаков. – Минск : Белорус. наука, 2006. –327 с.Поттосин, Ю.В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2011. – № 3 (16). – С. 100–107.Поттосин, Ю.В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2011. – № 3 (16). – С. 100–107.Романов, В.И. Разработка инструментальных средств логического проектирования /В.И. Романов // Логическое проектирование. Вып. 6. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2001. – С. 151–170.Романов, В.И. Разработка инструментальных средств логического проектирования /В.И. Романов // Логическое проектирование. Вып. 6. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2001. – С. 151–170.Romanov, V.I. Tools for programming Boolean calculations / V.I. Romanov // Abstracts of ECCO XVIII Conf. «Combinatorics for Modern Manufacturing, Logistics and Supply Chains», Minsk, Belarus. – Minsk, 2005. – P. 57–58.Romanov, V.I. Tools for programming Boolean calculations / V.I. Romanov // Abstracts of ECCO XVIII Conf. «Combinatorics for Modern Manufacturing, Logistics and Supply Chains», Minsk, Belarus. – Minsk, 2005. – P. 57–58.Кнут, Д.Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 /Д.Э. Кнут. – М. : Вильямс, 2013. – 960 с.Кнут, Д.Э. Искусство программирования. Т. 4, А. Комбинаторные алгоритмы. Ч. 1 /Д.Э. Кнут. – М. : Вильямс, 2013. – 960 с.

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