基于汉明距离递减变换的可逆逻辑综合算法  

A Synthesis Algorithm of Reversible Logic Circuit Based on the Decreasing Transform of Hamming Distance

作　　者：陈汉武[1,2] 李文骞[1] 阮越[1,3] 李志强[4] 

机构地区：[1]东南大学计算科学与工程学院,南京210096 [2]东南大学计算机网络和信息集成教育部重点实验室,南京210096 [3]安徽工业大学计算机学院,安徽马鞍山243005 [4]扬州大学信息工程学院,江苏扬州225009

出　　处：《计算机学报》2014年第8期1839-1845,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(60873101;61070240;61170321);高等学校博士学科点专项科研基金(20110092110024);东南大学计算机网络和信息集成教育部重点实验室开放基金资助~~

摘　　要：可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.现有的可逆逻辑综合算法虽然通过后期优化能够得到近似最优解,但是都存在生成的原始电路门数较多的问题,增加了后期优化工作的难度.文中提出一种基于真值表异位数计算的综合方法,根据异位数判定是否需增加逻辑非门达到减少输入和输出向量的汉明距离,从而实现边计算边简化函数,最后采用汉明距离递减变换的方法生成最终的电路.通过实验表明,相比于其他的综合算法,该算法得到的原始电路更接近于最优解或近似最优解,很大程度上减少了算法后续的优化工作量.Synthesis of reversible logic circuit implicates automatically constructing the desired quantum reversible logic circuits.Existing synthesis algorithms of reversible logic,although which can get the approximate optimal solution,are difficult in their optimizing work phase due to the excessive gate count generated in their earlier work phase.In order to reduce the difficulty of optimizing work,a new synthesis algorithm was presented according to the Number of reversible function＇s Different Bits （NDBs） in truth table.The algorithm used NDBs to decide whether the NOT GATE should be added to decrease the Hamming distance of the input and output vectors.By decreasing Hamming distance progressively,the algorithm could be done with computing and simplifying generation function at the same time.The experimental results showed that the original logic circuit we got was closer to optimal solution than other methods,so less optimal work was needed to get final logic circuit.

关 键 词：可逆逻辑综合 扩展Toffoli门 汉明距离 异位数 

分 类 号：TP387[自动化与计算机技术—计算机系统结构]