[1]安博,陈汉武,杨忠明,等.基于真值表变换的可逆逻辑综合算法[J].东南大学学报(自然科学版),2010,40(1):58-63.[doi:10.3969/j.issn.1001-0505.2010.01.011]
　An Bo,Chen Hanwu,Yang Zhongming,et al.Reversible logic synthesis algorithm based on transformation of truth table[J].Journal of Southeast University (Natural Science Edition),2010,40(1):58-63.[doi:10.3969/j.issn.1001-0505.2010.01.011]
点击复制

基于真值表变换的可逆逻辑综合算法()
分享到：

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

卷:
40
期数:
2010年第1期
页码:
58-63
栏目:
计算机科学与工程
出版日期:
2010-01-20

文章信息/Info

Title:
Reversible logic synthesis algorithm based on transformation of truth table
作者:
安博1;  陈汉武1;  杨忠明1;  王冬1; 2;  李志强1; 3
1 东南大学计算机科学与工程学院,南京 210096; 2 河南大学计算中心,开封 415002; 3 扬州大学信息工程学院, 扬州 225009
Author(s):
An Bo1;  Chen Hanwu1;  Yang Zhongming1;  Wang Dong1; 2;  Li Zhiqiang1; 3
1 School of Computer Science and Engineering,Southeast University,Nanjing 210096,China
2 Computer Center,Henan University,Kaifeng 415002,China
3 College of Information Engineering,Yangzhou University,Yangzhou 22500
关键词:
可逆逻辑综合;  真值表;  对换;  规则优化
Keywords:
reversible logic synthesis;  truth table;  swapping;  rules based optimizing
分类号:
TP387
DOI:
10.3969/j.issn.1001-0505.2010.01.011
摘要:
为实现将给定的二元可逆函数快速综合为相应电路,并保持其结果的最优或较优,提出一种基于真值表变换的快速综合算法.可逆函数与置换同构,任意置换均可表示为若干对换的乘积,通过将可逆函数转化为一系列对换的乘积,从对换的乘积中综合电路.对于3 bit逻辑电路只有28种对换,事先将28种对换的最优电路存入库中生成3 bit电路综合基,通过在库中查找快速生成可逆电路.根据逻辑门可交换规则引入优化方法,完成快速综合算法.结果表明,该方法不但可以提高可逆逻辑综合的效率,而且结构简单,易于实现,可以O(4n)的时间效率快速综合任意3 bit可逆逻辑电路,实现综合结果达到或接近最优.
Abstract:
To realize the synthesis of a certain reversible function rapidly,and make the result optimal or better, an algorithm based on the transformation of the truth table is proposed. A reversible function is isomorphic to a permutation and an arbitrary permutation can be expressed as a product of a series of swapping, thus the circuits can be generated in the product. Only 28 kinds of swapping exist for the 3 bit circuits,whose corresponding circuit blocks are stored into a library in advance as the bases of 3 bit circuits.Reversible logic circuits can be generated speedily by searching in this library.Meanwhile,the rules based optimizing method is added to complete the rapid synthesis algorithm.The results show that this algorithm can improve the efficiency of synthesizing the reversible logic circuits. It is easy to realize and with simple structure.It can synthesize arbitrary reversible logic circuits rapidly with the time complexity of O(4n),making the result reach or close to the optimal.

参考文献/References:

[1] Deutsch D.Quantum theory,the church-turing principle and the universal quantum computer[C] //Proceedings of the Royal Society.London,1985,400(1818):97-117.
[2] Shende V V,Prasad A K,Markov I L,et al.Reversible logic circuit synthesis[C] //Proceedings of the International Conference on Computer-Aided Design.San Jose,CA,USA,2002:125-132.
[3] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems,2005,24(6):807-817.
[4] Shende V V,Prasad A K,Markov I L,et al.Synthesis of reversible logic circuits[J].IEEE Trans on Computer-Aided Design of Integrated Circuits and Systems,2003,22(6):723-729.
[5] Song X Y,Yang G W,Perkowski M,et al.Algebraic characteristics of reversible gates[J].Theory of Computing Systems,2004,37(2):311-319.
[6] 李志强,陈汉武,李文骞.基于位运算的量子可逆逻辑电路快速综合算法[J].计算机科学,2008,35(3):13-17.
　 Li Zhiqiang,Chen Hanwu,Li Wenqian.Speedy algorithm for synthesis of quantum reversible logic circuits based on bit operation[J].Computer Science,2008,35(3):13-17.(in Chinese)
[7] Yang G W,Song X Y,Hung W N N,et al.Group theory based synthesis of binary reversible circuits[C] //Proceedings of the 3rd International Conference on Theory and Applications of Models of Computation.Beijing,China,2006:365-374.
[8] 陈汉武,李志强,徐宝文.置换群与整数间一对一Hash函数的构建[J].东南大学学报:自然科学版,2008,38(2):225-227.
　 Chen Hanwu,Li Zhiqiang,Xu Baowen.Construction of one-for-one Hash function mapping between permutation group and integral number[J].Journal of Southeast University:Natural Science Edition,2008,38(2):225-227.(in Chinese)
[9] Miller D M,Maslov D,Dueck G W.A transformation based algorithm for reversible logic synthesis[C] //Proceedings of the 40th Design Automation Conference.Anaheim,CA,USA,2003:318-323.
[10] Li W Q,Wang J J,Chen H W,et al.Application of template technique in optimizing quantum logical circuit[C] //Proceedings of the 11th International Conference on CSCWD.Melbourne,Australia,2007:155-161.
[11] Iwama K,Kambayashi Y,Yamashita S.Transformation rules for designing CNOT-based quantum circuits[C] //Proceedings of Design Automation Conference.New Orleans,LA,USA,2002,28(4):419-425.

备注/Memo

备注/Memo:
作者简介: 安博(1986—),男,硕士生; 陈汉武(联系人),男,博士,教授,博士生导师,hw_chen@seu.edu.cn.
基金项目: 国家自然科学基金资助项目(60572071,60873101)、江苏省自然科学基金资助项目(BM2006504,BK2007104).
引文格式: 安博,陈汉武,杨忠明,等.基于真值表变换的可逆逻辑综合算法[J].东南大学学报:自然科学版,2010,40(1):58-63. [doi:10.3969/j.issn.1001-0505.2010.01.011]
更新日期/Last Update: 2010-01-20