基于多染色体基因表达式编程的可逆逻辑综合方法研究

发布时间：2018-02-05 19:25

本文关键词： 可逆逻辑综合多基因编码多染色体编码调用关系　出处：《东华大学》2017年硕士论文　论文类型：学位论文

【摘要】：可逆逻辑电路是由可逆逻辑门依次级联构成,利用给定的逻辑门,按照可逆逻辑电路无扇入扇出、无反馈等约束条件和限制,实现预期逻辑功能且尽可能优化的可逆逻辑电路。它以可逆方式进行逻辑运算、不丢失输入信息,是一种可避免信息损失和有效降低能量损耗甚至达到零损耗的新型电路。可逆逻辑电路是实现量子计算的基础,它和常规不可逆逻辑电路存在较大差异。可逆逻辑电路的综合方法与现行的非可逆逻辑电路综合方法截然不同,比传统逻辑综合具有更大的难度。本文寻求以较少的运算量和人工参与,可自动地生成和优化可逆逻辑表达式的综合方法,论述了可逆逻辑综合的基本原理,技术特点和研究现状,通过研究单基因的基因表达式编程算法和多染色体基因表达式编程算法,对常规的基因表达式编程算法进行了改进。将单基因编码方式改进为多基因的编码方式,将多染色体编码方式改进为染色体之间具有相互联系的编码方式,并将多基因和具有相互联系的多染色体基因表达式编程算法应用于可逆逻辑综合,以提高综合能力和优化程度。具体地从基因的编码方式和适应度函数的改进出发,对算法进行了相应的改进,并进行了实验分析,主要的研究内容和结果包括以下几方面:(1)针对基因表达式编程算法的单基因编码方式,将单基因编码方式改进为多基因的编码方式,使得一个复杂的个体可以通过较少的字符编码来表示。(2)针对多染色体基因表达式编程算法的多染色体无相互联系的编码方式,将多染色体无相互联系的编码方式改进为染色体之间上层染色体对下层染色体具有调用关系的编码方式。染色体之间具有调用关系的编码方式解决了原多染色体之间没有相互联系的缺点,使得同一个个体之间的染色体与染色体之间可以进行信息交换,使个体自身内部能进行各种进化操作。(3)在改进的多染色体调用模型的基础上,增加了染色体体重组和基因随机重组操作。(4)面向可逆逻辑综合问题,改进了多染色体基因表达式编程算法的适应度函数,使算法适用于可逆逻辑综合。(5)利用C语言编程实现了多基因编码和多染色体调用模型编码的可逆逻辑综合,初步实现了最大11输入变量的可逆逻辑综合,并根据得到的可逆逻辑表达式绘制出对应的可逆逻辑电路。本文对基于多染色体基因表达式编程的可逆逻辑综合的关键性问题进行了探索和研究,理论分析和实验结果表明本文的方法能够有效地解决相应的问题,为可逆逻辑自动综合提供了一种新的方法。
[Abstract]:Reversible logic circuit is composed of reversible logic gate cascade in turn, using given logic gate, according to reversible logic circuit no fan in and out, no feedback and other constraints and limitations. A reversible logic circuit that realizes the expected logic function and optimizes as much as possible. It performs logic operations in a reversible manner and does not lose input information. It is a new circuit which can avoid the loss of information and reduce the energy loss or even achieve zero loss effectively. Reversible logic circuit is the foundation of quantum computation. The synthesis method of reversible logic circuit is different from that of non-reversible logic circuit. It is more difficult than the traditional logic synthesis. This paper seeks to generate and optimize the reversible logic expression automatically with less computation and manual participation, and discusses the basic principle of reversible logic synthesis. Through the research of single gene gene expression programming algorithm and polychromosome gene expression programming algorithm. The conventional genetic expression programming algorithm is improved. The single gene coding method is improved to the multi-gene coding mode, and the polychromosome coding method is improved to the coding mode with interlinked chromosomes. The algorithm of polygene and polychromosome gene expression programming is applied to reversible logic synthesis. In order to improve the synthesis ability and the degree of optimization, the algorithm is improved based on the improvement of gene coding mode and fitness function, and the experimental analysis is carried out. The main research contents and results include the following aspects: 1) in view of the single gene coding method of gene expression programming algorithm, the single gene coding method is improved to multi gene coding mode. So that a complex individual can be represented by fewer character encodings) an unrelated coding method for polychromosome gene expression programming algorithms. In this paper, we improve the coding method of polychromosome which is not related to each other. The coding method with calling relation between the upper chromosomes and the lower chromosomes solves the problem of the original polychromosomes. There is no connection between the shortcomings. This makes it possible to exchange information between chromosomes and chromosomes of the same individual, so that the individual can carry out various kinds of evolutionary operations within himself) on the basis of the improved multi-chromosome call model. The problem of reversible logic synthesis for chromosome body recombination and random gene recombination operation is added, and the fitness function of multi-chromosome gene expression programming algorithm is improved. The algorithm is suitable for reversible logic synthesis. (5) the reversible logic synthesis of multi-gene coding and multi-chromosome call model coding is realized by C language programming. The reversible logic synthesis of the maximum input variables of 11 is realized preliminarily. The corresponding reversible logic circuits are drawn according to the obtained reversible logic expressions. In this paper, the key problems of reversible logic synthesis based on multi-chromosome gene expression programming are explored and studied. The theoretical analysis and experimental results show that the proposed method can solve the corresponding problems effectively and provides a new method for automatic synthesis of reversible logic.
【学位授予单位】：东华大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP331

【相似文献】