# [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] 点击复制 基于真值表变换的可逆逻辑综合算法() 分享到： var jiathis_config = { data_track_clickback: true };

40

2010年第1期

58-63

2010-01-20

## 文章信息/Info

Title:
Reversible logic synthesis algorithm based on transformation of truth table

1 东南大学计算机科学与工程学院,南京 210096; 2 河南大学计算中心,开封 415002; 3 扬州大学信息工程学院, 扬州 225009
Author(s):
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:

TP387
DOI:
10.3969/j.issn.1001-0505.2010.01.011

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.