文档介绍：中国科学技术大学
博士学位论文
组合逻辑电路和多态逻辑电路设计算法研究
姓名:李知方
申请学位级别:博士
专业:计算机应用技术
指导教师:岳丽华;罗文坚
2011-05
摘要
摘要
进化型硬件(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-position)的多态逻辑电路设计方法。
Bi-position 方法使用一个传统的逻辑门(AND,OR 或者 XOR)将原真值
I
摘要
表分解为两个更简单的真值表,通过不断重复这一分解操作,完成自顶向下的
电路设计过程。基于 Bi-position 设计方法,本文提出了用于多态逻辑电
路设计的多态二叉分解( Poly-Bi-positon ) 方法。在
Poly-Bi-positon 方法中,使用多态门,将一个多态真值表分解为两个更
简单的多态真值表,从而实现多态电路的设计。
(3)研究了多态逻辑门集的完备性问题,给出了判断逻辑门集完备性的算
法。首先讨论了 Logic-0 和 Logic-1 对多态逻辑门集完备性的影响,给出了弱
完备和强完备多态逻辑门集的定义。其次,给出了基于多态多路选择器的完备
多态逻辑门集的定义。并在此定义的基础上,设计了两个判断两态多态逻辑门
集完备性的算法。最后,给出了判断任意态数多态逻辑门集的理论和完备性判
定算法。
(4)提出了判断多态逻辑门集完备性的直观算法。此方法通过构造几个关
键的多态电路来判断一个多态逻辑门集的完备性。如果这几个关键电路能够被
一个多态逻辑门集构建,那么它是完备的。否则,这个门集不完备。此完备性
判定方法和传统逻辑门集完备性的判定方法有很大相似性,直观易懂。而且适
用于手工操作。
本论文对数字逻辑电路进化设计中的可扩展性问题和多态电路进行了深入
的研究。一方面,提出快速高效的电路进化设计方法;另一方面,借鉴传统逻
辑电路的设计方法,给出设计大规模多态逻辑电路的方法。并给出了判断多态
门集完备性的算法。
关键词:进化算法进化型硬件电路进化设计多态逻辑电路完备