Preview

Информатика

Расширенный поиск

МЕТОД МНОГОБЛОЧНОЙ ПАРАЛЛЕЛЬНОЙ ДЕКОМПОЗИЦИИ СИСТЕМЫ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ

Аннотация

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

Об авторе

Ю. В. Поттосин
Объединенный институт проблем информатики НАН Беларуси
Беларусь
Минск, Сурганова, 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.)

Просмотров: 604


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)