【摘要】：計算機CMOS芯片的熱耗散限制了芯片的集成度,而傳統(tǒng)邏輯門的不可逆操作是導(dǎo)致能量耗散的主要原因。要避免能量耗散,電路必須由可逆門來構(gòu)造。因此,可逆電路在可逆計算、低能耗CMOS設(shè)計,光計算、量子計算及DNA計算等領(lǐng)域有著廣泛的應(yīng)用,可逆電路綜合逐漸成為新的研究熱點。已有的可逆電路綜合方法基本分為確定性算法、啟發(fā)式算法和進化類算法。其中,一部分確定性算法能有效地獲得可行解,甚至是對中、大規(guī)�？赡鎲栴},但獲得的解仍需后優(yōu)化過程進行改進。后優(yōu)化過程往往需要反復(fù)迭代并且作用有限。另一部分確定性算法使用窮盡式搜索方法取得最優(yōu)解,但只局限于小規(guī)模三位、四位可逆電路的綜合。啟發(fā)式方法利用貪婪式啟發(fā)策略進行解空間的約簡,對中小規(guī)模電路能夠在有限時間內(nèi)獲得有效解,但解仍需優(yōu)化。進化方法由于具有全局搜索能力,已用于可逆電路綜合,但相比較前兩類算法,只對小規(guī)模、低復(fù)雜度可逆函數(shù)進行了測試,并沒有取得突破性的成果。本文研究利用進化方法進行可逆電路綜合,旨在解決窮盡式搜索力所不及的中小規(guī)模問題,并在這些問題上能夠取得比確定性算法更優(yōu)的解�？赡骐娐肪C合問題可以建模成具有等式約束的最小化問題,其中約束是指電路的誤差,目標(biāo)表示可逆電路的代價。針對可逆電路綜合搜索空間巨大、最優(yōu)解長度不確定、上位性和多峰等特點,主要從變長編碼進化、等式約束處理、多樣性保持策略、混合進化策略、適應(yīng)度函數(shù)定義等方面入手,對進化可逆電路綜合算法設(shè)計進行了全面深入的研究,獲得了一些關(guān)鍵性的研究成果。主要概括為以下幾個方面:(1)設(shè)計實現(xiàn)基本變長染色體編碼進化算法。改進了約束違反評價函數(shù),利用可逆電路的正極性Reed Muller表達式與恒等函數(shù)正極性Reed Muller表達式的差別項數(shù)做為評價標(biāo)準,而不是用傳統(tǒng)的矩陣跡距離,因而避免了計算量較大的矩陣積及矩陣克羅內(nèi)克積的計算;利用從可逆函數(shù)的Reed Muller表達式中提取的因子數(shù)量信息,正確估計電路的最大長度并進行種群的初始化;采用染色體最大長度限制和無損交叉算子,使染色體長度逐漸增長,防止變長進化中的染色體膨脹。(2)設(shè)計了兩種等式約束處理方法。第一種方法采用目標(biāo)和約束分離的機制處理等式約束,對非支配的不可行解,計算節(jié)儉壓力并與平衡因子比較,根據(jù)比較結(jié)果完成種群中染色體的排序,將其作為選擇的基礎(chǔ)。通常,約束違反降低的過程往往伴隨著目標(biāo)值的增加,平衡因子反映了約束違反單位下降所能容忍的目標(biāo)值增加量,因此能起到防止染色體膨脹的作用。第二種方法采用基于偏好的多目標(biāo)優(yōu)化方法來處理約束。通過改進參考點多目標(biāo)優(yōu)化算法,根據(jù)解的分布動態(tài)生成并更新參考點,并定義新的基于距離的比較算子,使得搜索逐步受控地向約束違反減小的方向進行。(3)實現(xiàn)變長染色體編碼進化算法的多樣性保持機制。由于變長染色體編碼進化選擇過程中對具有較小約束違反的解的偏好,會使種群逐漸喪失多樣性,陷入局部最優(yōu),又由于可逆電路綜合問題解空間本身具有的多峰特點,進化過程中的多樣性保持尤其重要。我們借鑒并改進了子種群探測和種子保留的多樣性保持機制,定義了變長染色體之間的距離,增加了子種群的更新機制。實驗證明采用該多樣性保留機制后,可行解比例和解的質(zhì)量均有所提高。(4)設(shè)計實現(xiàn)混合算法。將進化算法與基于PPRM的啟發(fā)式算法結(jié)合,從當(dāng)前解的RRPM表達式中提取優(yōu)選因子構(gòu)建優(yōu)選門庫,在進化停滯階段進行個體的更新,從而加快進化算法的收斂速度,提高可行解的比例。(5)將進化可逆邏輯綜合研究成果與基于憶阻器蘊含門的邏輯綜合問題特點相結(jié)合,提出了基于憶阻器蘊含門的邏輯綜合進化算法。算法將變長編碼進化可逆邏輯綜合算法框架用于憶阻器蘊含門的邏輯電路綜合問題,提出了憶阻器蘊含門的染色體編碼、評價方法及提高可行解率的局部搜索方法,實驗證明了算法的有效性。本文對進化可逆邏輯電路綜合中的關(guān)鍵性問題進行了有效的探索和嘗試,實驗結(jié)果分析表明本文的方法對中、小規(guī)模的可逆標(biāo)準測試函數(shù)具有有效性,達到了預(yù)期的設(shè)計目的。另外,將進化可逆邏輯電路綜合方法應(yīng)用于基于憶阻器蘊含門的邏輯綜合問題,實驗結(jié)果進一步驗證了該方法可以推廣到其它變長編碼的邏輯電路綜合問題。
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2016
【分類號】：TP331.1
【圖文】：

第一章 緒論9圖1.2 可逆邏輯電路綜合算法比較1.3 論文的研究目的和內(nèi)容1.3.1 研究目的就上一節(jié)所總結(jié)的可逆邏輯綜合面臨的問題，及進化算法所具有的全局并行搜索和根據(jù)適應(yīng)度函數(shù)定義的不同優(yōu)化不同指標(biāo)的特點，本研究的目的就是針對可逆邏輯綜合問題大搜索空間、最優(yōu)解編碼長度未知、必須滿足等式約束等特點，設(shè)計專門的進化算法及進化、啟發(fā)式方法相結(jié)合的算法，在不引入多余輸入線的前提下，降低4-bit 及 4-bit 以上中小規(guī)�？赡骐娐返牧孔哟鷥r，設(shè)計可逆綜合多目標(biāo)優(yōu)化算法，取得多個優(yōu)化指標(biāo)的平衡。另外，由于除了可逆電路邏輯綜合問題外，大部分電路邏輯綜合問題都具有最優(yōu)解長度未知，需要滿足等式約束等特點，因此，得出能夠借鑒推廣、并有效解決具有上述特點的一類邏輯綜合問題的進化算法或混合算法

數(shù)的節(jié)點數(shù)量，但二叉決策圖的變形形式能夠用多項式的節(jié)點數(shù)量來表示許多實際函數(shù)。函數(shù) 3_17 的二叉決策圖如圖 2.1 所示。圖2.1 可逆函數(shù) 3_17 的二叉決策圖表示不相交循環(huán)表示。循環(huán)置換是置換的另一種表達形式，它以發(fā)生變化的文字的變化 次 序 為 序 ， 表 達 成 輪 換 的 形 式 。 如 ： 可 逆 函 數(shù) 3_17 的 置 換 過 程 為0 7 5 2 4 0，其余元素 1，3，6 不變，因此可以表示成 8 元素的循環(huán)置換 0 7 5 2 4 。一般每個循環(huán)的表達方法不唯一，習(xí)慣上總是將循環(huán)置換中出現(xiàn)的最小文字置首位。對于長度大于 2 的循環(huán)

西安電子科技大學(xué)博士學(xué)位論文16圖2.2 可逆電路輸入輸出結(jié)構(gòu)圖表2.1 邏輯與運算可逆真值表z y x f1f2f30 0 0 0 0 00 1 0 0 1 00 0 1 0 0 10 1 1 1 1 11 0 0 1 0 01 1 0 1 1 01 0 1 1 0 11 1 1 0 1 1圖 2.3 顯示了其對應(yīng)的可逆規(guī)范真值表。其中陰影部分為原不可逆規(guī)范，z 為常量輸入位，2f ,3f 為垃圾輸出位,滿足2f y，3f x，1f z xy。當(dāng)電路輸入端給 z賦值為 0 時，在輸出端1f 總能獲得 x 與 y 邏輯與運算的結(jié)果。2.1.3 可逆門可逆門 g 實現(xiàn)可逆函數(shù)，門 g-1能夠?qū)崿F(xiàn)逆變換�；究赡骈T定義如下，符號表示和矩陣規(guī)范見表 2.1。定義 2.3 設(shè)1 2 nX { x , x , , x} 是域變量集合。通用 Toffoli 門 GT[1]記為 TOF( C；t )

【相似文獻】

相關(guān)期刊論文 前10條

1 鄭成志;;“邏輯電路與集成電路”教學(xué)設(shè)計[J];中學(xué)物理教學(xué)參考;2016年16期

2 朱建廉;;關(guān)于“簡單的邏輯電路”教學(xué)要求的研究[J];物理教師;2008年06期

3 丁衛(wèi)東;;“簡單邏輯電路”教學(xué)要略[J];物理教師;2010年11期

4 李如虎;;初探簡單邏輯電路的分析方法[J];中學(xué)物理教學(xué)參考;2010年09期

5 胡志安;;《簡單邏輯電路》教學(xué)中碰到的兩個障礙[J];物理教學(xué)探討;2012年10期

6 呂坤;甘朝暉;;量子可逆邏輯電路自動合成的方法研究[J];計算機仿真;2012年12期

7 劉杰;韋永梅;;非鐘控狀態(tài)下的判優(yōu)邏輯電路研究[J];太原科技大學(xué)學(xué)報;2005年04期

8 ;邏輯電路、脈沖電路[J];電子科技文摘;2000年01期

9 瑞孫桂恩;邏輯電路與自動裝置[J];淮北煤師院學(xué)報(自然科學(xué)版);1995年02期

10 孫瑋;;邏輯電路系列的比較[J];集成電路應(yīng)用;1990年01期

相關(guān)會議論文 前10條

1 趙駿;陳漢武;陳開中;肖芳英;;可逆邏輯電路多余門錯誤的檢測[A];全國第十三次光纖通信暨第十四屆集成光學(xué)學(xué)術(shù)會議論文集[C];2007年

2 陳開中;肖芳英;李志強;陳漢武;;基于群論的可逆邏輯電路綜合方法的研究[A];全國第十三次光纖通信暨第十四屆集成光學(xué)學(xué)術(shù)會議論文集[C];2007年

3 王一泉;;計算機輔助邏輯電路的分析[A];全國計算機輔助教育學(xué)會第五屆學(xué)術(shù)年會論文集[C];1991年

4 莊保安;王鋒;顧樹棣;王煥玉;沈定力;;一種靈活快速的可編程多功能邏輯電路[A];第7屆全國核電子學(xué)與核探測技術(shù)學(xué)術(shù)年會論文集（二）[C];1994年

5 趙帆;姜巖峰;;基于深亞微米工藝的多米諾邏輯電路設(shè)計[A];2009通信理論與技術(shù)新發(fā)展——第十四屆全國青年通信學(xué)術(shù)會議論文集[C];2009年

6 孟憲元;李文元;范京;;FPGA與自主創(chuàng)新和高技術(shù)產(chǎn)業(yè)化[A];2006中國科協(xié)年會論文集（第13分會場）[C];2006年

7 白德風(fēng);呂長志;張U

本文編號：2800479