International Conference on Fuzzy Systems and Knowledge Discovery (FSKD)

A simplification algorithm for reversible logic network of positive/negative control gates

Xueyun Cheng, Zhijin Guan, Wei Wang, Lingling Zhu

Published May 1, 2012• 8 citations

Abstract

To further simplify the reversible circuit cascaded by positive/negative control (PNC) gates, new merging, moving and splitting rules of PNC gates were proposed in the paper, and these rules have been proved correct by way of logic algebra. We gave a novel simplification algorithm for reversible logic network of PNC gates by utilizing these rules. Experimental results on all 3-bit reversible functions show that our simplification algorithm is effective, it can decrease the gate count as well as the number of control bits compared to some known results, which were yielded by two excellent heuristic methods. Because the proposed rules have the generality, our simplification algorithm can be easily extended to reversible functions with more number of input bits.

DOI: 10.1109/fskd.2012.6233837

Related papers

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

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

Reversible Logic Synthesis Algorithm Based on Decreasing Complexity

Xueyun Cheng, Zhijin Guan, Zhu, Lingling

In order to reduce the scale of the generated reversible network, we present the concept of effective complexity-equal exchanging POT and splitting POT, and propose novel techniques for the synthesis of reversible networks of Toffoli gates. The interchanging and merging gates strategies in reversible network and relevant proofs are given, furthermore, we put forward the valid simplification method of a reversible network. The experimental results on all 3-bit and part of 4-bit reversible functions show that the proposed synthesis algorithm and simplification method have better performance in reducing reversible gate count as well as control bit count compared to other...

ASME Press eBooksJan 1, 20120 citations

Rule-based Optimization of Reversible Toffoli Circuits

Xueyu Cheng

Optimization of reversible circuits is one of key problems of reversible logic synthesis.To solve the problem of high algorithm complexity and poor scalability of reversible Toffoli circuits,the paper analyzed and summarized relationship between adjacent Toffoli gates,proposed and proven the moving and simplification rules of sub-sequence of reversible circuit cascaded by Toffoli gates,and gave the optimization algorithm based on these rules.The algorithm examines the circuit bidirectionally according to the moving rules,searches the sub-sequence satisfying simplification rules,performs corresponding optimization,and the process is repeated until the circuit does' t change.The algorithm is irrelevant to the number of input lines,does' t need to store extra information,is suitable to different Toffoli circuit synthesis methods,and its algorithm complexity is O(s3),which is superior to O(n!t2s3)of generally used template optimization technique.Results of examples and experiments on all 3-bit reversible functions show that the number of gates and the control bits can be reduced effectively and the cost of reversible circuit is decreased.

Jan 1, 20130 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

Network Structure Cascade for Reversible Logic

Zhijin Guan, Xiaolin Qin, Yi-Qing Zhang +1 more

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.

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