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 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. © 2013 zhiqiang li et al.