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

发布时间：2018-12-28 12:33

【摘要】：可逆逻辑电路是仅包含可逆运算的新型电路，可以根除源于信息损失的能耗和发热，是研究和实现超低功耗集成电路、量子计算机以及信息安全等的基础和关键。可逆逻辑综合就是利用给定的可逆逻辑门，按照可逆网络无扇入扇出、无反馈等约束条件和限制，实现具备预期逻辑功能且尽可能优化的可逆逻辑电路。因此，对可逆逻辑综合方法的研究具有重要的理论意义和应用前景。本文一方面针对可逆逻辑综合的需要，以显著提高可逆逻辑综合算法的胜任规模和优化程度为目标，对常规（非可逆）逻辑综合、优化方面著名的Espresso算法进行了移植和实现。通过分析常规的“积之和”表达式和便于可逆逻辑门实现的“积之异或和”表达式之间的差异与联系，推导出了它们之间相互转换的方法，然后据此方法讨论了将Espresso算法修改和移植用于可逆逻辑综合的思路和要点。通过理论推导和实例分析验证了上述移植方法应用于可逆逻辑综合的有效性，并对改进的算法进行了编程实现和实验检验。另一方面，针对可逆逻辑电路的特点，讨论了利用常用的可逆逻辑门和扩展的可逆逻辑门构造可逆逻辑电路的方法和步骤；重点研究了通过识别可逆逻辑表达式提取电路结构信息，并加以图形化显示的有效方法和可行算法，并对上述方法和算法进行了编程实现、实验验证和有效改进。希望本文对于可逆逻辑综合、优化方面的研究，，特别是现行（非可逆）逻辑综合、优化算法面向可逆逻辑的移植、改进，以及可逆逻辑设计结果的图形化表达和交互式分析、验证，能够具有较大参考价值甚至起到一定推动作用。
[Abstract]:Reversible logic circuit is a new type of circuit which contains only reversible operation. It can eliminate the energy consumption and heat caused by information loss. It is the foundation and key to research and implement ultralow power integrated circuit, quantum computer and information security. Reversible logic synthesis is to realize the reversible logic circuit with expected logic function and optimize as far as possible, according to the constraints and limitations of reversible network, such as no fan in and out, no feedback and so on, using a given reversible logic gate. Therefore, the research of reversible logic synthesis method has important theoretical significance and application prospect. In this paper, aiming at the need of reversible logic synthesis, aiming at improving the scale and optimization degree of reversible logic synthesis algorithm, the famous Espresso algorithm is transplanted and implemented in the aspect of conventional (non-reversible) logic synthesis and optimization. By analyzing the difference and relation between the expression of "sum of product" and the expression of "sum of products" which is easy to realize by reversible logic gate, the method of conversion between them is deduced. Based on this method, the idea and key points of modifying and transplanting Espresso algorithm for reversible logic synthesis are discussed. The validity of the proposed method in reversible logic synthesis is verified by theoretical derivation and example analysis. The improved algorithm is programmed and tested experimentally. On the other hand, according to the characteristics of reversible logic circuits, the methods and steps of constructing reversible logic circuits using common reversible logic gates and extended reversible logic gates are discussed. The effective methods and feasible algorithms for extracting circuit structure information by identifying reversible logic expressions and displaying them graphically are studied emphatically. The above methods and algorithms are implemented by programming, and verified by experiments and improved effectively. It is hoped that the research on reversible logic synthesis, optimization, especially the current (non-reversible) logic synthesis, the optimization algorithm oriented to the transplantation and improvement of reversible logic, and the graphical representation and interactive analysis of reversible logic design results will be carried out in this paper. Verification, can have greater reference value and even play a role in promoting.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN791

【参考文献】