International Conference on Natural Computation (ICNC)

Network Structure Cascade for Reversible Logic

Zhijin Guan, Xiaolin Qin, Yi-Qing Zhang, Quan Shi

Published Jan 1, 2007• 2 citations

Abstract

A reversible logic function maps each of the 2m input patterns to a unique output pattern. The network cascade structure problem is to realize a reversible function by a cascade of primitive reversible gates. We present a method that synthesizes a network with family of Toffoli gates. The cascade algorithm finds cascade of Toffoli gates with no backtracking and minimal look-ahead, and apply transformations that reduce the number of gates in the network. We have synthesized all three input and output reversible functions and compare our results to the other optimal results. We also present the results of applying our synthesis method to obtain networks for number of benchmark function.

DOI: 10.1109/icnc.2007.493

Related papers

Toffoli network synthesis with templates

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer gates, while realizing the same function. This paper addresses the above synthesis approach. We present a basic method and, based on that, a bidirectional synthesis algorithm which produces a network of Toffoli gates realizing a given reversible specification. An asymptotically optimal modification of the basic synthesis algorithm employing generalized mEXOR gates is also presented. Transformations are then applied using template matching. The basis for a template is a network of gates that realizes the identity function. If a sequence of gates in the synthesized network matches a sequence comprised of more than half the gates in a template, then a transformation using the remaining gates in the template can be applied resulting in a reduction in the gate count for the synthesized network. All templates with up to six gates are described in this paper. Experimental results including an exhaustive examination of all 3-variable reversible functions and a collection of benchmark problems are presented. The paper concludes with suggestions for further research.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsMay 24, 2005227 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOct 30, 2006379 citations

Reversible Logic Synthesis of Networks of Positive/Negative Control Gates

Wenying Zhu, Zhijin Guan, Yueqing Hang

The research in reversible logic has been attracted in recent years. It has applications in quantum computing, low-power CMOS design and nanotechnology. Many methods on how to cascade a reversible network have been proposed. And all these networks are composed of Toffoli/Fredkin gates. In this paper, we present a method that synthesizes a network with family of Positive/Negative Control (PNC) gates. Through introducing some examples for 3×3 reversible functions, and comparing with the network which is composed of Toffoli gates, the results show that introducing the PNC gates can produce an improvement for the number of gates in the reversible network, and have an advantage in reducing the cost of network.

International Conference on Natural Computation (ICNC)Jan 1, 20092 citations

Exact Toffoli Network Synthesis of Reversible Logic Using Boolean Satisfiability

Daniel J. Grosse, Xiaobo Chen, Rolf Drechsler

Compact synthesis results for reversible logic is of major interest in low-power design and quantum computing. Such reversible functions are realized as a cascade of Toffoli gates. In this paper, we present the first exact synthesis algorithm for reversible functions using generalized Toffoli gates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable iff there exists a network representation with d gates. Thus we can guarantee minimality. For a set of benchmarks experimental results are given.

IEEE Dallas Circuits and Systems Conference (DCAS)Oct 1, 200610 citations

A Synthesis Method for MVL Reversible Logic

D. Michael Miller, Gerhard W. Dueck, Dmitri Maslov

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.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)Jan 1, 200454 citations

Reversible Logic Synthesis Based on Positive/Negative Control Gate

Zhu Wen-ying, Zhijin Guan, Yueqin Hang

【Abstract】This paper presents a cascaded algorithm based on reversible network of Positive/Negative Control(PNC) gate, designs the corresponding templates for 3 bit input/output function, and gives a reduction algorithm for the cascaded network. Experimental results show that comparing with the network which is composed of cascaded Toffoli gates, the reversible network using PNC gates contains fewer gates and has an advantage in reducing the cost of network. 【Key words】reversible logic function; Positive/Negative Control(PNC) gate; reversible network; template

Jisuanji gongchengJan 1, 20100 citations