期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

基于真值表变换的可逆逻辑综合算法 被引量：3

Reversible logic synthesis algorithm based on transformation of truth table
在线阅读 下载PDF
导出
摘要 为实现将给定的二元可逆函数快速综合为相应电路,并保持其结果的最优或较优,提出一种基于真值表变换的快速综合算法.可逆函数与置换同构,任意置换均可表示为若干对换的乘积,通过将可逆函数转化为一系列对换的乘积,从对换的乘积中综合电路.对于3bit逻辑电路只有28种对换,事先将28种对换的最优电路存入库中生成3bit电路综合基,通过在库中查找快速生成可逆电路.根据逻辑门可交换规则引入优化方法,完成快速综合算法.结果表明,该方法不但可以提高可逆逻辑综合的效率,而且结构简单,易于实现,可以O(4n)的时间效率快速综合任意3bit可逆逻辑电路,实现综合结果达到或接近最优. 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 li- brary. Meanwhile, the rules based optimizing method is added to complete the rapid synthesis algo- rithm. 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（4^n） ,making the result reach or close to the optimal.
作者 安博 陈汉武 杨忠明 王冬 李志强
机构地区 东南大学计算机科学与工程学院 河南大学计算中心 扬州大学信息工程学院
出处 《东南大学学报（自然科学版）》 EI CAS CSCD 北大核心 2010年第1期58-63,共6页 Journal of Southeast University：Natural Science Edition
基金 国家自然科学基金资助项目(60572071 60873101) 江苏省自然科学基金资助项目(BM2006504 BK2007104)
关键词 可逆逻辑综合 真值表 对换 规则优化 reversible logic synthesis truth table swapping rules based optimizing
分类号 TP387 [自动化与计算机技术—计算机系统结构]
  • 相关文献

参考文献11

  • 1Deutsch D. Quantum theory, the church-turing principle and the universal quantum computer [ C]//Proceedings of the Royal Society. London, 1985,400 ( 1818 ) : 97 - 117.
  • 2Shende 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.
  • 3Maslov 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.
  • 4Shende 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.
  • 5Song 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. 被引量：3
  • 7Yang 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. 被引量：2
  • 9Miller 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.
  • 10Li W Q, Wang J J, Chen H W, et al. Application of template technique in optimizing quantum logical circuit [ C ]//Proceedings of the 11 th International Conference on CSCWD. Melbourne, Australia, 2007 : 155 - 161.

二级参考文献24

  • 1何雨果,孙吉贵.基于Haar小波的多尺度分析量子电路[J].科学通报,2005,50(20):2314-2316. 被引量：5
  • 2Fredkin E, Toffoli T. Conservative logic. International Journal of Theoretical Physics, 1982,21:219-253
  • 3Shende V V, Prasad A K, Markov I L,et al. Reversible logic circuit synthesis. In: Proceedings of the International Conference on Computer-Aided Design, California, 2002. 125-132
  • 4Song X Y, Yang G W, Perkowski M,et al. Algebraic characteristics of reversible gates. Theory of Computing Systems, 2004. 311-319
  • 5Shende V V, Prasad A K, Markov I L,et al. Synthesis of reversible logic circuits. In,IEEE Transactions on Circuits and Systems-Ⅰ, 2003, 22(6):723-729
  • 6Iwama K, Kambayashi Y, Yamashita S. Transformation rules for designing CNOT-based quantum circuits. In: Proceedings of Design Automation Conference, New Orleans, 2002, 28(4):419-424
  • 7Miller D M, Maslov D, Gueck G W. Spectral and two-place decomposition techniques in reversible logic. In: Proceedings of the 45th IEEE International Midwest Symposium on Circuits and Systems, Tulsa, 2002. 493-496
  • 8Miller D M. A transformation based algorithm for reversible logic synthesis. In: Proceedings of the International Conference on Computer-Aided Design, California, 2003. 318-323
  • 9Maslov D, Dueck G W, Miller D M. Toffoli network synthesis with templates. IEEE Transaetions on Cireuits and Systems-Ⅰ, 2005, 24(6) : 807-817
  • 10Mishchenko A, Perkowski M. Logic synthesis of reversible wave cascades. In: Proceedings of 11th IEEE International Workshop on Logic Synthesis, New Orleans, 2002. 197-202

共引文献2

同被引文献28

  • 1莫丽君.真值表在形式逻辑中的功能[J].辽宁工程技术大学学报（社会科学版）,2004,6(3):232-233. 被引量：2
  • 2陈宁,冯博琴.基于命题逻辑的组件约束检测[J].西安交通大学学报,2007,41(2):172-175. 被引量：2
  • 3朱晓波,杨伟民,叶芯.更改条件/判定覆盖最小真值表生成算法及其应用[J].上海理工大学学报,2007,29(1):84-88. 被引量：8
  • 4魏贵民,邹辉.全功能联结词集合的计算机实现[J].成都理工大学学报（自然科学版）,2007,34(3):359-363. 被引量：1
  • 5Fredkin E, Toffoli T. Conservative logic [ J ]. Interna- tional Journal of Theoretical Physics, 1982, 21 ( 3 ) :219 - 253.
  • 6Song X Y, Yang G W, Perkowski M. Algebraic char- acteristics of reversible gates [ J ]. Theory of Computing Systems, 2004, 37(2) :311 -319.
  • 7Iwama K, Kambayashi Y, Yamashita S. Transformation rules for designing CNOT-based quantum circuits [ C ]// Proceedings of the 39th Annual Design Automation Con- ference. New York, USA, 2002 : 419 - 424.
  • 8Maslov D, Dueck G W, Miller D M. Toffoli network synthesis with templates [ J ]. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Sys- tems, 2005, 24(6) : 807-817.
  • 9Shende 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.
  • 10Yang G W, Song X Y, Perkowski M, et al. Fast syn- thesis of exact minimal reversible circuits using group theory[ C ]//Proceedings of 2005 1EEE ASP-DAC. Shanghai, China, 2005 : 18 -21.

引证文献3

东南大学学报（自然科学版）
2010年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部