可逆邏輯綜合在量子計算和解決計算機熱耗問題中起著關鍵性的作用，而可逆邏輯綜合的規(guī)模一直是研究者們關心的重要內(nèi)容，ω階的可逆邏輯函數(shù)共有2^ω!個，隨著階數(shù)的增長，可逆邏輯函數(shù)的數(shù)目激增，要完全綜合這么多的可逆邏輯函數(shù)，難度可想而知。由于可逆邏輯函數(shù)的分類在可逆邏輯綜合中可以使模板重復使用，從而提高綜合的效率，所以可逆邏輯函數(shù)分類成為解決規(guī)模問題的重要方法。 本文正是針對這一主題，把可逆邏輯函數(shù)的NP-NP等價作為研究對象，對可逆邏輯函數(shù)分類及等價性判定做了探討。其主要內(nèi)容為： 1.提出可逆邏輯函數(shù)NP-NP等價的定義，該定義是把布爾函數(shù)NP-N等價的定義推廣到可逆邏輯函數(shù)得到的。通過把可逆邏輯函數(shù)表示成置換群中的置換，把可逆邏輯函數(shù)NP-NP等價分類轉(zhuǎn)化為置換群的雙陪集等價分類。 2.研究可逆邏輯非門和交換門對應置換構成的子群的性質(zhì)，結合可逆邏輯函數(shù)NP-NP等價類的特性，對群論中計算雙陪集個數(shù)的公式進行了改進，完成了可逆邏輯函數(shù)NP-NP等價類個數(shù)的計算。如果用窮舉的方法，在普通計算機上最多只能計算出3階可逆邏輯函數(shù)NP-NP等價類個數(shù)，而用該方法在相同的計算機上...

【文章頁數(shù)】：54 頁

【學位級別】：碩士

【文章目錄】：
摘要
ABSTRACT
第一章 緒論
    1.1 課題研究的背景
    1.2 可逆邏輯函數(shù)分類的意義
    1.3 可逆邏輯綜合及可逆邏輯函數(shù)分類的研究現(xiàn)狀
    1.4 論文的結構安排
第二章 基礎知識和相關理論
    2.1 布爾函數(shù)與可逆邏輯函數(shù)
        2.1.1 布爾函數(shù)及其主要表達式
        2.1.2 可逆邏輯函數(shù)與可逆邏輯門
    2.2 等價關系與集合的分類
    2.3 群論基礎知識
        2.3.1 群與子群
        2.3.2 置換群
        2.3.3 共軛與陪集
        2.3.4 群的作用
    2.4 本章小結
第三章 可逆邏輯函數(shù) NP-NP 等價類個數(shù)的計算
    3.1 可逆邏輯函數(shù)的置換表示
    3.2 理論基礎
        3.2.1 邏輯非門與交換門的性質(zhì)
        3.2.2 可逆邏輯函數(shù) NP-NP 等價
    3.3 算法
    3.4 算法實驗及其結果
    3.5 本章小結
第四章 可逆邏輯函數(shù) NP-NP 等價判定
    4.1 三階可逆邏輯函數(shù)的 NP-NP 等價判定
        4.1.1 改進的 J.E.Savage 算法
        4.1.2 布爾函數(shù)固定極 RM 展開式極性的確定
        4.1.3 輔因子的碼值向量
        4.1.4 三階可逆邏輯函數(shù) NP-NP 等價判定
    4.2 可逆邏輯函數(shù) NP-NP 等價判定的代數(shù)方法
    4.3 本章小結
第五章 總結與展望
    5.1 論文總結
    5.2 工作展望
致謝
參考文獻
碩期間取得的研究成果



本文編號：3824570