Journal of Applied Mathematics
Volume 2013 (2013), Article ID 291410, 8 pages
http://dx.doi.org/10.1155/2013/291410
Research Article

Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis

Zhiqiang Li,1 Hanwu Chen,2 Guowu Yang,3 and Wenjie Liu4

1College of Information Engineering, Yangzhou University, Yangzhou 225009, China
2School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
3University of Electronic Science and Technology Chengdu, Sichuan, Chengdu 611731, China
4Nanjing University of Information Science & Technology, Nanjing 210044, China

Received 8 February 2013; Accepted 23 February 2013

Academic Editor: Xiaoyu Song

Copyright © 2013 Zhiqiang Li et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

Owing to the exponential nature of the memory and run-time complexity, many methods can only synthesize 3-bit reversible circuits and cannot synthesize 4-bit reversible circuits well. We mainly absorb the ideas of our 3-bit synthesis algorithms based on hash table and present the efficient algorithms which can construct almost all optimal 4-bit reversible logic circuits with many types of gates and at mini-length cost based on constructing the shortest coding and the specific topological compression; thus, the lossless compression ratio of the space of -bit circuits reaches near . This paper presents the first work to create all 3120218828 optimal 4-bit reversible circuits with up to 8 gates for the CNT (Controlled-NOT gate, NOT gate, and Toffoli gate) library, and it can quickly achieve 16 steps through specific cascading created circuits.