摘要
为减少可逆逻辑综合中使用的可逆门,通过对基于带权有向图的可逆逻辑综合算法的分析,针对函数转换过程中过渡门数较多及电路优化算法简单的问题,提出了有效的等复杂度基本输出变换的概念,扩充并证明了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.
出处
《计算机工程与设计》
CSCD
北大核心
2012年第11期4214-4218,4304,共6页
Computer Engineering and Design
基金
国家自然科学基金项目(60873069)
南通市应用研究计划基金项目(K2010004)
关键词
可逆逻辑综合
带权有向图
Toffoli门
函数复杂性
基本输出变换
reversible logic synthesis
weighted direction graph
Toffoli gates
function complexity
primitive output transfor-mation （POT）
