Asymptotically Optimal Circuit for a Storage Access Function
Asymptotically Optimal Circuit for a Storage Access Function
复制标题
存储访问函数的渐近最优电路
DOI：
10.1109/tc.1980.1675657
复制
发表时间：
1980
影响因子：
3.7
通讯作者：
M. Paterson
中科院分区：
文献类型：
--
作者：
Peter Klein;M. Paterson
设gk:{0,1}n+k→{0,1}，其中n = 2k是由gk(a1，···，ak, X0，···，xn-1) = x(a)定义的二进制函数，其中(a)是具有二进制表示形式a1，···，ak的自然数。这个函数模拟随机存取存储器中的读操作。在2010年，Paul证明了gk的组合复杂度的2n的下界。这种对应关系导出了gk在2n + 0（√n）个门和深度渐近于k的电路中的实现。
Let gk:{0,1}n+k → {0,1}, where n = 2k, be the binary function defined by gk(a1,···, ak, X0,···, xn-1) = x(a) where (a) is the natural number with binary representation a1,···, ak. This function models the reading operation in a random-access storage. In [1] Paul proved a 2n lower bound to the combinational complexity of gk. This correspondence derives a realization for gk in a circuit with 2n + 0(√n) gates and a depth asymptotic to k.