中文摘要：

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.由于搜索空间随电路规模增长成指数增长,现有的可逆逻辑综合算法虽然能够得到近似最优的解,但是都存在计算时间过长的问题.文中提出了一种类似选择排序的可逆逻辑综合算法,其实质为基于变换规则的合成法.它采用一个无向无权图表示所有可以进行变换的路径,在综合的过程中,采用选择排序思想每次从小到大的选择需要交换的输出项,然后从路径选择图中找到最优的路径进行变换,最终使得函数的输出序列有序即完成综合.此外,文中还对得到的量子电路进行了优化.实验表明,相比其它综合算法,该算法不仅总能获得最优解或近似最优解,而且效率高、易于实现.

英文摘要：

Reversible logic studies have promising potential on energy lossless circuit design,quantum computation,nanotechnology,etc.Though existing synthesis methods can provide optimal solutions,yet they may suffer from long computation time,due to the fact that the search space is likely to grow exponentially as the circuit size increases.Therefore,in this paper,the authors propose an analogic selection sorting algorithm essentially based on the transformation-based algorithm.An unweighted,undirected graph is used for the representation of all transformable paths.During the synthesis process,a sequence of transformation is built to make all the output patterns appeared in the right place.The whole process can be implemented by a sequence of Toffoli gates.In addition,the authors propose a simplification algorithm to further optimize the generated circuit.The experimental results show that the algorithm,compared with other exact methods,can achieve optimal or very close to optimal solutions with less computation time.Furthermore,the algorithm is more easily understood and implemented.