-
题名基于规则的可逆Toffoli电路优化算法
被引量:5
- 1
-
-
作者
程学云
管致锦
张海豹
丁卫平
-
机构
南通大学计算机科学与技术学院
南通大学电子信息学院
-
出处
《计算机科学》
CSCD
北大核心
2013年第10期32-38,共7页
-
基金
国家自然科学基金(60873069)
江苏省高校自然科学基金(12KJB520013)
南通市应用研究计划(BK2013043)资助
-
文摘
可逆电路的优化是可逆逻辑综合的关键问题之一。为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法。根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止。该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3)。在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价。
-
关键词
可逆逻辑综合
可逆函数
Toffoli门
可逆电路优化
-
Keywords
Reversible logic synthesis, Reversible function, Toffoli gate, Optimization of reversible circuit
-
分类号
TP302
[自动化与计算机技术—计算机系统结构]
-