arXiv:1008.3694

Sorting Network for Reversible Logic Synthesis

Md. Saiful Islam, Md. Rafiqul Islam, Abdullah Al Mahmud, Muhammad Rezaul Karim

Published Aug 22, 2010• 4 citations

Abstract

In this paper, we have introduced an algorithm to implement a sorting network for reversible logic synthesis based on swapping bit strings. The algorithm first constructs a network in terms of n*n Toffoli gates read from left to right. The number of gates in the circuit produced by our algorithm is then reduced by template matching and removing useless gates from the network. We have also compared the efficiency of the proposed method with the existing ones.

DOI: 10.48550/arxiv.1008.3694

Related papers

BSSSN: Bit String Swapping Sorting Network for Reversible Logic Synthesis

Md. Saiful Islam

In this paper, we have introduced the notion of UselessGate and ReverseOperation. We have also given an algorithm to implement a sorting network for reversible logic synthesis based on swapping bit strings. The network is constructed in terms of n*n Toffoli Gates read from left to right and it has shown that there will be no more gates than the number of swappings the algorithm requires. The gate complexity of the network is O(n2). The number of gates in the network can be further reduced by template reduction technique and removing UselessGate from the network.

arXiv:1008.4668Aug 27, 20106 citations

Building Toffoli Network for Reversible Logic Synthesis Based on Swapping Bit Strings

Hafiz Md. Hasan Babu, Md. Saiful Islam, Md. Rafiqul Islam +4 more

In this paper, we have implemented and designed a sorting network for reversible logic circuits synthesis in terms of n*n Toffoli gates. The algorithm presented in this paper constructs a Toffoli Network based on swapping bit strings. Reduction rules are then applied by simple template matching and removing useless gates from the network. Random selection of bit strings and reduction of control inputs are used to minimize both the number of gates and gate width. The method produces near optimal results for up to 3-input 3-output circuits.

arXiv:1008.3357Aug 19, 20100 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 SystemsMay 24, 2005227 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

A novel Toffoli network synthesis algorithm for reversible logic

Yexin Zheng, Chao Huang

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. Reversible logic features a one-to-one input output correspondence which makes the logic synthesis for reversible functions differs greatly from traditional Boolean functions. Exact synthesis methods can provide optimal solutions in terms of the total number of reversible gates in the synthesis results. Unfortunately, they may suffer from long computation time, due to the fact that the search space is likely to grow exponentially as the circuit size increases. Therefore, in this paper, we propose an efficient synthesis heuristic which provides high quality synthesis results of Toffoli network in more reasonable computation time. We use a weighted, directed graph for reversible function representation and complexity measurement. The proposed algorithm maximally decreases function complexity during synthesis steps. It has the ability to climb out of local minimums and guarantees algorithm convergence. The experimental results show that our algorithm can achieve optimal or very close to optimal solutions with computation time several orders of magnitude less than the exact methods. Compared with other heuristics, our method demonstrates superior performance in terms of reversible gate count as well as computation time.

Asia and South Pacific Design Automation Conference (ASP-DAC)Jan 1, 200912 citations

Templates for Toffoli Network Synthesis

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

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Tooli networks can be divided into two steps. First, nd 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 second step. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation reducing the gate count can be applied. All templates for m 7a re described in this paper.

Jan 1, 200311 citations