Boolean functions with multiplicative complexity 3 and 4

摘要

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 Fisher and Peralta (2002), and Find et al. (IJICoT4(4), 222-236,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 dimensiondim(f) of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that the multiplicative complexity offis at least left ceiling dim(f)/2 right ceiling . For MC 3, this implies that there are no equivalence classes other than those 24 identified in calik et al. (2018). Using the techniques from calik 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 ofn-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.