进化型硬件(Evolvable Hardware, EHW)是能够根据外部环境变化而自动的调整自身结构,从而适应新环境的一种硬件。一方面,EHW具有自组织、自适应、自修复和容错等特点,它的这种自适应能力使得系统在极端和未知环境条件下(如深空、深海探索)具有更高的可靠性和更强的生存能力。另一方面,EHW为电路设计提供了新的方法。使用EHW技术,可以找到传统电路设计方法难以探索到的硬件结构,从而使设计出的电路具耗用资源少、功耗低、容错等特性。EHW技术已可成功设计规模较小的电路。但是,现在的EHW技术面临可扩展性问题,难以生成较大规模的电路。目前,EHW的目标电路主要是传统的数字逻辑电路、时序逻辑电路或者模拟电路。但是,随着多态电子学的出现,多态电路为EHW的发展提供了新的思路。多态电子学是近年来新兴的一个电子学研究领域,和传统的电子学不同,多态器件是具有内在多功能特性的电子学器件。一个多态器件,在不同的环境中将表现出不同的功能。利用多态电路的内在多功能性和对环境信号的敏感特性,将其与EHW技术相结合,可以构建新型的自适应电路和系统。本文旨在研究基于EHW技术的组合逻辑电路设计方法,多态逻辑电路设计方法和多态逻辑电路的完备性理论。本论文的主要研究内容和创新之处有如下几个方面。(1)提出了基于逐步降维方法(Stepwise Dimension Reduction, SDR)的组合逻辑电路进化设计算法。对于多输入单输出的电路,该方法将整个电路分解为多个子电路,前一个子电路的输出是后一个子电路的输入。每一个子电路都单独进化生成,并且尽量使该子电路的输出个数小于输入个数。当某一个子电路的输出数是1时,进化结束。最后,将生成的子电路前后连接在一起,得到目标电路。使用基于逐步降维的方法可以减少进化时间,得到更大规模的电路。但是,对于复杂度较高的电路(如5×5乘法器),通过逐步降维方法得到的某些子电路很难进化生成。针对此问题,提出了扩展的逐步降维方法(Extended Dimension Stepwise Reduction, 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)提出了判断多态逻辑门集完备性的直观算法。此方法通过构造几个关键的多态电路来判断一个多态逻辑门集的完备性。如果这几个关键电路能够被一个多态逻辑门集构建,那么它是完备的。否则,这个门集不完备。此完备性判定方法和传统逻辑门集完备性的判定方法有很大相似性,直观易懂,而且适用于手工操作。本论文对组合逻辑电路进化设计中的可扩展性问题和多态电路设计理论进行了深入的研究。一方面,提出快速高效的电路进化设计方法；另一方面,借鉴传统逻辑电路的设计方法,给出了设计较大规模多态逻辑电路的方法,以及判断多态门集完备性的算法。