|
This article is cited in 1 scientific paper (total in 1 paper)
On the multiplicative complexity of some Boolean functions
S. N. Selezneva Moscow State University, Moscow, 119992, Russia
Abstract:
In this paper, we study the multiplicative complexity of Boolean functions. The multiplicative complexity of a Boolean function $f$ is the smallest number of $\&$-gates in circuits in the basis $\{x\& y, x\oplus y, 1\}$ such that each such circuit computes the function $f$. We consider Boolean functions which are represented in the form $x_1, x_2\dots x_n\oplus q(x_1,\dots,x_n)$, where the degree of the function $q(x_1,\dots,x_n)$ 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 $x_1\dots x_n\oplus r(x_1,\dots,x_n)$, where $r(x_1,\dots,x_n)$ is a multi-affine function, is, in some cases, equal to $(n-1)$.
Key words:
Boolean function, circuit, complexity, multiplicative complexity, upper bound.
Received: 05.03.2014
Citation:
S. N. Selezneva, “On the multiplicative complexity of some Boolean functions”, Zh. Vychisl. Mat. Mat. Fiz., 55:4 (2015), 730–736; Comput. Math. Math. Phys., 55:4 (2015), 724–730
Linking options:
https://www.mathnet.ru/eng/zvmmf10197 https://www.mathnet.ru/eng/zvmmf/v55/i4/p730
|
Statistics & downloads: |
Abstract page: | 163 | Full-text PDF : | 30 | References: | 43 | First page: | 7 |
|