Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts |
| |
Authors: | S. N. Selezneva |
| |
Affiliation: | 1.Department of Computational Mathematics and Cybernetics,Moscow State University,Moscow,Russia |
| |
Abstract: | An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ESPP(n) = ? (2 n /n 2). The quantity L ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |