| 基于规则的可逆Toffoli电路优化算法 |
| |
| 引用本文： | 程学云,管致锦,张海豹,丁卫平. 基于规则的可逆Toffoli电路优化算法[J]. 计算机科学, 2013, 40(10): 32-38 |
| |
| 作者姓名： | 程学云 管致锦 张海豹 丁卫平 |
| |
| 作者单位： | 1. 南通大学计算机科学与技术学院 南通 226019
2. 南通大学电子信息学院 南通 226019 |
| |
| 基金项目： | 本文受国家自然科学基金(60873069),江苏省高校自然科学基金(12KJB520013),南通市应用研究计划(BK2013043)资助 |
| |
| 摘 要： | 可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.
|
| 关 键 词： | 可逆逻辑综合 可逆函数 Toffoli门 可逆电路优化 |
| 收稿时间： | 2012-10-26 |
| 修稿时间： | 2013-03-22 |
Rule-based Optimization of Reversible Toffoli Circuits |
| |
| CHENG Xue-yun,GUAN Zhi-jin,ZHANG Hai-bao and DING Wei-pin. Rule-based Optimization of Reversible Toffoli Circuits[J]. Computer Science, 2013, 40(10): 32-38 |
| |
| Authors: | CHENG Xue-yun GUAN Zhi-jin ZHANG Hai-bao DING Wei-pin |
| |
| Affiliation: | School of Computer Science and Technology,Nantong University,Nantong 226019,China;School of Computer Science and Technology,Nantong University,Nantong 226019,China;College of Electronics and Information,Nantong University,Nantong 226019,China;School of Computer Science and Technology,Nantong University,Nantong 226019,China |
| |
| Abstract: | |
| |
| Keywords: | Reversible logic synthesis Reversible function Toffoli gate Optimization of reversible circuit |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
|
