組合邏輯電路和多態(tài)邏輯電路設(shè)計(jì)算法研究.pdf

1、進(jìn)化型硬件（Evolvable Hardware：EHW）是能夠根據(jù)外部環(huán)境變化而自動(dòng)的調(diào)整自身結(jié)構(gòu)，從而適應(yīng)新環(huán)境的一種硬件。一方面，EHW具有自組織、自適應(yīng)、自修復(fù)和容錯(cuò)等特點(diǎn)，它的這種自適應(yīng)能力使得系統(tǒng)在極端和未知環(huán)境條件下（如深空、深海探索）具有更高的可靠性和更強(qiáng)的生存能力。另一方面，EHW為電路設(shè)計(jì)提供了新的方法。使用EHW技術(shù)，不但可以找到傳統(tǒng)電路設(shè)計(jì)方法難以探索到的硬件結(jié)構(gòu)，從而使設(shè)計(jì)出的電路具有緊湊、低功耗、容錯(cuò)和自修復(fù)

2、等特性；而且，EHW 不需要領(lǐng)域知識(shí)，可以減輕設(shè)計(jì)人員的負(fù)擔(dān)，降低設(shè)計(jì)成本。EHW 技術(shù)已可成功設(shè)計(jì)規(guī)模較小的電路。但是，現(xiàn)在的EHW 技術(shù)面臨可擴(kuò)展性問(wèn)題，難以生成較大規(guī)模的電路。
　　 目前，EHW的目標(biāo)電路主要是傳統(tǒng)的數(shù)字邏輯電路、時(shí)序邏輯電路或者模擬電路。但是，隨著多態(tài)電子學(xué)的出現(xiàn)，多態(tài)電路為EHW的發(fā)展提供了新的思路。多態(tài)電子學(xué)是近年來(lái)新興的一個(gè)電子學(xué)研究領(lǐng)域，和傳統(tǒng)的電子學(xué)不同，多態(tài)器件是具有內(nèi)在多功能特性的電子學(xué)器

3、件。一個(gè)多態(tài)器件，在不同的環(huán)境中將表現(xiàn)出不同的功能。利用多態(tài)電路的內(nèi)在多功能性和對(duì)環(huán)境信號(hào)的敏感特性，將其與EHW 技術(shù)相結(jié)合，可以構(gòu)建新型的自適應(yīng)電路和系統(tǒng)。
　　 本文旨在研究基于EHW技術(shù)的電路設(shè)計(jì)方法,多態(tài)邏輯電路的設(shè)計(jì)方法和多態(tài)邏輯電路的完備性理論。本論文的主要研究?jī)?nèi)容和創(chuàng)新有如下幾個(gè)方面：
　　 （1）提出了基于逐步降維方法（Stepwise Dimension Reduction，SDR）的組合邏輯電路進(jìn)化

4、設(shè)計(jì)算法。對(duì)于多輸入單輸出的電路，該方法將整個(gè)電路分解為多個(gè)子電路，前一個(gè)子電路的輸出是后一個(gè)子電路的輸入。每一個(gè)子電路都單獨(dú)進(jìn)化生成，并且盡量使該子電路的輸出個(gè)數(shù)小于輸入個(gè)數(shù)。當(dāng)某一個(gè)子電路的輸出數(shù)是1 時(shí)，進(jìn)化結(jié)束。最后，將生成的子電路前后連接在一起，得到目標(biāo)電路。使用基于逐步降維的方法可以減少進(jìn)化時(shí)間，得到更大規(guī)模的電路。但是，對(duì)于復(fù)雜度很高的電路（如5×5 乘法器），通過(guò)逐步降維方法得到的某些子電路很難進(jìn)化生成。針對(duì)此問(wèn)題，提出

5、了擴(kuò)展的逐步降維方法（Extended Dimension Stepwise Reduction Approach，XSDR）。當(dāng)某個(gè)子電路難以實(shí)現(xiàn)降維時(shí)，XSDR 將輸入真值表分解為兩個(gè)更簡(jiǎn)單的真值表。對(duì)這兩個(gè)真值表分別使用XSDR 方法生成其電路，最后使用異或門(mén)將兩個(gè)電路連接起來(lái)。實(shí)驗(yàn)結(jié)果表明，與逐步降維方法相比，擴(kuò)展的逐步降維方法耗用的進(jìn)化時(shí)間更短，生成的電路規(guī)模更大。
　　 （2）提出了基于二叉分解（Bi-Decompo

6、sition）的多態(tài)邏輯電路設(shè)計(jì)方法。
　　 Bi-Decomposition 方法使用一個(gè)傳統(tǒng)的邏輯門(mén)（AND，OR 或者XOR）將原真值表分解為兩個(gè)更簡(jiǎn)單的真值表，通過(guò)不斷重復(fù)這一分解操作，完成自頂向下的電路設(shè)計(jì)過(guò)程?；贐i-Decomposition 設(shè)計(jì)方法，本文提出了用于多態(tài)邏輯電路設(shè)計(jì)的多態(tài)二叉分解（Poly-Bi-Decompositon）方法。在Poly-Bi-Decompositon 方法中，使用多態(tài)門(mén)，將一

7、個(gè)多態(tài)真值表分解為兩個(gè)更簡(jiǎn)單的多態(tài)真值表，從而實(shí)現(xiàn)多態(tài)電路的設(shè)計(jì)。
　　 （3）研究了多態(tài)邏輯門(mén)集的完備性問(wèn)題，給出了判斷邏輯門(mén)集完備性的算法。首先討論了Logic-0和Logic-1 對(duì)多態(tài)邏輯門(mén)集完備性的影響，給出了弱完備和強(qiáng)完備多態(tài)邏輯門(mén)集的定義。其次，給出了基于多態(tài)多路選擇器的完備多態(tài)邏輯門(mén)集的定義。并在此定義的基礎(chǔ)上，設(shè)計(jì)了兩個(gè)判斷兩態(tài)多態(tài)邏輯門(mén)集完備性的算法。最后，給出了判斷任意態(tài)數(shù)多態(tài)邏輯門(mén)集的理論和完備性判定算法

8、。
　　 （4）提出了判斷多態(tài)邏輯門(mén)集完備性的直觀算法。此方法通過(guò)構(gòu)造幾個(gè)關(guān)鍵的多態(tài)電路來(lái)判斷一個(gè)多態(tài)邏輯門(mén)集的完備性。如果這幾個(gè)關(guān)鍵電路能夠被一個(gè)多態(tài)邏輯門(mén)集構(gòu)建，那么它是完備的。否則，這個(gè)門(mén)集不完備。此完備性判定方法和傳統(tǒng)邏輯門(mén)集完備性的判定方法有很大相似性，直觀易懂。而且適用于手工操作。
　　 本論文對(duì)數(shù)字邏輯電路進(jìn)化設(shè)計(jì)中的可擴(kuò)展性問(wèn)題和多態(tài)電路進(jìn)行了深入的研究。一方面，提出快速高效的電路進(jìn)化設(shè)計(jì)方法；另一方面，