【摘要】：可逆計算的研究在許多領域有重要應用,例如信號處理,密碼學,計算機圖形學,納米學和光子電路。例如,可逆計算的理論是量子計算的基礎。量子計算的電路模型的一個重要特點就是可逆性,可逆性也是量子力學假定發(fā)展的結果�？赡嬗嬎愕囊粋�重要問題是可逆電路綜合。但是,目前可逆邏輯電路綜合算法還存在著適用電路規(guī)模過小、時空代價過高等一系列問題,還不能滿足未來可逆計算及其相關領域對可逆邏輯電路的要求。因此,系統(tǒng)而深入地研究可逆電路的合成及優(yōu)化技術,尋找更為高效的合成和優(yōu)化可逆電路的算法是很有必要的。我們對可逆邏輯及其綜合算法進行了深入研究,主要研究工作及成果如下:1、基于置換中循環(huán)分解的可逆電路綜合算法可逆函數(shù)與置換同構,任意置換都有其相應的循環(huán)表示。文中我們基于探索置換的循環(huán)表示的性質的思路,提出了一種新的基于置換中循環(huán)分解的可逆電路綜合算法。該算法由兩部分組成,第一部分根據(jù)異位數(shù)判定是否需增加邏輯非門達到減少輸入和輸出向量的漢明距離;第二部分依據(jù)置換以及置換的循環(huán)表示的性質,將置換中循環(huán)分解,漸漸接近恒等置換,直至變?yōu)楹愕戎脫Q,這部分電路由正反控制的Toffoli門實現(xiàn)。該算法提供了一種新的思路,且仍可以通過改進算法來優(yōu)化最終結果,并且這種思路也可以擴展到4量子比特乃至更多比特位的電路綜合。2、基于CUDA的可逆電路綜合算法加速的研究CUDA是目前應用最為廣泛的通用并行計算架構,借助GPU(圖像處理器)的并行處理能力,在不增加額外成本的情況下就能較大幅度的提升程序的運行速度和相應的求解能力。這部分工作中,我們將借助CUDA并行架構,實現(xiàn)一種計算Hash函數(shù)的快速算法以及實現(xiàn)置換的乘積運算以模擬可逆電路的級聯(lián),分別對其加速比進行了研究,完成了一種高效的可逆電路綜合算法在CUDA運算平臺的并行化實現(xiàn)。
【圖文】：

扇入；③沒有反饋；④網(wǎng)絡分層級聯(lián)。逡逑一個可逆函數(shù)可以用真值表的形式表示，可以把它看作一個整數(shù)序列｛０，１，…，２ｎ－ｌ｝到自逡逑身的一一映射，還可以用整數(shù)集合的置換表示。圖２－１為一個３變量的可逆邏輯網(wǎng)絡，表逡逑２－１為其可逆函數(shù)的真值表表示，式（２．３）為其可逆函數(shù)的置換表示。逡逑Ｘ３邋邐邐Ｏ邐少３逡逑Ｘ！邐邐Ｏ邐ｙｉ逡逑ｘ邋丨邐？—？—＾逡逑圖２－１邋—個３輸入／輸出可逆邏輯網(wǎng)絡逡逑表２－１是圖２－１所示可逆邏輯網(wǎng)絡的真值表表示：逡逑表２－１邋—個３ｘ３的可逆邏輯函數(shù)逡逑輸入邐輸出逡逑邐尤邋３邐＆邋ａ邐ｙ３邋Ｖ２邋ｙｉ逡逑０

１邐１邐１１＾邐、｜１１邐１逡逑圖２－２該可逆邏輯函數(shù)的雙射關系逡逑式（２．３）為圖２－１所示的可逆邏輯網(wǎng)絡的置換表示，，該式的含義是：ｆ（０）＝２，邋ｆ（ｌ）＝６，…，逡逑ｆ（７）＝４。逡逑／０邐１邐２邐３邐４邐５邐６邐７＼逡逑ａ＝邋（２邐６邐０邐１邐７邐３邐５邐４）邐（２３）逡逑我們論文的主要內(nèi)容就是基于可逆邏輯網(wǎng)絡（可逆邏輯函數(shù)）的置換這一表示形式的逡逑性質，這一小節(jié)是這篇論文的重要理論基礎。下一小結為大家介紹可逆邏輯網(wǎng)絡構成的基逡逑本元素一可逆邏輯門。逡逑２．３可逆邏輯門逡逑可逆邏輯門是邏輯網(wǎng)絡的基本元素�？赡孢壿嬮T的級聯(lián)，可以構造形成可逆網(wǎng)絡，用逡逑以實現(xiàn)復雜的邏輯和算術運算。也就是說，上一節(jié)中我們所說的可逆邏輯函數(shù)是用可逆邏逡逑輯門來實現(xiàn)的，可逆邏輯門也對應著相應的可逆邏輯函數(shù)�？赡孢壿嬮T所對應的邏輯函數(shù)逡逑一定是實現(xiàn)雙射。即可逆邏輯門的輸入和輸出必須有一個一對的映射關系，輸出可由輸入逡逑唯一確定，同樣它的輸入也能由輸出唯一確定。逡逑因此，設一個（ｍ，ｎ）的邏輯門有ｍ個輸入和ｎ個輸出，ｍ＝ｎ是一個邏輯門可逆的必要逡逑條件。如果一個邏輯門是可逆的
【學位授予單位】：揚州大學
【學位級別】：碩士
【學位授予年份】：2018
【分類號】：TP38

【相似文獻】

相關期刊論文 前10條

1 鄭士貴;高級綜合算法、工具和設計研討會[J];管理科學文摘;1997年09期

2 李斌;綜合算法和設計方法研討會[J];管理科學文摘;1997年10期

3 江衛(wèi)國,賈焰,周堤基,吳泉源;TD匹配自動邏輯綜合算法[J];計算機輔助設計與圖形學學報;1989年01期

4 馬靜;麻莉莉;;最小控制綜合算法綜述[J];計算機測量與控制;2013年12期

5 雷偉剛,劉大杰,童小華;空間線要素綜合算法的不確定性討論[J];測繪工程;2005年01期

6 洪源源,邱菀華;AHP、GEM及其綜合算法[J];中國管理科學;2000年04期

7 周玉潔,周錦君;環(huán)Z/(m)上兩種序列綜合算法之間的關系[J];高校應用數(shù)學學報A輯(中文版);1998年04期

8 周錦君,戚文峰,周玉潔;Gr銉bner基推廣及Z/(m)上多條序列綜合算法[J];中國科學(A輯 數(shù)學 物理學 天文學 技術科學);1995年02期

9 胡健;;導彈主動雷達制導系統(tǒng)彈道控制綜合算法[J];戰(zhàn)術導彈技術;2007年06期

10 雷偉剛,劉大杰,童小華;空間線要素綜合算法的不確定性討論[J];鐵道勘察;2004年06期

相關會議論文 前3條

1 雷偉剛;劉大杰;童小華;;空間線要素綜合算法的不確定性討論[A];廣東省電機工程學會2003-2004年度優(yōu)秀論文集[C];2005年

2 石連拴;;離散變量結構拓撲優(yōu)化設計綜合算法的進一步探討[A];第九屆全國結構工程學術會議論文集第Ⅱ卷[C];2000年

3 王美珍;沈婕;;基于JUMP的居民地實時地圖綜合算法研究[A];中國地理學會2007年學術年會論文摘要集[C];2007年

相關碩士學位論文 前5條

1 朱蔚;基于置換中循環(huán)分解的可逆電路綜合算法[D];揚州大學;2018年

2 劉磊;基于簡化的三維城市模型綜合算法研究[D];南京大學;2015年

3 楊文龍;基于預編譯庫的邏輯綜合算法的研究與實現(xiàn)[D];復旦大學;2013年

4 王美珍;面向移動地圖表達的居民地地圖綜合算法研究[D];南京師范大學;2008年

5 戴立新;電磁超聲系統(tǒng)強噪聲干擾抑制算法研究[D];西南交通大學;2010年

本文編號：2623548