Multiplicative complexity of some Boolean functionsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 27 января 2016 г.
Аннотация:The multiplicative (or conjunctive) complexity of a Boolean function f(x1, . . . , xn) (respectively, of a system of Boolean functions F = {f1, . . . , fm}) is the smallest number of AND gates in circuits in the basis {x&y, x ⊕ y, 1} implementing the function f (respectively, all the functions of system F). The multiplicative complexity of a function f (of a system of functions F) will be denoted by μ(f) (respectively, μ(F)). It will be shown that μ(f) = n − 1 if a function f(x1, . . . , xn) is representable as x1x2 . . . xn ⊕ q(x1, . . . , xn), where q is a function of degree two (n ≥ 3).Moreover,we show that μ(f) ≤ n−1 if a function f(x1, . . . , xn) is representable as a XOR sum of two multiaffine functions. Furthermore, μ(F) = n−1 if F = {x1x2 . . . xn , f(x1, . . . , xn)},where f is a function of degree two or a multiaffine function.