可逆計(jì)算中邏輯綜合若干問(wèn)題研究.pdf

1、可逆計(jì)算是一個(gè)新興的研究領(lǐng)域，它在現(xiàn)代和未來(lái)計(jì)算機(jī)的諸多技術(shù)中都具有重要價(jià)值?？赡孢壿嬀C合是可逆計(jì)算研究的關(guān)鍵問(wèn)題之一。它是低功耗電路設(shè)計(jì)和量子信息技術(shù)研究的重要組成部分，并在信息安全、納米技術(shù)等現(xiàn)代技術(shù)領(lǐng)域也有著重要應(yīng)用?？赡孢壿嬀C合，就是按照可逆網(wǎng)絡(luò)無(wú)扇出、無(wú)反饋等約束條件和限制，實(shí)現(xiàn)相應(yīng)的可逆邏輯網(wǎng)絡(luò)，并使得代價(jià)盡可能小。目前，在可逆邏輯門(mén)網(wǎng)絡(luò)的構(gòu)造、可逆邏輯綜合的算法、規(guī)模、優(yōu)化、代價(jià)以及可逆邏輯綜合相關(guān)應(yīng)用等方面有許多問(wèn)題需要

2、解決。本文的主要貢獻(xiàn)在于：
　　 1.構(gòu)造了一個(gè)可逆邏輯門(mén)網(wǎng)絡(luò)級(jí)聯(lián)系統(tǒng)，主要工作包括：分析和證明了同型Toffoli門(mén)串聯(lián)輸出結(jié)果與Toffoli門(mén)個(gè)數(shù)之間的關(guān)系；給出了Toffoli門(mén)串聯(lián)網(wǎng)絡(luò)的計(jì)數(shù)；揭示了輸入向量中Hamming重量的位向量個(gè)數(shù)與位向量位數(shù)之間的關(guān)系；給出了Toffoli門(mén)串聯(lián)網(wǎng)絡(luò)變換種類(lèi)的計(jì)算方法；提出了能夠進(jìn)行Toffoli門(mén)串聯(lián)、并聯(lián)和混聯(lián)的網(wǎng)絡(luò)級(jí)聯(lián)算法。利用這些算法構(gòu)造了一個(gè)基于Toffoli門(mén)的可逆

3、網(wǎng)絡(luò)級(jí)聯(lián)系統(tǒng)，實(shí)驗(yàn)驗(yàn)證了該系統(tǒng)的有效性。
　　 2.在可逆邏輯綜合的模型構(gòu)造和代價(jià)分析方面，提出了正反控制可逆級(jí)聯(lián)模型；分析了正反控制可逆級(jí)聯(lián)模型的代價(jià)，給出了基于該模型可逆網(wǎng)絡(luò)中NOT門(mén)化簡(jiǎn)的方法。揭示了增加可逆門(mén)的綜合方法中對(duì)任意可逆函數(shù)收斂的性質(zhì)，提出了相應(yīng)的可逆綜合算法。部分NCMC Benchmark函數(shù)測(cè)試和結(jié)果分析表明，綜合過(guò)程中標(biāo)志可逆網(wǎng)絡(luò)最小化代價(jià)的無(wú)用輸出信息數(shù)和可逆門(mén)的數(shù)量都取得了比較理想的效果。
　

4、　 3.在邏輯函數(shù)可逆綜合方法中主要完成了下面三個(gè)方面的工作：
　　 (1）提出了基于SOP的邏輯函數(shù)優(yōu)化方法，該方法通過(guò)多輸出函數(shù)的蘊(yùn)涵項(xiàng)擴(kuò)展、積項(xiàng)集合的補(bǔ)集求解、布爾函數(shù)的無(wú)冗余覆蓋選擇和布爾函數(shù)的RM變換等一系列步驟，化簡(jiǎn)一個(gè)標(biāo)準(zhǔn)的邏輯函數(shù)。實(shí)驗(yàn)結(jié)果驗(yàn)證了上述過(guò)程中相關(guān)算法的有效性。給出了優(yōu)化后的邏輯函數(shù)轉(zhuǎn)化為FPRM的算法，以此變換SOP為正極性Reed-Muller形式。提出了一個(gè)可逆邏輯函數(shù)的綜合算法，使用固定極性

5、Reed-Muller分解，在每個(gè)分段綜合邏輯函數(shù)為T(mén)offoli門(mén)網(wǎng)絡(luò)。用NCMC Benchmark例題驗(yàn)證了算法的有效性。
　　 (2）證明了任意一個(gè)變換可以通過(guò)n-輪換和一個(gè)變換生成，因此任意相鄰的2-輪換置換可以通過(guò)至多兩個(gè)NOT門(mén)在無(wú)附加信息位的情況下生成，推導(dǎo)出任意可逆邏輯門(mén)網(wǎng)絡(luò)可以通過(guò)NOT門(mén)和2-CNOT門(mén)實(shí)現(xiàn)。給出了一個(gè)基于置換群的可逆邏輯門(mén)網(wǎng)絡(luò)級(jí)聯(lián)算法，并通過(guò)實(shí)例對(duì)算法進(jìn)行了驗(yàn)證。
　　 (3）提出

6、了基于布爾置換構(gòu)造可逆網(wǎng)絡(luò)的兩種方法：第一，詳細(xì)分析了布爾置換兩個(gè)重要的判定條件，給出了交換選擇滿(mǎn)足布爾置換條件平衡函數(shù)的方法，提出了通過(guò)布爾置換迭代構(gòu)造可逆網(wǎng)絡(luò)的算法。算法分析結(jié)果表明，采用該算法可以較快地構(gòu)造可逆網(wǎng)絡(luò)。第二，揭示了上置換群中的正形置換是一個(gè)n位可逆網(wǎng)絡(luò)，并分析了正形置換構(gòu)成一個(gè)可逆網(wǎng)絡(luò)的特點(diǎn)；證明了兩個(gè)可逆網(wǎng)絡(luò)級(jí)聯(lián)成一個(gè)可逆網(wǎng)絡(luò)等價(jià)于上置換群中兩個(gè)正形置換的積；提出了基于正形置換的可逆網(wǎng)絡(luò)級(jí)聯(lián)算法。
　　 4