检索结果-内蒙古大学图书馆

A 4-NORMAL LOWER BOUND ON THE combinational complexity OF CERTAIN SYMMETRICAL BOOLEAN FUNCTIONS OVER THE BASIS OF UNATE DYADIC BOOLEAN FUNCTIONS

引用

SIAM JOURNAL ON COMPUTING 1991年第3期20卷 499-505页

作者： ZWICK, U TEL AVIV UNIV DEPT COMP SCI IL-69978 TEL AVIV ISRAEL

A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a 4n-O(1) lower bound on the circuit complexity of the function over U2 = B2-{+, = }, the basis of unate dyadic boolean functions. Among the functions to which this lower bound applies are the modular functions MOD(k) (n) for any fixed k greater-than-or-equal-to 3 (MOD(k) (n) is the function which returns 1 if and only if (SIGMA-x(i)) mod k = 0). Finally, a 5n upper bound is obtained on the circuit complexity over U2 of the function MOD4 (n).

关键词： combinational complexity BOOLEAN FUNCTIONS LOWER BOUNDS

来源：评论

学校读者我要写书评

暂无评论

N-LOG-N LOWER BOUND ON SYNCHRONOUS combinational complexity

引用

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY 1977年第2期64卷 300-306页

作者： HARPER, LH UNIV CALIF RIVERSIDE DEPT MATHRIVERSIDECA 92502

Abstract: Synchronous combinational machines are combinational machines such that the length of all paths from inputs to a logic element are the same. In this paper is is shown that any Boolean function of n variables satisfying certain subfunction conditions (which are satisfied by “almost all” such functions) must have synchronous combinational complexity at least $n\log n$.

关键词： Boolean functions combinational complexity probabilistic set theory

来源：评论

学校读者我要写书评

暂无评论

Binary Adder Circuits of Asymptotically Minimum Depth, Linear Size, and Fan-Out Two

引用

ACM TRANSACTIONS ON ALGORITHMS 2018年第1期14卷 1–18页

作者： Held, Stephan Spirkl, Sophie Theresa Univ Bonn Res Inst Discrete Math Lennestr 2 D-53113 Bonn Germany Princeton Univ Program Appl & Computat Math Fine HallWashington Rd Princeton NJ 08544 USA

We consider the problem of constructing fast and small binary adder circuits. Among widely used adders, the Kogge-Stone adder is often considered the fastest, because it computes the carry bits for two n-bit numbers (where n is a power of two) with a depth of 2 log(2) n logic gates, size 4n log(2) n, and all fan-outs bounded by two. Fan-outs of more than two are disadvantageous in practice, because they lead to the insertion of repeaters for repowering the signal and additional depth in the physical implementation. However, the depth bound of the Kogge-Stone adder is off by a factor of two from the lower bound of log(2) n. Two separate constructions by Brent and Krapchenko achieve this lower bound asymptotically. Brent's construction gives neither a bound on the fan-out nor the size, while Krapchenko's adder has linear size, but can have up to linear fan-out. With a fan-out bound of two, neither construction achieves a depth of less than 2 log(2) n. In a further approach, Brent and Kung proposed an adder with linear size and fan-out two but twice the depth of the Kogge-Stone adder. These results are 33-43 years old and no substantial theoretical improvement for has beenmade since then. In this article, we integrate the individual advantages of all previous adder circuits into a new family of full adders, the first to improve on the depth bound of 2 log(2) n while maintaining a fan-out bound of two. Our adders achieve an asymptotically optimum logic gate depth of log(2) n + o(log(2) n) and linear size O(n).

关键词： Binary addition circuit combinational complexity parallel depth size fan-out

来源：评论

学校读者我要写书评

暂无评论

LINEAR LOWER BOUNDS ON UNBOUNDED FAN-IN BOOLEAN CIRCUITS

引用

INFORMATION PROCESSING LETTERS 1985年第2期21卷 71-74页

作者： HROMKOVIC, J Department of Theoretical Cybernetics Cosmenius University 842 15 Bratislava Czechoslovakia

A major problem in complexity theory has been the determination of lower bounds on Boolean circuit complexity. In previous work, linear lower bounds have been obtained for 2-bounded fan-in Boolean circuits. An investigation is made of the determination of linear lower bounds for unbounded fan-in circuits. A general model of unbounded fan-in circuits is introduced based on a special class of powerful circuits, characterized as directed, acyclic graphs with unbounded indegree and outdegree nodes. These circuits are more powerful than unbounded fan-in circuits previously studied. Through definition of the communication complexity of this class of circuits, linear lower bounds on circuit complexity of Boolean functions are obtained.

关键词： combinational complexity communication complexity unbounded fan-in Boolean circuits

来源：评论

学校读者我要写书评

暂无评论

PIK MASS-PRODUCTION AND AN OPTIMAL CIRCUIT FOR THE NECIPORUK SLICE

引用

COMPUTATIONAL complexity 1995年第2期5卷 132-154页

作者： HILTGEN, AP PATERSON, MS UNIV WARWICK DEPT COMP SCICOVENTRY CV4 7ALW MIDLANDSENGLAND

Let f : {0, 1}(n) --> {0, 1}(m) be an m-output Boolean function in n variables. f is called a k-slice if f(x) equals the all-zero vector for all x with Hamming weight less than k and f(x) equals the all-one vector for all x with Hamming weight more than k. Wegener showed that ''PIk-set circuits'' (set circuits over prime implicants of length k) are at the heart of any optimum Boolean circuit for a k-slice f. We prove that, in PIk-set circuits, savings are possible for the mass production of any F\X, i.e., any collection F of m output-sets given any collection X of n input-sets, if their PIk-set complexity satisfies SCm(F\X) greater than or equal to 3n + 2m. This PIk mass production, which can be used in monotone circuits for slice functions, is then exploited in different ways to obtain a monotone circuit of complexity 3n + o(n) for the Neciporuk slice, thus disproving a conjecture by Wegener that this slice has monotone complexity Theta(n(3/2)). Finally, the new circuit for the Neciporuk slice is proven to be asymptotically optimal, not only with respect to monotone complexity, but also with respect to combinational complexity.

关键词： combinational complexity MASS PRODUCTION SLICE FUNCTIONS SET CIRCUITS UPPER BOUNDS

来源：评论

学校读者我要写书评

暂无评论

GRAPH FUNCTIONS OF BOOLEAN FUNCTIONS

引用

IEEE TRANSACTIONS ON COMPUTERS 1984年第1期33卷 97-99页

作者： REISCHER, C SIMOVICI, DA UNIV MASSACHUSETTS DEPT MATHBOSTONMA 02125

We introduce and characterize those Boolean functions (graph functions) which can be regarded as characteristic functions of graphs of other Boolean functions. An algorithm for detecting these functions is also presen... 详细信息

关键词： Boolean functions complexity theory Arrays Switches Data mining Algorithm design and analysis Author Keywords identifying graph function Boolean function combinational complexity graph function

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL WORK OF combinational MACHINES

引用

IEEE TRANSACTIONS ON COMPUTERS 1977年第11期26卷 1161-1163页

作者： ECKER, K SCHUTT, D GESELLS MATH & DATENVERARBEITUNG BONNFED REP GER UNIV BONN INST INFORMATD-5300 BONN 1FED REP GER

In this correspondence we discuss an application of a work measure introduced by Hellerman. Uniform machines are represented by chains of transformations of Boolean functions. The work of any transformation depends on... 详细信息

关键词： Boolean matrix combinational complexity combinational machine (logic circuit) computational work of processes transformation of Boolean functions.

来源：评论

学校读者我要写书评

暂无评论

ASYMPTOTICALLY OPTIMAL CIRCUIT FOR A STORAGE ACCESS FUNCTION

引用

IEEE TRANSACTIONS ON COMPUTERS 1980年第8期29卷 737-738页

作者： KLEIN, P PATERSON, MS UNIV WARWICK DEPT COMP SCIWARWICKFED REP GER

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,··... 详细信息

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.

关键词： Boolean function combinational complexity

来源：评论

学校读者我要写书评

暂无评论

The complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging

引用

IEEE Transactions on Computers 1979年第10期C-28卷 773-782页

作者： Lamagna, Edmund A. Department of Computer Science and Experimental Statistics University of Rhode Island Kingston RI 02881 United States

In this paper, we consider the size of combinational switching networks required to synthesize monotone Boolean functions using only operations from the functionally incomplete set of primitives {disjunction, conjunction}. A general methodology is developed which is used to derive Ω(n log n) lower bounds on the size of monotone switching circuits for certain bilinear forms (including Toeplitz and circulant matrix-vector products, and Boolean convolution), certain routing networks (including cyclic and logical shifting), and sorting and merging. A homomorphic mapping technique is also given whereby the lower bounds derived on the sizes of monotone switching networks for Boolean functions can be extended to a larger class of problem domains. Copyright © 1979 by the Institute of Electrical and Electronics Engineers, Inc.

关键词： Bilinear form combinational complexity homomorphic mapping merging monotone increasing Boolean function routing network shifting sorting

来源：评论

学校读者我要写书评

暂无评论

A

引用

SIAM Journal on Computing 1991年第3期20卷 499-505页

作者： Uri Zwick

A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a 4n−O(1)4n−O(1)4n - O(1) lower bound on the circuit complexity of the function over <span class="MJ

A simple, and easy-to-check, property of a symmetric boolean function is shown to imply a

4n−O(1) $4n - O(1)$ lower bound on the circuit complexity of the function over

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：