组合逻辑电路和多态逻辑电路设计算法研究

摘要

进化型硬件（Evolvable Hardware：EHW）是能够根据外部环境变化而自动的调整自身结构，从而适应新环境的一种硬件。一方面，EHW具有自组织、自适应、自修复和容错等特点，它的这种自适应能力使得系统在极端和未知环境条件下（如深空、深海探索）具有更高的可靠性和更强的生存能力。另一方面，EHW为电路设计提供了新的方法。使用EHW技术，不但可以找到传统电路设计方法难以探索到的硬件结构，从而使设计出的电路具有紧凑、低功耗、容错和自修复等特性；而且，EHW 不需要领域知识，可以减轻设计人员的负担，降低设计成本。EHW 技术已可成功设计规模较小的电路。但是，现在的EHW 技术面临可扩展性问题，难以生成较大规模的电路。
　　 目前，EHW的目标电路主要是传统的数字逻辑电路、时序逻辑电路或者模拟电路。但是，随着多态电子学的出现，多态电路为EHW的发展提供了新的思路。多态电子学是近年来新兴的一个电子学研究领域，和传统的电子学不同，多态器件是具有内在多功能特性的电子学器件。一个多态器件，在不同的环境中将表现出不同的功能。利用多态电路的内在多功能性和对环境信号的敏感特性，将其与EHW 技术相结合，可以构建新型的自适应电路和系统。
　　 本文旨在研究基于EHW技术的电路设计方法,多态逻辑电路的设计方法和多态逻辑电路的完备性理论。本论文的主要研究内容和创新有如下几个方面：
　　 （1）提出了基于逐步降维方法（Stepwise Dimension Reduction，SDR）的组合逻辑电路进化设计算法。对于多输入单输出的电路，该方法将整个电路分解为多个子电路，前一个子电路的输出是后一个子电路的输入。每一个子电路都单独进化生成，并且尽量使该子电路的输出个数小于输入个数。当某一个子电路的输出数是1 时，进化结束。最后，将生成的子电路前后连接在一起，得到目标电路。使用基于逐步降维的方法可以减少进化时间，得到更大规模的电路。但是，对于复杂度很高的电路（如5×5 乘法器），通过逐步降维方法得到的某些子电路很难进化生成。针对此问题，提出了扩展的逐步降维方法（Extended Dimension Stepwise Reduction Approach，XSDR）。当某个子电路难以实现降维时，XSDR 将输入真值表分解为两个更简单的真值表。对这两个真值表分别使用XSDR 方法生成其电路，最后使用异或门将两个电路连接起来。实验结果表明，与逐步降维方法相比，扩展的逐步降维方法耗用的进化时间更短，生成的电路规模更大。
　　 （2）提出了基于二叉分解（Bi-Decomposition）的多态逻辑电路设计方法。
　　 Bi-Decomposition 方法使用一个传统的逻辑门（AND，OR 或者XOR）将原真值表分解为两个更简单的真值表，通过不断重复这一分解操作，完成自顶向下的电路设计过程。基于Bi-Decomposition 设计方法，本文提出了用于多态逻辑电路设计的多态二叉分解（Poly-Bi-Decompositon）方法。在Poly-Bi-Decompositon 方法中，使用多态门，将一个多态真值表分解为两个更简单的多态真值表，从而实现多态电路的设计。
　　 （3）研究了多态逻辑门集的完备性问题，给出了判断逻辑门集完备性的算法。首先讨论了Logic-0和Logic-1 对多态逻辑门集完备性的影响，给出了弱完备和强完备多态逻辑门集的定义。其次，给出了基于多态多路选择器的完备多态逻辑门集的定义。并在此定义的基础上，设计了两个判断两态多态逻辑门集完备性的算法。最后，给出了判断任意态数多态逻辑门集的理论和完备性判定算法。
　　 （4）提出了判断多态逻辑门集完备性的直观算法。此方法通过构造几个关键的多态电路来判断一个多态逻辑门集的完备性。如果这几个关键电路能够被一个多态逻辑门集构建，那么它是完备的。否则，这个门集不完备。此完备性判定方法和传统逻辑门集完备性的判定方法有很大相似性，直观易懂。而且适用于手工操作。
　　 本论文对数字逻辑电路进化设计中的可扩展性问题和多态电路进行了深入的研究。一方面，提出快速高效的电路进化设计方法；另一方面，借鉴传统逻辑电路的设计方法，给出设计大规模多态逻辑电路的方法。并给出了判断多态门集完备性的算法。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章 绪 论

第2章 基于逐步降维方法的数字逻辑电路进化设计算法

第3章 基于二叉分解（Bi-Decomposition）方法的多态逻辑电路设计

第4章 多态逻辑门集的完备性研究

第5章 判断多态逻辑门集完备性的直观算法

第6章 总结与展望

附 录

参考文献

致 谢

在读期间发表的论文和参加的科研项目

作者简历