Microprocessor design complexity is growing rapidly. As a result, current development costs for top of the line processors are staggering, and are doubling every 4 years. As we design ever larger and more complex proc...
详细信息
Multiple-valued quantum circuit synthesis using permutations-based fast transforms is introduced. Since the reduction of power consumption is a major requirement for the circuit design in future technologies, such as ...
详细信息
ISBN:
(纸本)0769521304
Multiple-valued quantum circuit synthesis using permutations-based fast transforms is introduced. Since the reduction of power consumption is a major requirement for the circuit design in future technologies, such as in quantum computing, the main features of several future technologies will include reversibility. Consequently, the new quantum circuits can play an important task in the design of future circuits that consume minimal power.
Novel quantum circuit synthesis using reversible Davio expansions is introduced the new method uses two planes to synthesize the quantum circuits: 1) reversible butterfly circuit plane, and 2) plane of quantum gates t...
详细信息
ISBN:
(纸本)0769521304
Novel quantum circuit synthesis using reversible Davio expansions is introduced the new method uses two planes to synthesize the quantum circuits: 1) reversible butterfly circuit plane, and 2) plane of quantum gates to perform additions and multiplications. Since the reduction of power consumption is a major requirement for circuit design of future technologies, such as in quantum circuits, the main features of several future technologies will include reversibility, and thus the new synthesis method using reversible butterfly circuits can play an important role in the synthesis of circuits that consume minimal power.
We present a new method for proving strong lower bounds in communication complexity. this method is based on the notion of the conditional information complexity of a function which is the minimum amount of informatio...
详细信息
ISBN:
(纸本)0769518222
We present a new method for proving strong lower bounds in communication complexity. this method is based on the notion of the conditional information complexity of a function which is the minimum amount of information about the inputs that has to be revealed by a communication protocol for the function. While conditional information complexity is a lower bound on communication complexity, we show that it also admits a direct sum theorem. Direct sum decomposition reduces our task to that of proving conditional information complexity lower bounds for simple problems (such as the AND of two bits). For the latter, we develop novel techniques based on Hellinger distance and its generalizations. Our paradigm leads to two main results: (1) An improved lower bound for the multi-party set-disjointness problem in the general communication complexity model, and a nearly optimal lower bound in the one-way communication model. As a consequence, we show that for any real k > 2, approximating the kth frequency moment in the data stream model requires essentially Omega(n(1-2/k)) space;this resolves a conjecture of Alon et al. (J. Comput. System Sci. 58(l) (1999) 137). (2) A lower bound for the L-p approximation problem in the general communication model;this solves an open problem of Saks and Sun (in: proceedings of the 34thannualacmsymposium on theory of Computing (STOC), 2002, pp. 360-369). As a consequence, we show that for p > 2, approximating the L-p norm to within a factor of n(epsilon) in the data stream model with constant number of passes requires Omega(n(1-4epsilon-2/p)) space. (C) 2003 Elsevier Inc. All rights reserved.
We introduce a graph-theoretical approach to the study of approximation of non-Boolean functions on Boolean algebra. We show that optimal interpolations of non-Boolean functions by Boolean functions are linked to mini...
详细信息
We introduce a graph-theoretical approach to the study of approximation of non-Boolean functions on Boolean algebra. We show that optimal interpolations of non-Boolean functions by Boolean functions are linked to minimal chromatic decompositions of graphs attached to these functions and we study special vertices in these graphs.
In this paper, we provide a brief review of various decision diagrams (DDs) with attributed edges, and then we propose a method for construction of various edge-valued diagrams for multiple-valued logic functions. We ...
详细信息
In this paper, we provide a brief review of various decision diagrams (DDs) with attributed edges, and then we propose a method for construction of various edge-valued diagrams for multiple-valued logic functions. We consider construction of both edge-valued diagrams withthe additive and the multiplicative attributes at the edges. We illustrate the application of related algorithms by constructing examples of decision diagrams for quaternary functions.
Ternary Galois Field Sum of Products (TGFSOP) expressions are found to be good choice for ternary reversible, and especially quantum, logic design. In this paper, we propose 16 Ternary Galois Field Expansions (TGFE) a...
详细信息
Ternary Galois Field Sum of Products (TGFSOP) expressions are found to be good choice for ternary reversible, and especially quantum, logic design. In this paper, we propose 16 Ternary Galois Field Expansions (TGFE) and introduce three Ternary Galois Field Decision Diagrams (TGFDD) using the proposed TGFEs, which are useful for reversible and quantum logic design. We also propose a heuristic for creating TGFDDs and a method for flattening the TGFDDs for determining TGFSOP expressions. We provide experimental results to show the effectiveness of the developed methods.
the success of the local covering approach to multiple-valued input two-valued output (MVITVO) functions minimization depends vastly on the proper choice of the base minterms from the ON set of the some new techniques...
详细信息
the success of the local covering approach to multiple-valued input two-valued output (MVITVO) functions minimization depends vastly on the proper choice of the base minterms from the ON set of the some new techniques to improve the performance of this approach. We have introduced a graph called an enhanced assignment graph (BAG) for the efficient grouping of the Boolean variables. In order to make the best choice of the proper base minterm we have defined a new technique to find the potential canonical cube (PCC) covering it. In this process we have succeeded in finding out the essential primes efficiently which enhances the total computation time and produces better sum of products (SOP).
Copy Decision Diagrams (CDDs) are an approach to the reduction of sizes of Multi-Terminal Binary Decision Diagrams (MTBDDs) by using the copy properties of discrete functions. Functions having different types of copy ...
详细信息
Copy Decision Diagrams (CDDs) are an approach to the reduction of sizes of Multi-Terminal Binary Decision Diagrams (MTBDDs) by using the copy properties of discrete functions. Functions having different types of copy properties can be efficiently represented by CDDs. Illustrative examples are Walsh and Reed-Muller functions as well as different binary codes. In this paper we consider an extension of this idea to Multi-valued Decision Diagrams (MDDs). We propose Copy MDDs (CMDD) as a modification of MDDs that exploits copy properties of functions besides properties already used in reduction of MDDs. Experimental results show reduction capabilities of CMDDs.
An r-valued m-variable reversible logic function maps each of the r m input patters to a unique output pattern. the synthesis problem is to realize a reversible function by a cascade of primitive reversible gates. In ...
详细信息
An r-valued m-variable reversible logic function maps each of the r m input patters to a unique output pattern. the synthesis problem is to realize a reversible function by a cascade of primitive reversible gates. In this paper, we present a simple heuristic algorithm that exploits the bidirectional synthesis possibility inherent in the reversibility of the specification. the primitive reversible gates considered here are one possible extension of the well-known binary Toffoli gates. We present exhaustive results for the 9! 2-variable 3-valued reversible functions comparing the results of our algorithm to optimal results found by breadth-first search. the approach can be applied to general m-variable, r-valued reversible specifications. Further, we show how the presented technique can be applied to irreversible specifications. the synthesis of a 3-input, 3-valued adder is given as a specific case.
暂无评论