On length of Boolean functions of a small number of variables in the class of pseudo-polynomials

Selezneva, S.N.; Lobanov, A.A.

Статья опубликована в журнале из списка RSCI Web of Science

Информация о цитировании статьи получена из Web of Science, Scopus
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 21 октября 2020 г.

Авторы: Selezneva S.N., Lobanov A.A.
Журнал: Известия Иркутского государственного университета. Серия Математика
Том: 33
Год издания: 2020
Первая страница: 96
Последняя страница: 105
DOI: 10.26516/1997-7670.2020.33.96
Аннотация: Minimization of Boolean functions in their various representations is required in logic design of digital devices. EXOR sums (polynomial forms) are considered among other representations. An EXOR sum (a polynomial form) is an expression that is an EXOR sum of products of factors in a certain form. We can accentuate some classes of EXOR sums (of polynomial forms) such that Fixed Polarized Reed-Muller forms, FPRMs (polarized polynomial forms, PPFs), EXOR Sums of Products, ESOPs (polynomial normal forms, PNFs), EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs), etc. In series of works, minimization algorithms are devised, and bounds are obtained for the length of functions in these classes of EXOR sums. Herewith, there are different aspects in these researches, in particular, to obtain bounds of the length for the most complex functions of $n$ variables for an arbitrary number $n$ and to find the exact length for functions of a small number of variables.The present work is devoted to finding the exact length for functions of a small number of variables. EXOR Sums of Pseudo-Products, ESPPs (pseudo-polynomial forms, PSPFs) for Boolean functions are considered in it. An EXOR Sum of Pseudo-Products, ESPP (a pseudo-polynomial form, PSPF) is an expression that is an EXOR sum of products of linear functions. The length of an ESPP is the number of its summands; the length of a function in the class of ESPPs is the smallest length among all ESPPs, representing this function. In the work, the complete classification by the length in the class of ESPPs is obtained for functions of four variables. The largest length and the average length in the class of ESPPs are found for functions of five variables.
Добавил в систему: Селезнева Светлана Николаевна

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ИНХС РАН

On length of Boolean functions of a small number of variables in the class of pseudo-polynomialsстатья

Прикрепленные файлы