Efficient evaluation of Boolean functions is a fundamental problem in computer science, impacting computational complexity and hardware performance. A natural way to evaluate Boolean functions is using circuits compos...
详细信息
ISBN:
(纸本)9798331522452;9798331522445
Efficient evaluation of Boolean functions is a fundamental problem in computer science, impacting computational complexity and hardware performance. A natural way to evaluate Boolean functions is using circuits composed of two-input operators. However, synthesizing minimum circuits for functions with more than 6 inputs is typically infeasible. This paper introduces an engine based on Edward's theory of symmetry-based remapping for synthesizing Boolean chains. The proposed engine can synthesize functions with up to 20 inputs within seconds, surpassing state-of-the-art tools that require extensive hyper-parameter tuning to handle similar functions and fail to scale beyond that. Additionally, it enhances the interpretability of Boolean chains, uncovering recursive substructures that facilitate optimality proofs and inform bit-wise manipulation algorithms.
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 (...
详细信息
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).
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 ...
详细信息
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.
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...
详细信息
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).
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
The author studies a general model of unbounded fan-in circuits. Besides AND, OR, and NEG gates he allows, for each commutative and associative Boolean function g: left brace 0, 1 right brace **2 yields left brace 0, ...
详细信息
The author studies a general model of unbounded fan-in circuits. Besides AND, OR, and NEG gates he allows, for each commutative and associative Boolean function g: left brace 0, 1 right brace **2 yields left brace 0, 1 right brace , g-gates. Such circuits are called CA-circuits. Considering the parity function he shows that CA-circuits are more powerful than unbounded fan-in circuits studied till now.
The prefix problem is to compute all the products x t o x2 o xk for iik in, where o is an associative operation A recurstve construction IS used to obtain a product circuit for solving the prefix problem which has dep...
详细信息
It is shown that several natural, undecidable properties of grammars are such that the size of the smallest Turing machine which correctly answers questions of length n grows at a nearly maximal rate as n grows. Thus,...
详细信息
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 oper...
详细信息
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(vn) gates and a depth asymptotic to k.
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, conjunct...
详细信息
暂无评论