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

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

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.现有的可逆逻辑综合算法虽然通过后期优化能够得到近似最优解,但是都存在生成的原始电路门数较多的问题,增加了后期优化工作的难度.文中提出一种基于真值表异位数计算的综合方法,根据异位数判定是否需增加逻辑非门达到减少输入和输出向量的汉明距离,从而实现边计算边简化函数,最后采用汉明距离递减变换的方法生成最终的电路.通过实验表明,相比于其他的综合算法,该算法得到的原始电路更接近于最优解或近似最优解,很大程度上减少了算法后续的优化工作量.

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.