Energy and fan-in of logic circuits computing symmetric Boolean functions
Energy and fan-in of logic circuits computing symmetric Boolean functions
复制标题
计算对称布尔函数的逻辑电路的能量和扇入
DOI：
10.1016/j.tcs.2012.11.039
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Kei Uchizawa and Xiao Zhou
中科院分区：
文献类型：
--
作者：
Akira Suzuki;Kei Uchizawa and Xiao Zhou
本文考虑一种逻辑电路（即，由门组成的组合电路，每个门计算布尔函数）C计算对称布尔函数f，并研究C的两个复杂性度量，能量e和扇入l之间的关系，其中能量e是在C的所有输入上输出“1”的门的最大数量，扇入l是C中每个门的最大输入数。首先证明了任意n元对称布尔函数f都可以用能量e= O（n/l）且扇入l的逻辑电路计算，然后给出了几乎紧的下界e≥ n（n-mf）/l <$，其中mf是f的值向量中连续“0”或“1”的最大个数.我们的结果意味着存在一个权衡之间的能量和扇入的逻辑电路计算一个对称的布尔函数。
In this paper, we consider a logic circuit (ie, a combinatorial circuit consisting of gates, each of which computes a Boolean function) C computing a symmetric Boolean function f, and investigate a relationship between two complexity measures, energy e and fan-in l of C, where the energy e is the maximum number of gates outputting “1” over all inputs to C, and the fan-in l is the maximum number of inputs of every gate in C. We first prove that any symmetric Boolean function f of n variables can be computed by a logic circuit of energy e= O (n/l) and fan-in l, and then provide an almost tight lower bound e≥⌈(n− m f)/l⌉ where m f is the maximum numbers of consecutive “0” s or “1” s in the value vector of f. Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function.