Главная         Авторы   Статьи   Год проведения   Тематика   Организации        Конференция МЭС

О сложности инверсных графов, реализующих булевы функции от малого числа переменных
Авторы
	Ложкин С.А.
	Зизов В.С.
	Шуплецов М.С.
	Жуков В.В.
	Хзмалян Д.Э.
	Белянков О.О.
Год публикации
	2020
DOI
	10.31114/2078-7707-2020-4-95-102
УДК
	004.023
Аннотация
	В работе рассматривается задача построения каталогов схем, реализующих функции алгебры логики от малого числа переменных. Данная задача рассматривается для двух моделей схем из функциональных элементов, описанных в тексте. Общей чертой моделей является наличие элемента отрицания нулевой стоимости, различаются модели своими базисами. Для решения задачи разработаны алгоритмы синтеза схем, и на их основе реализованы программные инструменты. С применением описанных методов получены минимальные и близкие к ним схемы для всех функций алгебры логики от пяти переменных. Установлена верхняя оценка сложности реализации функций в этих моделях. Показана верхняя оценка средней сложности схем в этих моделях.
Ключевые слова
	методы синтеза схем, схема из функциональных элементов, базис Поста, сложность булевых функций, средняя схемная сложность, функция голосования, база данных схем.
Ссылка на статью
	Ложкин С.А., Зизов В.С., Шуплецов М.С., Жуков В.В., Хзмалян Д.Э., Белянков О.О. О сложности инверсных графов, реализующих булевы функции от малого числа переменных // Проблемы разработки перспективных микро- и наноэлектронных систем (МЭС). 2020. Выпуск 4. С. 95-102. doi:10.31114/2078-7707-2020-4-95-102
Адрес статьи
	http://www.mes-conference.ru/data/year2020/pdf/D103.pdf