On the multiplicative complexity of some Boolean functionsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 28 октября 2016 г.
Аннотация:In this paper, we study the multiplicative complexity of Boolean functions. The multipliplicative complexity of a Boolean function f is the smallest number of &-gates in circuits in the basis {x & y, x ⊕ y, 1} such that each such circuit computes the function f. We consider Boolean functions which are represented in the form x1, x2…xn ⊕ q(x1, …, xn), where the degree of the function q(x1, …, xn) is 2. We prove that the multiplicative complexity of each such function is equal to (n – 1). We also prove that the multiplicative complexity of Boolean functions which are represented in the form x1 … xn ⊕ r(x1, …, xn), where r(x1, …, xn) is a multi-affine function, is, in some cases, equal to (n – 1).