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

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

【學(xué)位級(jí)別】：碩士

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



本文編號(hào)：3824570