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 Y.V. A METHOD FOR MULTI-BLOCK PARALLEL DECOMPOSITION OF A SYSTEM OF PARTIAL BOOLEAN FUNCTIONS. Informatics. 2017;(3(55)):92-98. (In Russ.)

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


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


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