informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-233Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМЕТОД МНОГОБЛОЧНОЙ ПАРАЛЛЕЛЬНОЙ ДЕКОМПОЗИЦИИ СИСТЕМЫ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙA METHOD FOR MULTI-BLOCK PARALLEL DECOMPOSITION OF A SYSTEM OF PARTIAL BOOLEAN FUNCTIONSПоттосинЮ. В.PottosinYu. V.

Минск, Сурганова, 6

pott@newman.bas-net.byОбъединенный институт проблем информатики НАН БеларусиBelarus20170310201703(55)9298Copyright © Поттосин Ю.В., 20172017Поттосин Ю.В.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/233

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

A method for multi-block parallel decomposition of a system of partial Boolean functions represented by a pair of ternary matrices is described. The method involves examining the row orthogonality graphs of those matrices. It is reduced to finding the complete bipartite subgraphs (bicliques) in one of those graphs and finding a shortest cover of the row set of the other graph by those bicliques.

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 (Technical report) / M.A. Perkowski, S. Grygiel. – Portland, USA : Portland State University, Department of Electrical Engineering, 1995. – 188 p.Perkowski, M.A. A Survey of Literature on Functional Decomposition. Version IV (Technical report) / M.A. Perkowski, S. Grygiel. – Portland, USA : Portland State University, Department of Electrical Engineering, 1995. – 188 p.An improved functional decomposition method based on FAST and the method of removal and operation / F. Yu [et al.] // Intern. Conf. 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.] // Intern. Conf. on System Science and Engineering (ICSSE), Dalian, China, Jun. 2012. – Dalian, 2012. – P. 487–492.Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.Закревский, А.Д. Параллельная декомпозиция системы слабо определенных булевых функций / А.Д. Закревский, А.Е. Перышкин // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5. – С. 59–66.Закревский, А.Д. Параллельная декомпозиция системы слабо определенных булевых функций / А.Д. Закревский, А.Е. Перышкин // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5. – С. 59–66.Поттосин, Ю.В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков. – Минск : Белорус. наука, 2006. – 327 с.Поттосин, Ю.В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков. – Минск : Белорус. наука, 2006. – 327 с.Бибило, П.Н. Декомпозиция булевых функций на основе решения логических уравнений / П.Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.Бибило, П.Н. Декомпозиция булевых функций на основе решения логических уравнений / П.Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.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.Закревский, А.Д. Комбинаторный поиск подходящих разбиений при декомпозиции булевых функций / А.Д. Закревский // Вестник ТГУ. Приложение. – 2006. – № 18. – С. 4–9.Закревский, А.Д. Комбинаторный поиск подходящих разбиений при декомпозиции булевых функций / А.Д. Закревский // Вестник ТГУ. Приложение. – 2006. – № 18. – С. 4–9.Поттосин, Ю.В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2011. – № 3(16). – С. 100–107.Поттосин, Ю.В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2011. – № 3(16). – С. 100–107.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.Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.Taghavi Afshord, S. An input variable partitioning algorithm for functional decomposition of a system of Boolean functions based on the tabular method / S. Taghavi Afshord, Yu.V. Pottosin, B. Arasteh // Discrete Applied Mathematics. – 2015. – Vol. 185. – P. 208–219.Taghavi Afshord, S. An input variable partitioning algorithm for functional decomposition of a system of Boolean functions based on the tabular method / S. Taghavi Afshord, Yu.V. Pottosin, B. Arasteh // Discrete Applied Mathematics. – 2015. – Vol. 185. – P. 208–219.Поттосин, Ю.В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю.В. Поттосин, Е.А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф. – Екатеринбург : УрО РАН, 1998. – С. 185–189.Поттосин, Ю.В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю.В. Поттосин, Е.А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф. – Екатеринбург : УрО РАН, 1998. – С. 185–189.Pottosina, S. Finding maximal complete bipartite subgraphs in a graph / S. Pottosina, Yu. Pottosin, B. Sedliak // J. Applied Mathematics. – 2008. – Vol. 1, no. 1. – P. 75–81.Pottosina, S. Finding maximal complete bipartite subgraphs in a graph / S. Pottosina, Yu. Pottosin, B. Sedliak // J. Applied Mathematics. – 2008. – Vol. 1, no. 1. – P. 75–81.

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