Efficient Algorithms for Optimal 4‐Bit Reversible Logic System Synthesis

Zhiqiang Li, Hanwu Chen, Guowu Yang and Wenjie Liu

Journal of Applied Mathematics, 2013, vol. 2013, issue 1

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 n‐bit circuits reaches near 2 × n!. 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.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1155/2013/291410

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:jnljam:v:2013:y:2013:i:1:n:291410

Access Statistics for this article

More articles in Journal of Applied Mathematics from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().