|
Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2015, Number 5, Pages 47–50
(Mi vmumm268)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Short notes
Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements
Yu. A. Kombarov Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Abstract:
The paper is devoted to realization of parity functions by circuits in the basis $U_\infty$. This basis contains all functions of form $(x_1^{\sigma_1}\&\ldots\& x_k^{\sigma_k})^{\beta}$. We present method of constructing circuts for pairity function of $n$ variables with complexity of $\lfloor (7n-4)/3\rfloor$. This improves previous known upper bound of $U_\infty$-complexity of parity function, that was
$\lceil (5n-1)/2\rceil$. It is also shown that constructed circuits are minimal for very small $n$ (for $n<7$).
Key words:
Boolean circuis, circuit complexity, parity function, minimal circuit.
Received: 11.06.2014
Citation:
Yu. A. Kombarov, “Upper estimate of realization complexity of linear functions in a basis consisting of multi-input elements”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2015, no. 5, 47–50; Moscow University Mathematics Bulletin, 70:5 (2015), 226–229
Linking options:
https://www.mathnet.ru/eng/vmumm268 https://www.mathnet.ru/eng/vmumm/y2015/i5/p47
|
Statistics & downloads: |
Abstract page: | 137 | Full-text PDF : | 103 | References: | 23 |
|