可逆計算中邏輯綜合若干問題研究.pdf

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

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

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

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

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

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