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

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

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

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

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

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

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

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

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