面向可逆逻辑综合的Espresso算法的改进与实现

摘要

可逆逻辑电路是仅包含可逆运算的新型电路，可以根除源于信息损失的能耗和发热，是研究和实现超低功耗集成电路、量子计算机以及信息安全等的基础和关键。可逆逻辑综合就是利用给定的可逆逻辑门，按照可逆网络无扇入扇出、无反馈等约束条件和限制，实现具备预期逻辑功能且尽可能优化的可逆逻辑电路。因此，对可逆逻辑综合方法的研究具有重要的理论意义和应用前景。
　　本文一方面针对可逆逻辑综合的需要，以显著提高可逆逻辑综合算法的胜任规模和优化程度为目标，对常规（非可逆）逻辑综合、优化方面著名的Espresso算法进行了移植和实现。通过分析常规的“积之和”表达式和便于可逆逻辑门实现的“积之异或和”表达式之间的差异与联系，推导出了它们之间相互转换的方法，然后据此方法讨论了将Espresso算法修改和移植用于可逆逻辑综合的思路和要点。通过理论推导和实例分析验证了上述移植方法应用于可逆逻辑综合的有效性，并对改进的算法进行了编程实现和实验检验。另一方面，针对可逆逻辑电路的特点，讨论了利用常用的可逆逻辑门和扩展的可逆逻辑门构造可逆逻辑电路的方法和步骤；重点研究了通过识别可逆逻辑表达式提取电路结构信息，并加以图形化显示的有效方法和可行算法，并对上述方法和算法进行了编程实现、实验验证和有效改进。
　　希望本文对于可逆逻辑综合、优化方面的研究，特别是现行（非可逆）逻辑综合、优化算法面向可逆逻辑的移植、改进，以及可逆逻辑设计结果的图形化表达和交互式分析、验证，能够具有较大参考价值甚至起到一定推动作用。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 课题研究背景与意义

1.2 课题研究历史与现状

1.3 主要研究内容与论文结构

2 可逆逻辑电路及其综合基础

2.1 常用可逆逻辑门简介

2.2 可逆逻辑电路及其评价指标

2.3 可逆逻辑电路的综合方法概述

2.4 本章小结

3 Espresso算法的化简原理和工作流程

3.1 Espresso算法概述

3.2 基本概念和理论

3.3 逻辑函数的单调性

3.4 永真式判定算法

3.5 Espresso算法的实现流程

3.6 Espresso算法的总流程

3.7 本章小结

4 Espresso算法的移植和实现

4.1 算法移植的原理

4.2 算法移植的实现

4.3 移植的Espresso算法的结果与分析

4.4 本章小结

5 可逆逻辑表达式的自动分析和图示

5.1 扩展的可逆逻辑门

5.2 可逆逻辑电路的构造方法

5.3 可逆逻辑表达式的图形化显示方法

5.4 可逆逻辑表达式的显示结果与分析

5.5 本章小结

6 总结与展望

6.1 全文总结

6.2 展望

参考文献

攻硕期间的研究成果

致谢