可逆逻辑作为量子计算，纳米技术，低功耗设计等新兴技术的基础，近年来得到了越来越多的关注和研究.然而，大多数可逆逻辑综合方法对函数真值表表达形式的依赖使得综合电路规模受到了限制.决策图作为一种更加简洁的布尔函数表示方法，其为可逆逻辑综合提供了另一种途径.本文基于Kronecker函数决策图(KFDD)提出了一种适合于综合大规模电路的综合方法.该方法利用KFDD描述功能函数，以局部最优的方式从三种节点分解方法中寻找最优分解方法，并根据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.
关键词
可逆逻辑电路综合 /
Kronecker函数决策图 /
节点分解方法 /
分解类型表
{{custom_keyword}} /
Key words
reversible logic circuit synthesis /
Kronecker functional decision diagram /
node decomposition types /
decomposition type list
{{custom_keyword}} /
中图分类号：
TP387
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[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.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
航空科学基金 (No.2011ZD52050)
{{custom_fund}}
PDF(1082 KB)
