基于规则的可逆Toffoli电路优化算法

摘要：

可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.

关键词：可逆逻辑综合、可逆函数、Toffoli门、可逆电路优化

所属期刊栏目：40

分类号：TP302(计算技术、计算机技术)

资助基金：国家自然科学基金60873069;江苏省高校自然科学基金12KJB520013;南通市应用研究计划BK2013043

在线出版日期：2013-11-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：32-38