基于KFDD的可逆逻辑电路综合设计方法

doi:10.3969/j.issn.0372-2112.2014.05.031

电子学报

基于KFDD的可逆逻辑电路综合设计方法

王友仁, 沈先坤, 周影辉

南京航空航天大学自动化学院, 江苏南京 210016

收稿日期:2013-03-29 修回日期:2013-07-24 出版日期:2014-05-25
- 作者简介:
- 王友仁 男，1963年生，博士、教授、博士生导师，研究方向为电路理论、信号处理、进化硬件、故障诊断预测、智能系统等. E-mail:wangyrac@nuaa.edu.cn沈先坤男，1987年生，南京航空航天大学自动化学院硕士研究生，研究方向为量子可逆逻辑电路综合技术. E-mail:245931823@qq.com
- 基金资助:
- 航空科学基金 (No.2011ZD52050)

Synthesis Design Method of Reversible Logic Circuit Based on Kronecker Functional Decision Diagram

WANG You-ren, SHEN Xian-kun, ZHOU Ying-hui

College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing, Jiangsu 210016, China

Received:2013-03-29 Revised:2013-07-24 Online:2014-05-25 Published:2014-05-25

摘要/Abstract

摘要： 可逆逻辑作为量子计算，纳米技术，低功耗设计等新兴技术的基础，近年来得到了越来越多的关注和研究.然而，大多数可逆逻辑综合方法对函数真值表表达形式的依赖使得综合电路规模受到了限制.决策图作为一种更加简洁的布尔函数表示方法，其为可逆逻辑综合提供了另一种途径.本文基于Kronecker函数决策图(KFDD)提出了一种适合于综合大规模电路的综合方法.该方法利用KFDD描述功能函数，以局部最优的方式从三种节点分解方法中寻找最优分解方法，并根据Kronecker函数决策图中不同类型的节点构建相应的可逆逻辑电路模块，最后将各节点替换电路模块实现级联得到结果电路.以可逆基准电路为例，对该方法进行了验证.实验结果表明，该方法能以较低的代价实现对较大规模函数的可逆逻辑电路综合.

关键词: 可逆逻辑电路综合, Kronecker函数决策图, 节点分解方法, 分解类型表

Abstract: Reversible logic has obtained more and more attention and research as the basis for several emerging technologies such as quantum computing,nanotechnologies and low-power design.However,currently most synthesis algorithms for reversible circuits suffer from being restricted to deal with relatively small functions only,since they rely on a truth table representation of the function to be synthesized.Decision Diagram serving as a more compact Boolean function description provides anther way to synthesis of reversible logic.Here,a synthesis approach based on Kronecker Functional Decision Diagram (KFDD) is proposed,that generates KFDD for a logic function by means of choosing the local optimal one from three alternative node decomposition types.Finally,the result circuit can be produced by substituting all nodes of the KFDD with circuit modules and cascading them.Verified by reversible benchmarks,experiments show the adaption of the proposed approach to large functions with better results.

Key words: reversible logic circuit synthesis, Kronecker functional decision diagram, node decomposition types, decomposition type list

中图分类号:

TP387

王友仁, 沈先坤, 周影辉. 基于KFDD的可逆逻辑电路综合设计方法[J]. 电子学报, DOI: 10.3969/j.issn.0372-2112.2014.05.031.

WANG You-ren, SHEN Xian-kun, ZHOU Ying-hui. Synthesis Design Method of Reversible Logic Circuit Based on Kronecker Functional Decision Diagram[J]. Acta Electronica Sinica, DOI: 10.3969/j.issn.0372-2112.2014.05.031.

参考文献

[1] Donald J,Jha N K.Reversible logic synthesis with Fredkin and Peres gates[J].ACM Journal on Emerging Technologies in Computing Systems (JETC),2008,4(1):2.
[2] Maslov D,Dueck G W,Miller D M.Toffoli network synthesis with templates[J].IEEE Transactions on Circuits and Systems,2005,24(6):807-817.
[3] Saeedi M,Sedighi M,Zamani M S.Synthesis of reversible circuits using a moving forward strategy[J].IEICE Electronics Express,2008,5(17):638-643.
[4] Datta K,Rathi G,Sengupta I,et al.Synthesis of reversible circuits using heuristic search method [A].Proceedings of 2012 25th International Conference on VLSI Design [C].Piscataway,NJ:IEEE,2012.328-333.
[5] Wille R,Drechsler R.Effect of BDD optimization on synthesis of reversible and quantum logic [J].Electronic Notes in Theoretical Computer Science,2010,253(6):57-70.
[6] 王友仁，黄媛媛，冯冉，等.基于矩阵编码的量子可逆逻辑电路进化设计方法[J].电子学报，2011，39(11)：2576-2582. Wang Youren,Huang Yuanyuan,Feng Ran.Evolutionary design technology of quantum reversible logic circuit based on matrix coding[J].Acta Electronica Sinica,2011,39(11):2576-2582.(in Chinese)
[7] Kerntopf P.A new heuristic algorithm for reversible logic synthesis[A].Proceedings of the 41st annual Design Automation Conference[C].New York:ACM,2004.834-837.
[8] Wille R,Drechsler R.BDD-based synthesis of reversible logic for large functions[A].Proceedings of the 46th Annual Design Automation Conference[C].New York:ACM,2009.270-275.
[9] Pang Y,Wang S,He Z,et al.Positive Davio-based synthesis algorithm for reversible logic[A].Proceedings of 2011 IEEE 29th International Conference on Computer Design[C] .Piscataway,NJ:IEEE,2011.212-218.
[10] Drechsler R,Becker B.Ordered Kronecker functional decision diagrams——a data structure for representation and manipulation of boolean functions [J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,1998,17(10):965-973.
[11] Wille R,Groβe D,Teuber L,et al.RevLib:An online resource for reversible functions and reversible circuits[A].Proceedings of 38th International Symposium on Multiple Valued[C].Piscataway,NJ:IEEE,2008.220-225.

[1]	卜登立, 郭鸣. 基于布尔表达式图的可逆电路综合方法[J]. 电子学报, 2020, 48(3): 494-502.
[2]	卜登立. 基于ESOP最大加权输出相容类的可逆电路综合方法[J]. 电子学报, 2018, 46(8): 1866-1875.
[3]	朱皖宁, 刘志昊. 基于量子计算的用户识别算法[J]. 电子学报, 2018, 46(1): 24-30.
[4]	朱皖宁, 陈汉武. 迭代次数自适应的Grover算法[J]. 电子学报, 2016, 44(12): 2975-2980.
[5]	薛希玲, 李文骞, 陈汉武, 刘志昊. 基于Grover硬币算子的量子行走在商图上的演化算子[J]. 电子学报, 2016, 44(3): 555-559.
[6]	王冬, 朱长江, 张晓蕾. 量子三值全加器设计[J]. 电子学报, 2014, 42(7): 1452-1456.
[7]	朱皖宁, 陈汉武, 李志钢, 阮越, 王冬, 周刚. 基于NCP门库的一维量子行走可逆逻辑电路[J]. 电子学报, 2013, 41(1): 91-97.
[8]	杨忠明;陈汉武;王冬;. 基于二分法量子可逆逻辑电路综合[J]. 电子学报, 2012, 40(5): 1045-1049.
[9]	陈雄;陈汉武;刘志昊;李志强. 基于状态向量表示的快速量子仿真算法[J]. 电子学报, 2011, 39(3): 500-504.
[10]	王冬;陈汉武;安博;杨忠明. 基于矩阵初等变换的四量子比特可逆电路综合算法[J]. 电子学报, 2010, 38(11): 2561-2565.
[11]	肖芳英;陈汉武;刘志昊;李志强;刘文杰;. 有限域上非本原BCH码的对偶包含判定[J]. 电子学报, 2010, 38(8): 1858-1861.
[12]	汪鹏君;李辉;吴文晋;王伶俐;张小颖;戴静. 量子遗传算法在多输出Reed-Muller逻辑电路最佳极性搜索中的应用[J]. 电子学报, 2010, 38(5): 1058-1063.
[13]	薛希玲;陈汉武;刘志昊;李志强;. 量子线路仿真的分治算法[J]. 电子学报, 2010, 38(2): 439-442.
[14]	李志强;陈汉武;徐宝文;肖芳英;薛希玲. 四量子可逆逻辑电路快速综合算法[J]. 电子学报, 2008, 36(11): 2081-2089.

基于KFDD的可逆逻辑电路综合设计方法

Synthesis Design Method of Reversible Logic Circuit Based on Kronecker Functional Decision Diagram

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics