МЕТОД МНОГОБЛОЧНОЙ ПАРАЛЛЕЛЬНОЙ ДЕКОМПОЗИЦИИ СИСТЕМЫ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ
Аннотация
Описывается метод многоблочной параллельной декомпозиции системы частичных булевых функций, представленной парой троичных матриц. Метод предполагает рассмотрение графов ортогональности строк указанных матриц и сводится к нахождению полных двудольных подграфов (биклик) в одном из этих графов и кратчайшему покрытию множества ребер другого графа этими подграфами.
Об авторе
Ю. В. Поттосин
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Минск, Сурганова, 6
Беларусь
Минск, Сурганова, 6
Список литературы
1. 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.
2. 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.
3. 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.
4. Закревский, А.Д. Логические основы проектирования дискретных устройств / А.Д. Закревский, Ю.В. Поттосин, Л.Д. Черемисинова. – М. : Физматлит, 2007. – 592 с.
5. Закревский, А.Д. Параллельная декомпозиция системы слабо определенных булевых функций / А.Д. Закревский, А.Е. Перышкин // Логическое проектирование. – Минск : Ин-т техн. кибернетики НАН Беларуси, 2000. – Вып. 5. – С. 59–66.
6. Поттосин, Ю.В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю.В. Поттосин, Е.А. Шестаков. – Минск : Белорус. наука, 2006. – 327 с.
7. Бибило, П.Н. Декомпозиция булевых функций на основе решения логических уравнений / П.Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.
8. 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.
9. Закревский, А.Д. Комбинаторный поиск подходящих разбиений при декомпозиции булевых функций / А.Д. Закревский // Вестник ТГУ. Приложение. – 2006. – № 18. – С. 4–9.
10. Поттосин, Ю.В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю.В. Поттосин, Е.А. Шестаков // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. – 2011. – № 3(16). – С. 100–107.
11. 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.
12. Бибило, П.Н. Применение диаграмм двоичного выбора при синтезе логических схем / П.Н. Бибило. – Минск : Беларус. навука, 2014. – 231 с.
13. 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.
14. Поттосин, Ю.В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю.В. Поттосин, Е.А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф. – Екатеринбург : УрО РАН, 1998. – С. 185–189.
15. 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.
Рецензия
Для цитирования:
Поттосин Ю.В. МЕТОД МНОГОБЛОЧНОЙ ПАРАЛЛЕЛЬНОЙ ДЕКОМПОЗИЦИИ СИСТЕМЫ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ. Информатика. 2017;(3(55)):92-98.
For citation:
Pottosin Yu.V. A METHOD FOR MULTI-BLOCK PARALLEL DECOMPOSITION OF A SYSTEM OF PARTIAL BOOLEAN FUNCTIONS. Informatics. 2017;(3(55)):92-98. (In Russ.)
Просмотров: 650
Послать статью по эл. почте 