[1]李志钢,陈汉武,李志强,等.基于对换门库的可逆逻辑电路综合算法[J].东南大学学报(自然科学版),2012,42(5):832-836.[doi:10.3969/j.issn.1001-0505.2012.05.007]
 Li Zhigang,Chen Hanwu,Li Zhiqiang,et al.Reversible logic circuit synthesis algorithm based on transposition gate library[J].Journal of Southeast University (Natural Science Edition),2012,42(5):832-836.[doi:10.3969/j.issn.1001-0505.2012.05.007]
点击复制

基于对换门库的可逆逻辑电路综合算法()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
42
期数:
2012年第5期
页码:
832-836
栏目:
计算机科学与工程
出版日期:
2012-09-20

文章信息/Info

Title:
Reversible logic circuit synthesis algorithm based on transposition gate library
作者:
李志钢1 陈汉武12 李志强3 朱皖宁1 刘志昊1
1 东南大学计算机科学与工程学院,南京 211189; 2 东南大学计算机网络和信息集成教育部重点实验室, 南京 211189; 3 扬州大学信息工程学院,扬州 225009
Author(s):
Li Zhigang1 Chen Hanwu12 Li Zhiqiang3 Zhu Wanning1 Liu Zhihao1
1 School of Computer Science and Engineering, Southeast University, Nanjing 211189, China
2 Key Laboratory of Computer Network and Information Integration of Ministry of Education, Southeast University, Nanjing 211189, China
3 College of Information Engineering, Yangzhou University, Yangzhou 225009, China
关键词:
量子可逆逻辑综合 置换群规则 对换门库 优化规则
Keywords:
quantum reversible logic circuits synthesis permutation group rules transposition gate library optimization rules
分类号:
TP301
DOI:
10.3969/j.issn.1001-0505.2012.05.007
摘要:
为了将可逆函数以较小的代价自动构造为对应的可逆逻辑电路,提出了一种基于对换门库的综合算法.首先,将可逆函数的输出作为快速排序算法的输入数据,在排序算法中按顺序保留所交换的元素对,并输出该元素对序列; 其次,利用置换群规则对该序列进行优化处理,获得相似度最高的对换序列; 然后,逆序排列该对换序列,并基于对换门库生成可逆函数的初始电路; 最后,应用电路门优化规则,对初始电路进行优化,得到最终的可逆逻辑电路.相比于其他算法,所提算法明显提高了可逆逻辑综合效率,其思想的简洁性使得算法更易于理解和实现.
Abstract:
To automatically construct desired quantum reversible logic circuit with minor quantum cost, an synthesis algorithm based on the transposition gate library(TGL)is presented. First, the output of the reversible function is taken as the input of the quick sort algorithm(QSA). The order of elements pairs which are swapped in the QSA are retained in order, and the sequence of elements pairs is as the output. Secondly, the sequence is optimized according to the permutation group rules to get a new one in which the similarity is highest among pairs. Thirdly, the new sequence is reversed and the initial circuit is generated based on the TGL. Finally, according to the gate optimization rules, the initial circuit is optimized to get the final reversible logic circuit. Compared with other algorithms, the proposed one has higher efficiency of synthesis of quantum reversible logic circuits. Due to its concise idea, it is easy to understand and realize.

参考文献/References:

[1] Fredkin E,Toffoli T.Conservative logic[J].International Journal of Theoretical Physics,1982,21(3):219-253.
[2] Song X Y,Yang G W,Perkowski M.Algebraic characteristics of reversible gates[J].Theory of Computing Systems,2004,37(2):311-319.
[3] Iwama K,Kambayashi Y,Yamashita S.Transformation rules for designing CNOT-based quantum circuits[C] //Proceedings of the 39th Annual Design Automation Conference.New York,USA,2002:419-424.
[4] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems,2005,24(6):807-817.
[5] Shende V V,Prasad A K,Markov I L,et al.Reversible logic circuit synthesis[C] //Proceedings of 2002 IEEE/ACM International Conference on Computer-Aided Design.New Orleans,Louisiana,USA,2002:125-132.
[6] Yang G W,Song X Y,Perkowski M,et al.Fast synthesis of exact minimal reversible circuits using group theory[C] //Proceedings of 2005 IEEE ASP-DAC.Shanghai,China,2005:18-21.
[7] 安博,陈汉武,杨忠明,等.基于真值表变换的可逆逻辑综合算法[J].东南大学学报:自然科学版,2010,40(1):58-63.
  An Bo,Chen Hanwu,Yang Zhongming,et al.A reversible logic synthesis algorithm based on the transformation of truth table[J].Journal of Southeast University:Natural Science Edition,2010,40(1):58-63.(in Chinese)
[8] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis [C] //Proceedings of the 40th Annual Design Automation Conference.Anaheim,CA,USA,2003:318-323.
[9] 万四爽,陈汉武,曹如进.类选择排序的可逆逻辑综合算法[J].计算机学报,2010,33(12):2343-2352.
  Wan Sishuang,Chen Hanwu,Cao Rujin.An analogic selection sorting algorithm for synthesis of reversible logic circuits[J].Chinese Journal of Computer,2010,33(12):2343-2352.(in Chinese)
[10] 李志强,陈汉武,徐宝文,等.量子可逆逻辑电路综合的快速算法研究[J].计算机学报,2009,32(7):1291-1303.
  Li Zhiqiang,Chen Hanwu,Xu Baowen,et al.A fast algorithm for synthesis of quantum reversible logic circuits[J].Chinese Journal of Computer,2009,32(7):1291-1303.(in Chinese)
[11] Bennett C.Logical reversibility of computation[J].IBM Journal of Research and Development,1973,17(6):525-532.

备注/Memo

备注/Memo:
作者简介: 李志钢(1985—),男,博士生; 陈汉武(联系人),男,博士,教授,博士生导师,hw_chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60873101,61070240,61170321)、高等学校博士学科点专项科研基金资助项目(20110092110024).
引文格式: 李志钢,陈汉武,李志强,等.基于对换门库的可逆逻辑电路综合算法[J].东南大学学报:自然科学版,2012,42(5):832-836. [doi:10.3969/j.issn.1001-0505.2012.05.007]
更新日期/Last Update: 2012-09-20