Exact Synthesis of Reversible Circuits Using A* Algorithm
详细信息 查看全文
- 作者：K. Datta (1)
- 关键词：Reversible logic synthesis ; A* algorithm ; Quantum cost
- 刊名：Journal of The Institution of Engineers (India): Series B
- 出版年：2015
- 出版时间：June 2015
- 年：2015
- 卷：96
- 期：2
- 页码：121-130
- 全文大小：454 KB
- 参考文献：1. Rabaey, JM (2009) Low Power Design Essentials. Springer, Series on Integrated Circuits and Systems, New York
- 刊物主题：Communications Engineering, Networks;
- 出版者：Springer India
- ISSN：2250-2114
文摘
With the growing emphasis on low-power design methodologies, and the result that theoretical zero power dissipation is possible only if computations are information lossless, design and synthesis of reversible logic circuits have become very important in recent years. Reversible logic circuits are also important in the context of quantum computing, where the basic operations are reversible in nature. Several synthesis methodologies for reversible circuits have been reported. Some of these methods are termed as exact, where the motivation is to get the minimum-gate realization for a given reversible function. These methods are computationally very intensive, and are able to synthesize only very small functions. There are other methods based on function transformations or higher-level representation of functions like binary decision diagrams or exclusive-or sum-of-products, that are able to handle much larger circuits without any guarantee of optimality or near-optimality. Design of exact synthesis algorithms is interesting in this context, because they set some kind of benchmarks against which other methods can be compared. This paper proposes an exact synthesis approach based on an iterative deepening version of the A* algorithm using the multiple-control Toffoli gate library. Experimental results are presented with comparisons with other exact and some heuristic based synthesis approaches.