Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Jisuanji gongcheng

Reversible Logic Synthesis Based on Positive/Negative Control Gate

Zhu Wen-ying, Zhijin Guan, Yueqin Hang

Published Jan 1, 2010• 0 citations
OpenAlex

Abstract

【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

Related papers

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, 2009•2 citations

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

Xueyun Cheng, Zhijin Guan, Wei Wang +1 more

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.

International Conference on Fuzzy Systems and Knowledge Discovery (FSKD)•May 1, 2012•8 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, 2007•2 citations

The Reversible Network Cascade Based on Reversible Logic Gate Coding Method

Hui Li, Zhijin Guan, Shanli Chen +1 more

Reversible computing is an emerging area of research and reversible logic synthesis is its important aspect. This paper provides reversible network cascade method based on reversible logic gate coding method. According to the number of vertical lines and control bits, which from small to large, the method constructs automatically the different output vectors corresponding network meanwhile the algorithm can generate all the reversible network. Compared with the three variables reversible function test in benchmark, its control gates amounts are much less and the cost is much lower.

International Conference on Information Assurance and Security (IAS)•Jan 1, 2009•1 citation

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 Systems•Oct 30, 2006•379 citations

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 Systems•May 24, 2005•227 citations
【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
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.
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.
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.
Reversible computing is an emerging area of research and reversible logic synthesis is its important aspect. This paper provides reversible network cascade method based on reversible logic gate coding method. According to the number of vertical lines and control bits, which from small to large, the method constructs automatically the different output vectors corresponding network meanwhile the algorithm can generate all the reversible network. Compared with the three variables reversible function test in benchmark, its control gates amounts are much less and the cost is much lower.
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
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.