可逆邏輯門與可逆邏輯電路的Petri網(wǎng)建模與分析.pdf

1、Petri網(wǎng)是對離散并行系統(tǒng)建模的有效工具之一。Petri網(wǎng)的結(jié)構(gòu)有直觀的圖形表示，也有基于數(shù)學工具的抽象表述方式。它的理論發(fā)展為分析系統(tǒng)行為和計算機科學提供堅實的理論基礎(chǔ)。Petri網(wǎng)已被廣泛的應(yīng)用于計算機科學，分布式計算以及并發(fā)系統(tǒng)的建模與分析當中。
　　本文利用Petri網(wǎng)對量子計算模型的核心可逆邏輯門與大型的可逆邏輯電路進行建模與分析。首先根據(jù)邏輯電路門（包括與門和非門等）的Petri網(wǎng)模型得到可逆邏輯門Fredkin門的

2、Petri網(wǎng)模型，進而對建立的Petri網(wǎng)模型的可達性、并發(fā)性、有界性、結(jié)構(gòu)有界性、死鎖和活性等特性進行分析。將Fredkin門的Petri網(wǎng)模型轉(zhuǎn)化為嚴格的數(shù)學表達方式后進行分析。通過分析得到Fredkin可逆邏輯門的Petri網(wǎng)模型是結(jié)構(gòu)有界、結(jié)構(gòu)守恒的、不存在死鎖、陷阱和沖突，并且存在兩對并發(fā)變遷，但是Fredkin可逆邏輯門的Petri網(wǎng)模型不是活性網(wǎng)。
　　可逆邏輯電路是量子計算模型的核心結(jié)構(gòu)，利用可逆邏輯門可以組建大型

3、的可逆邏輯電路。在Fredkin門的Petri網(wǎng)基礎(chǔ)上，本文進一步對大型的可逆邏輯電路進行Petri建模。由可逆邏輯門組成的可逆邏輯電路在一定程度上能夠保持Petri網(wǎng)的可達性、并發(fā)性、有界性、結(jié)構(gòu)有界性、死鎖、活性等特性；反之，一部分可逆邏輯電路的Petri網(wǎng)模型具備的特性是Fredkin可逆邏輯門所不具備的，通過分析得到死鎖、活性以及可達性是比較典型的三個滿足上述特征的特性。通過分析可逆邏輯門的每個輸入與輸出的關(guān)系以及可逆邏輯電路中