Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis
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 algorithm...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2013-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2013/291410 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832567125909176320 |
|---|---|
| author | Zhiqiang Li Hanwu Chen Guowu Yang Wenjie Liu |
| author_facet | Zhiqiang Li Hanwu Chen Guowu Yang Wenjie Liu |
| author_sort | Zhiqiang Li |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-bd3484dc61af49199438746cf91b2a3b |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2013-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-bd3484dc61af49199438746cf91b2a3b2025-02-03T01:02:18ZengWileyJournal of Applied Mathematics1110-757X1687-00422013-01-01201310.1155/2013/291410291410Efficient Algorithms for Optimal 4-Bit Reversible Logic System SynthesisZhiqiang Li0Hanwu Chen1Guowu Yang2Wenjie Liu3College of Information Engineering, Yangzhou University, Yangzhou 225009, ChinaSchool of Computer Science and Engineering, Southeast University, Nanjing 211189, ChinaUniversity of Electronic Science and Technology Chengdu, Sichuan, Chengdu 611731, ChinaNanjing University of Information Science & Technology, Nanjing 210044, ChinaOwing 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.http://dx.doi.org/10.1155/2013/291410 |
| spellingShingle | Zhiqiang Li Hanwu Chen Guowu Yang Wenjie Liu Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis Journal of Applied Mathematics |
| title | Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis |
| title_full | Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis |
| title_fullStr | Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis |
| title_full_unstemmed | Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis |
| title_short | Efficient Algorithms for Optimal 4-Bit Reversible Logic System Synthesis |
| title_sort | efficient algorithms for optimal 4 bit reversible logic system synthesis |
| url | http://dx.doi.org/10.1155/2013/291410 |
| work_keys_str_mv | AT zhiqiangli efficientalgorithmsforoptimal4bitreversiblelogicsystemsynthesis AT hanwuchen efficientalgorithmsforoptimal4bitreversiblelogicsystemsynthesis AT guowuyang efficientalgorithmsforoptimal4bitreversiblelogicsystemsynthesis AT wenjieliu efficientalgorithmsforoptimal4bitreversiblelogicsystemsynthesis |