RESUMEN
Multiplicative complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis (AND, XOR, NOT). Boolean functions with MC 1 and 2 have been characterized in Fischer and Peralta (2002), and Find et al. (2017), respectively. In this work, we identify the affine equivalence classes for functions with MC 3 and 4. In order to achieve this, we utilize the notion of the dimension dim(f) of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that the multiplicative complexity of f is at least [dim(f)/2]. For MC 3, this implies that there are no equivalence classes other than those 24 identified in Çalik et al. (2018). Using the techniques from Çalik et al. and the new relation between the dimension and MC, we identify all 1277 equivalence classes having MC 4. We also provide a closed formula for the number of n-variable functions with MC 3 and 4. These results allow us to construct AND-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.
RESUMEN
A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a Boolean circuit over the basis {XOR, AND, NOT}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and by Boyar and Peralta in 2008. We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions ∑ k n and counting functions ∑ k n with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric ∑ 4 8 and the counting ∑ 4 8 functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.
RESUMEN
The multiplicative complexity of a Boolean function is the minimum number of two-input AND gates that are necessary and sufficient to implement the function over the basis (AND, XOR, NOT). Finding the multiplicative complexity of a given function is computationally intractable, even for functions with small number of inputs. Turan et al. [1] showed that n-variable Boolean functions can be implemented with at most n-1 AND gates for n ≤ 5. A counting argument can be used to show that, for n ≥ 7, there exist n-variable Boolean functions with multiplicative complexity of at least n. In this work, we propose a method to find the multiplicative complexity of Boolean functions by analyzing circuits with a particular number of AND gates and utilizing the affine equivalence of functions. We use this method to study the multiplicative complexity of 6-variable Boolean functions, and calculate the multiplicative complexities of all 150357 affine equivalence classes. We show that any 6-variable Boolean function can be implemented using at most 6 AND gates. Additionally, we exhibit specific 6-variable Boolean functions which have multiplicative complexity 6.
