A Novel Transformation-Based Algorithm for Reversible Logic Synthesis

Reversible logic studies have promising potential on energy lossless circuit design, quantum computation, nanotechnology, etc. This paper proposes an analogic selection sorting algorithm essentially based on the transformation-based algorithm. It uses an unweighted, undirected graph for the representation of all transformable paths. During the synthesis process, a sequence of transformations are performed to enable all the output patterns to appear in the right place. The whole process can be implemented by a sequence of Toffoli gates. In addition, a simplification algorithm is put forward to further optimize the generated circuit. The experimental results show that this algorithm, compared with other exact methods, can achieve optimal or nearly optimal solutions with less computation time. Furthermore, it is more easily understood and implemented.