基于带权有向图的可逆逻辑综合改进算法  

Improved reversible logic synthesis algorithm based on weighted directed graph

作　　者：程学云[1] 管致锦[1] 

机构地区：[1]南通大学计算机科学与技术学院,江苏南通226019

出　　处：《计算机工程与设计》2012年第11期4214-4218,4304,共6页Computer Engineering and Design

基　　金：国家自然科学基金项目(60873069);南通市应用研究计划基金项目(K2010004)

摘　　要：为减少可逆逻辑综合中使用的可逆门,通过对基于带权有向图的可逆逻辑综合算法的分析,针对函数转换过程中过渡门数较多及电路优化算法简单的问题,提出了有效的等复杂度基本输出变换的概念,扩充并证明了Toffoli门序列的移动和化简规则,给出了改进的基于带权有向图的可逆逻辑综合算法。实验结果表明,该算法不仅减少了可逆电路构成时所使用的可逆门,而且对构建的可逆电路实现了有效化简,大幅度减少了门数和控制位数,降低了可逆电路代价。To reduce the number of reversible gates used in the reversible logic synthesis, by analyzing the reversible logic synthesis algorithm based on the weighted direction gragh （WDG）, the number of transitional gates in the process of function transformation is more and the optimization algorithm is simple, so the concept of efficient complexity-equal primitive output transformation （POT） is proposed, the moving and simplification rules for Toffoli gate sequence are expanded and proven, and the improved synthesis algorithm based on WDG is given. Experimental results show that the improved algorithm can not only reduce the number of reversible gates during circuit generation, but also optimize the generated circuit effectively, the number of gates and control bits is reduced greatly, and the circuit cost is decreased.

关 键 词：可逆逻辑综合 带权有向图 Toffoli门 函数复杂性 基本输出变换 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]