Preview

Информатика

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

Эвристический метод многоблочной параллельной декомпозиции системы частичных булевых функций

Аннотация

Описывается эвристический метод многоблочной параллельной декомпозиции системы частичных булевых функций, минимизирующий число функций, которые составляют искомую суперпозицию. При этом накладывается ограничение на число аргументов получаемых функций. Метод предполагает задание функций в интервальной форме, т. е. в виде пары троичных матриц. Одна из матриц представляет интервалы булева пространства аргументов (матрица интервалов), другая матрица - значения функций на этих интервалах (матрица функций). Рассматриваются графы ортогональности строк указанных матриц, и задача декомпозиции функций сводится к задаче о кратчайшем покрытии множества ребер графа ортогональности строк матрицы функций полными двудольными подграфами (бикликами) графа ортогональности строк матрицы интервалов. Каждой биклике приписывается определенным образом дизъюнктивная нормальная форма (ДНФ), и рассматриваются только те биклики, у которых соответствующие ДНФ имеют элементарные конъюнкции ранга, не превышающего границы числа аргументов получаемых функций. Биклики, составляющие искомое покрытие, и само покрытие формируются последовательно по определенным правилам. По каждой из этих биклик строится функция, аргументами которой являются переменные из элементарной конъюнкции минимального ранга соответствующей ДНФ. Получаемые функции представляются также в интервальной форме.

Об авторе

Ю. В. Поттосин
Объединенный институт проблем информатики, Национальная академия наук Беларуси
Россия

Поттосин Ю. В. - кандидат физико-математических наук, ведущий научный сотрудник.

Ул. Сурганова, 6, 220012, Минск



Список литературы

1. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. - М. : Физматлит, 2007. - 592 с.

2. Бибило, П. Н. Синтез комбинационных схем методом функциональной декомпозиции / П. Н. Бибило, С. В. Енин. - Минск : Наука и техника, 1987. - 189 с.

3. Поттосин, Ю. В. Табличные методы декомпозиции систем полностью определенных булевых функций / Ю. В. Поттосин, Е. А. Шестаков. - Минск : Беларуская навука, 2006. - 327 с.

4. Поттосин, Ю. В. Метод многоблочной параллельной декомпозиции системы частичных булевых функций / Ю. В. Поттосин // Информатика. - 2017. - № 3(55). - С. 92-98.

5. Поттосин, Ю. В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю. В. Поттосин, Е. А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф., Екатеринбург, 1998. - Екатеринбург : УрО РАН, 1998. -С. 185-189.


Рецензия

Для цитирования:


Поттосин Ю.В. Эвристический метод многоблочной параллельной декомпозиции системы частичных булевых функций. Информатика. 2018;15(4):109-116.

For citation:


Pottosin Yu.V. A heuristic method for multi-block parallel decomposition of a system of partial Boolean functions. Informatics. 2018;15(4):109-116. (In Russ.)

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


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


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