題-1_100_100.jpg)
基本信息
- 項目名稱：
- 基于可逆邏輯門編碼和變進制數(shù)的可逆網(wǎng)絡(luò)級聯(lián)
- 小類：
- 信息技術(shù)
- 簡介：
- 作品提出了基于可逆邏輯門編碼和變進制數(shù)的可逆門網(wǎng)絡(luò)級聯(lián)方法。該方法按垂直線條數(shù)從小到大，控制位個數(shù)從小到大自動構(gòu)造不同輸出向量所對應(yīng)網(wǎng)絡(luò)并且能夠自動生成所需的單個可逆網(wǎng)路或批量連續(xù)序號可逆網(wǎng)絡(luò)。通過變進制數(shù)與可逆網(wǎng)絡(luò)輸出向量的對應(yīng)關(guān)系，能夠快速地找到可逆網(wǎng)絡(luò)輸出向量所對應(yīng)的序號，精準(zhǔn)地判斷輸出向量是否已出現(xiàn)，減少了搜索的次數(shù)和搜索空間。與已有的Benchmark例題比較，控制位數(shù)、可逆邏輯門數(shù)得到一定改善。 本作品的研究結(jié)果可以直接應(yīng)用于低功耗電路的可逆邏輯設(shè)計和可逆邏輯門庫的構(gòu)建，其中可逆邏輯門網(wǎng)絡(luò)自動生成算法已成為可逆邏輯設(shè)計平臺的組成部分。
- 詳細介紹：
- 可逆門的邏輯級聯(lián)是可逆邏輯綜合的重要組成部分?？赡孢壿嬀C合是一個新興的研究領(lǐng)域，它是可逆計算研究的主要內(nèi)容，并在低功耗電路設(shè)計、信息安全、納米技術(shù)等其它一些現(xiàn)代科學(xué)領(lǐng)域有著重要應(yīng)用。 由于構(gòu)造可逆邏輯門網(wǎng)絡(luò)有很強的限制，因此一直沒有非常系統(tǒng)有效的設(shè)計方法，網(wǎng)絡(luò)構(gòu)造的規(guī)模也得不到提高。本作品通過對網(wǎng)絡(luò)的輸入/輸出位、垂直線及水平線編號，構(gòu)造出可逆網(wǎng)絡(luò)的基本元素，同時基于變進制數(shù)，給出了可逆網(wǎng)絡(luò)輸出向量與序號之間的對應(yīng)方法，調(diào)用可逆網(wǎng)絡(luò)的構(gòu)造函數(shù)自動構(gòu)建網(wǎng)絡(luò)。該構(gòu)造函數(shù)按垂直線條數(shù)從小到大，控制位個數(shù)從小到大構(gòu)造不同輸出向量所對應(yīng)網(wǎng)絡(luò)，自動生成所需的單個可逆網(wǎng)絡(luò)或批量連續(xù)序號可逆網(wǎng)絡(luò)。而通過使用變進制數(shù)的方法，能夠快速、方便地找到可逆網(wǎng)絡(luò)輸出向量所對應(yīng)的序號。這種命名方法和變進制的靈活使用在解決可逆網(wǎng)絡(luò)級聯(lián)的問題中是首次使用，并且較好地解決了可逆網(wǎng)絡(luò)級聯(lián)規(guī)模小的問題和網(wǎng)絡(luò)存儲問題。 可逆邏輯門級聯(lián)比較多的集中在3-4輸入/輸出的可逆網(wǎng)絡(luò)中，而本作品能夠自動生成3輸入/輸出以上的可逆網(wǎng)絡(luò)。由于n變量可逆邏輯函數(shù)的數(shù)量是(2^n)!，目前已知的利用窮盡搜索法對所有3變量可逆邏輯函數(shù)最小化的技術(shù)還無法實現(xiàn)相關(guān)的存儲。采用群論作為分析工具應(yīng)用到可逆門的級聯(lián)中，在內(nèi)存需求和算法效率上有了一定改善，但還需要進行大量的排序，無法實現(xiàn)規(guī)模較大的可逆網(wǎng)絡(luò)級聯(lián)。本作品實現(xiàn)了全部1-4輸入/輸出和部分5輸入/輸出Benchmark例題的Toffoli可逆邏輯門網(wǎng)絡(luò)的級聯(lián)和相關(guān)存儲。 在D.Maslov等人提出的模板方法中，由于模板種類的限制，只能實現(xiàn)部分可逆邏輯網(wǎng)絡(luò)，無法實現(xiàn)全部可逆邏輯門網(wǎng)絡(luò)的級聯(lián)，本作品能夠支持生成批量甚至是全部的可逆網(wǎng)絡(luò)，并能精準(zhǔn)地判斷輸出向量是否曾出現(xiàn)，大大減小了搜索空間和搜索次數(shù)。與Benchmark例題比較，在可逆邏輯門的數(shù)量和控制位的數(shù)量上都有一定的優(yōu)勢（見論文中相關(guān)結(jié)果分析和測試報告）。 本作品的研究結(jié)果可以直接應(yīng)用于低功耗電路的可逆邏輯設(shè)計和可逆邏輯門庫的構(gòu)建，其中可逆邏輯門網(wǎng)絡(luò)自動生成算法已成為可逆邏輯設(shè)計平臺的組成部分，并實現(xiàn)了相應(yīng)的可逆網(wǎng)絡(luò)自動生成演示系統(tǒng)。 本作品的重要組成部分“The Generation of the Reversible Gate Network-based the Variable System Numbers”（基于變進制數(shù)可逆門網(wǎng)絡(luò)的生成）和“The Reversible Network Cascade Based on Reversible Logic Gate Coding Method”（基于可逆邏輯門編碼方法的可逆網(wǎng)絡(luò)級聯(lián)）均由本參賽作品的主要學(xué)生完成，已分別被“The 5th International Conference on Natural Computation (ICNC'09)”（2009年第五屆自然計算國際學(xué)術(shù)會議）和“Fifth International Conference on Information Assurance and Security (IAS-2009)”（2009年第五屆信息保障與安全國際會議）錄用，并將在IEEE Computer Society出版。
作品專業(yè)信息
撰寫目的和基本思路
- 目的：能精準(zhǔn)判斷可逆網(wǎng)絡(luò)級聯(lián)過程中狀態(tài)空間是否出現(xiàn)，減少搜索次數(shù)和空間，自動生成可逆網(wǎng)絡(luò)，克服網(wǎng)絡(luò)規(guī)模小、級聯(lián)代價高等問題。 基本思路：首先以Toffoli門為基礎(chǔ)，構(gòu)建可逆網(wǎng)絡(luò)模型；對可逆網(wǎng)絡(luò)的輸入/輸出位、垂直線及水平線編號；構(gòu)造出具有不同意義的Toffoli門作為基本元素；給出基于變進制數(shù)的可逆網(wǎng)絡(luò)輸出向量序號表示方法；調(diào)用基本元素生成可逆網(wǎng)絡(luò)并進行相應(yīng)的實驗驗證。
科學(xué)性、先進性及獨特之處
- 科學(xué)性：本作品為可逆邏輯綜合的重要組成部分。研究過程中提出了相關(guān)定理和算法，通過國際標(biāo)準(zhǔn)的Benchmark例題驗證算法的正確性和有效性。 先進性：可逆邏輯門級聯(lián)比較多的集中在3-4輸入/輸出網(wǎng)絡(luò)，本作品實現(xiàn)了1-4輸入/輸出網(wǎng)絡(luò)和5輸入/輸出Benchmark例題。 獨特之處：能自動生成所需的單個或批量可逆網(wǎng)絡(luò)，突破了模板種類限制，較好地解決了網(wǎng)絡(luò)級聯(lián)規(guī)模小和存儲問題。
應(yīng)用價值和現(xiàn)實意義
- 可逆門網(wǎng)絡(luò)級聯(lián)是一個新興的研究領(lǐng)域，它是量子計算和量子信息技術(shù)研究的重要組成部分，并在低功耗電路設(shè)計、信息安全、納米技術(shù)等其它一些現(xiàn)代科學(xué)領(lǐng)域有著重要應(yīng)用。 本課題的研究結(jié)果可以直接應(yīng)用于低功耗電路的可逆邏輯設(shè)計和可逆邏輯門庫的構(gòu)建，其中3輸入/輸出的可逆網(wǎng)絡(luò)的部分結(jié)果與可逆全加器的邏輯部件相對應(yīng)。
學(xué)術(shù)論文摘要
- 本文提出了基于可逆邏輯門編碼和變進制數(shù)的可逆網(wǎng)絡(luò)級聯(lián)方法。該方法按垂直線條數(shù)從小到大，控制位個數(shù)從小到大自動構(gòu)造不同輸出向量所對應(yīng)的網(wǎng)絡(luò)并且能夠自動生成所需的單個可逆網(wǎng)路或批量連續(xù)序號可逆網(wǎng)絡(luò)。通過變進制數(shù)與可逆網(wǎng)絡(luò)輸出向量的對應(yīng)關(guān)系，能夠快速地找到可逆網(wǎng)絡(luò)輸出向量所對應(yīng)的序號，精準(zhǔn)地判斷輸出向量是否已出現(xiàn)，大大減少了搜索的次數(shù)和搜索空間。與已有的Benchmark例題比較，控制位數(shù)、可逆邏輯門數(shù)得到一定改善。
獲獎情況
- 本作品的重要組成部分"The Generation of the Reversible Gate Network-based the Variable System Numbers"(基于變進制數(shù)可逆門網(wǎng)絡(luò)的生成)和"The Reversible Network Cascade Based on Reversible Logic Gate Coding Method"(基于可逆邏輯門編碼方法的可逆網(wǎng)絡(luò)級聯(lián))均由本參賽作品的主要學(xué)生完成，已分別被"The 5th International Conference on Natural Computation (ICNC'09)"(2009年第五屆自然計算國際學(xué)術(shù)會議)和"Fifth International Conference on Information Assurance and Security (IAS-2009)"(2009年第五屆信息保障與安全國際會議)錄用，并將在IEEE Computer Society出版。 本作品獲得某大學(xué)第二屆大學(xué)生課外學(xué)術(shù)科技作品競賽自然科學(xué)類論文一等獎。
鑒定結(jié)果
- “挑戰(zhàn)杯”江蘇省選拔賽專家意見：“可逆邏輯電路設(shè)計是新的方向，有廣泛應(yīng)用前景，本作品取得一定的研究成果”。
參考文獻
- [1] 李志強，陳漢武，徐寶文，劉文杰，基于HaSH表的量子可逆邏輯電路綜合的快速算法，計算機研究與發(fā)展，2008，45（12）:2162-2171. [2] Yang G., Song X W, Hung N. Perkowski, Group theory based synthesis of binary reversible circuits. The 3rd Annual Conference on Theory and Applications of Models of Computation(TAMC), Anaheim California, USA: IEEE/ACM, 2006, p. 365–374. [3] D. Maslov, G.W. Dueck, and D.M. Miller. Synthesis of Fridkin-Toffoli reversible networks. IEEE Transactions on VLSI systems, 2005, 13(6): 765-769. [4] D. Maslov , G. W. Dueck , D. M. Miller, Techniques for the synthesis of reversible Toffoli networks, ACM Transactions on Design Automation of Electronic Systems (TODAES), 2007(12): 42-46. [5] Pawel Kerntopf. A new heuristic algorithm for reversible logic synthesis. DAC 2004, p.834-837. [6] K. Iwama, Y. Kambayashi, S. Yamashita. Transformation rules for designing CNOT-based quantum circuits. Design Automation Conference, New Orleans, Louisiana, USA, ACM, 2002(149): 419-424.
同類課題研究水平概述
- 可逆邏輯門網(wǎng)絡(luò)生成問題的研究是隨著近些年量子計算和量子信息以及集成電路等技術(shù)的需求和發(fā)展才被真正給予重視，尚處于發(fā)展階段。 盡管近幾年來不斷有新的可逆門級聯(lián)模型和可逆門網(wǎng)絡(luò)級聯(lián)算法的研究成果出現(xiàn)，但目前可逆門級聯(lián)模型及其相關(guān)算法所能實現(xiàn)的可逆門網(wǎng)絡(luò)仍然存在著網(wǎng)絡(luò)規(guī)模小、級聯(lián)代價高、級聯(lián)過程中時空復(fù)雜度高等一系列問題。 Shende提出了3輸入變量可逆門的網(wǎng)絡(luò)級聯(lián)方法，M.Perkowski首先把分解因式方法用到可逆邏輯設(shè)計上。Iwama 等人給出了CNOT門的網(wǎng)絡(luò)級聯(lián)規(guī)則，分析了CNOT 門序列順序變化的規(guī)律，其輸出是標(biāo)準(zhǔn)型的Toffoli門，這個標(biāo)準(zhǔn)型是用PPRM直接實現(xiàn)可逆,同時也是一個Zhegalkin多項式。Iwama證明了任何一個可逆網(wǎng)絡(luò)都能通過確定的可逆操作得到一個標(biāo)準(zhǔn)型。這樣，標(biāo)準(zhǔn)型可以轉(zhuǎn)化為一個最小化可逆邏輯門網(wǎng)絡(luò)。遺憾的是，他們沒有給出任何通過變換集簡化可逆邏輯門網(wǎng)絡(luò)的方法。 Shende等人利用窮盡搜索法對所有3變量可逆邏輯函數(shù)最小化進行了研究，結(jié)果表明，n變量可逆邏輯函數(shù)的數(shù)量是(2^n)!，用他們的技術(shù)還無法實現(xiàn)相關(guān)的存儲。G.Yang等人嘗試采用群論作為分析工具應(yīng)用到可逆門的級聯(lián)中，在內(nèi)存需求和算法效率上有了一定改善，但還需要進行大量的排序，只能實現(xiàn)部分可逆邏輯網(wǎng)絡(luò)，而且網(wǎng)絡(luò)級聯(lián)的規(guī)模較小。Dmitri Maslov等人提出了模板的方法進行可逆邏輯門級聯(lián)，由于模板種類的限制，無法實現(xiàn)全部可逆邏輯門網(wǎng)絡(luò)的級聯(lián)。 我國在可逆邏輯門級聯(lián)的研究也取得了一些重要成果。東南大學(xué)陳漢武等人實現(xiàn)了4輸入/輸出可逆邏輯門網(wǎng)絡(luò)的級聯(lián)。 本作品實現(xiàn)了全部1-4輸入/輸出可逆網(wǎng)絡(luò)和部分5輸入/輸出Benchmark例題的Toffoli可逆邏輯門網(wǎng)絡(luò)的級聯(lián)和相關(guān)存儲，與Benchmark例題比較，在可逆邏輯門的數(shù)量和控制位的數(shù)量上都有一定的優(yōu)勢。
