可逆邏輯表達式的識別和圖示方法

張 樂，趙曙光，肖華軍

(東華大學(xué)信息科學(xué)與技術(shù)學(xué)院，上海 201620)

可逆計算［1］是一種計算過程可逆的計算模型。在這種計算模型中，使用的能量較低，熵的增加會最小化。可逆邏輯電路設(shè)計即可逆邏輯綜合是可逆計算的重要研究內(nèi)容［2－5］。可逆邏輯綜合，就是用給定的可逆邏輯門，按照預(yù)期的邏輯功能和可逆網(wǎng)絡(luò)無扇出、無反饋等約束條件和限制，實現(xiàn)相應(yīng)的可逆邏輯網(wǎng)絡(luò)，并使得代價盡可能小［6］，其關(guān)鍵是以可逆邏輯門為基本單元，快速有效地生成性能指標，盡可地能優(yōu)化的可逆邏輯電路。目前可逆邏輯電路的研究仍然處于理論階段，且面臨著設(shè)計規(guī)模、設(shè)計代價、電路優(yōu)化等許多尚待解決的問題。

常用的可逆邏輯門都是基于異或的操作來實現(xiàn)的，使用該操作的邏輯門可通過簡單的表達式進行描述，所以可利用異或邏輯的基本方法對可逆邏輯電路進行綜合和化簡，通過綜合得到的異或表達式(組)來構(gòu)建可逆邏輯電路。本文針對可逆邏輯電路的特點，介紹了用擴展的可逆邏輯門構(gòu)造可逆邏輯電路的方法和步驟。重點闡述了可逆邏輯函數(shù)異或表達式得到可逆邏輯電路原理圖的具體編程方法，并通過C語言編程實現(xiàn)對可逆邏輯電路的圖形化顯示，然后通過具體的實驗證明了顯示結(jié)果的有效性。

1 可逆邏輯門概述

可逆邏輯門是可逆邏輯電路的基本構(gòu)件，其特點是輸入端與輸出端的個數(shù)相等，且各輸入組合之間是一一對應(yīng)關(guān)系。一個n輸入n輸出的二值邏輯門稱為n位可逆邏輯門，或稱為(n，n)可逆門。

1.1 常用的可逆邏輯門

目前，常用的可逆邏輯門主要有一位，兩位以及3位可逆邏輯門。一位可逆邏輯門也稱為(1，1)可逆邏輯門，如NOT門，其作用是使0變成1或1變成0。兩位可逆邏輯門常用的有Feynman門，也稱控制非門(Control－not Gate)，簡稱 CNOT 門［7］。Feynman門有兩位輸入，一位作為控制位(Control Bit，記為C)，另一位作為目標位(Target Bit，記為T)。3位可逆邏輯門主要有CCNOT門，由麻省理工學(xué)院的Toffoli于1980年提出，所以也稱 Toffoli門［8］。

圖1 NOT門

圖2 CNOT門

圖3 Toffili門

其中，“●”表示正向控制端;“⊕”表示受控端。

1.2 擴展的可逆邏輯門

PNC(Positive/Negative Control)門［9］是 在 一 般Toffoli門的基礎(chǔ)上進行衍變和推廣而得到的，也是一個雙控門，但其是正、反控制稱為正/反控制門。有3個輸入位，其中兩個作為控制位，另一位作為目標位?？刂莆挥姓粗?，當正控制位的值為1，反控制位為0時，目標位的值取反，否則目標位的值保持不變。在可逆邏輯網(wǎng)絡(luò)中，PNC門一般如圖4所示。

圖4 PNC門

其中，“●”表示正向控制端;“○”表示反向控制端;“⊕”表示受控端。

MCMT 門(Multiple Control Multiple Target Gate，多控制多目標門)［9］，又稱擴展的PNC門，可記為MCMT(C;T)，其中C為控制位集合，T為目標位集合。一個具有n位控制位、k位目標位的MCMT門實現(xiàn)變換，其邏輯函數(shù)可表示為

MCMT門在實際應(yīng)用中更為廣泛，其靈活性在于，設(shè)置了不同的參數(shù)后，MCMT門可表示其他的基本可逆邏輯門:

(1)當 C=φ，T={xi0}，a0=1時，MCMT門為NOT門。

(2)當C={x0}，T={xi0}，a0=1，且x0時，MCMT門為CNOT門。

(3)當C={x0，x1}，T={xi0}，a0=1，且=x0和=x1時，MCMT門為Toffoli門。

2 可逆邏輯電路構(gòu)造方法

可逆邏輯電路的可逆性特點決定了傳統(tǒng)的邏輯門已不再使用，以異或運算為基礎(chǔ)的可逆邏輯門將其取代，邏輯函數(shù)中“積之異或和”(ESOP)表達式取代“積之和”(SOP)表達式成為了可逆邏輯最適用的表達形式，所以由ESOP表達式(組)利用可逆邏輯門級聯(lián)便可構(gòu)造可逆邏輯電路。

利用MCMT門，便可實現(xiàn)對多輸入多輸出可逆邏輯電路的構(gòu)造［6］。用MCMT門實現(xiàn)任意多輸入多輸出異或表達式的具體步驟如下:

步驟1 根據(jù)輸入變量設(shè)置控制位集合。

步驟2 根據(jù)輸出變量的個數(shù)添加輔助位作為目標位，并初始化到0狀態(tài)。

步驟3 依次為每個積項添加一個MCMT門，這個MCMT門的控制端作用于該積項中的各個輸入變量。

步驟4 每個MCMT門的控制位作用于相應(yīng)的各個目標位，然后將各個目標位作為最后的輸出。

利用MCMT門構(gòu)造可逆邏輯網(wǎng)絡(luò)具體的步驟如下:

例1 ESOP表達式形式的多輸入多輸出邏輯函數(shù)表達式組為

步驟1 為使網(wǎng)絡(luò)可逆，添加4位輔助位存儲輸出，共8位。

步驟2 添加5個分別以第一個函數(shù)中各個積項中的變量為控制位的MCMT門，即第一個MCMT門以x0，x1，x2和x3為控制位，第二個以x0，x1和x3為控制位，第3個以x0，x1和x3位控制位，第4個以 x1和 x2為控制位，第 5 個以 x0，x1，x2，x3為控制位。

步驟3 按照步驟2，依次為邏輯函數(shù)F2，F(xiàn)3和F4添加與各函數(shù)中乘積項對應(yīng)的MCMT門。

步驟4 將各個輔助位作為最后的輸出，完成可逆邏輯電路的構(gòu)造。

通過手工繪制例1的可逆邏輯電路構(gòu)造結(jié)果如圖5所示，其中“●”表示控制端，表示當該控制位的值為真時才對目標位起作用，“○”表示控制端，表示當該控制位的值為假時才對目標位起作用，“⊕”表示受控端。

圖5 利用MCMT門實現(xiàn)可逆邏輯電路示例

對于多輸入單輸出可逆邏輯電路的構(gòu)造，須要利用MCMT門的一種特殊情況MCT門，簡稱多控門，該門只有一個目標位。通過添加一輔助位便可用MCT門實現(xiàn)可逆邏輯網(wǎng)絡(luò)。CNOT門、Toffoli門以及擴展的PNC門等都屬于MCT門。

用MCT門實現(xiàn)任意的異或表達式的具體步驟如下:

步驟1 根據(jù)輸入變量設(shè)置控制位集合。

步驟2 添加一位輔助位作為目標位，并初始化到0狀態(tài)。

步驟3 依次根據(jù)每個乘積項添加一個MCT門，該MCT門的控制端為相應(yīng)乘積項所含輸入變量的組合。

步驟4 在所有MCT門的作用下，將輔助位的輸出作為最后的輸出。

例2 邏輯函數(shù)的ESOP表達式為f(x0，x1，x2)=，用MCT門構(gòu)建可逆邏輯電路如圖6所示。

圖6 利用MCT門實現(xiàn)可逆邏輯電路示例

3 表達式的識別和圖示方法

通過對可逆邏輯電路的圖形化顯示的研究，能直觀地反映輸入輸出關(guān)系，以驗證是否達到預(yù)期目標。所以本文在給定可逆邏輯組合電路表達式的情況下，利用可逆邏輯電路的構(gòu)造方法，通過C語言編程，以形象的方式表達可逆邏輯組合電路的輸入輸出關(guān)系，分析可逆邏輯電路的功能和需求，對可逆邏輯電路原理圖進行圖形化顯示和驗證。

利用C語言編程，對可逆邏輯電路進行圖形化顯示的具體方法和步驟如下:

步驟1 根據(jù)可逆邏輯電路的構(gòu)造方法，首先需要輸入邏輯函數(shù)的變量個數(shù)及輸出個數(shù)，從而確定需畫出的控制位個數(shù)以及需要添加的輔助位個數(shù)，以及確定是利用MCT還是MCMT門進行構(gòu)造可逆邏輯電路。

步驟2 將邏輯函數(shù)以字符形式輸入。由于可逆邏輯電路的邏輯表達式一般為積之異或和的形式，所以邏輯函數(shù)主要為基于異或門的組合邏輯電路，如果是其他形式的邏輯表達式，如SOP表達式，則無法得到原理圖。所以，需對輸入的表達式進行判斷，若不是ESOP表達，則提示輸入錯誤，需重新輸入。邏輯函數(shù)的變量若輸入為真，則用A～Z表示，為假則用A'～Z'表示。

步驟3 根據(jù)輸入輸出的個數(shù)，在相應(yīng)的位置上畫出與輸入數(shù)相等的控制線以及與輸出個數(shù)相等的目標線。

步驟4 對讀取的邏輯表達式進行解析，判斷表達式等號前的字符個數(shù)個，并將表達式等號后的字符型轉(zhuǎn)換為整型。

步驟5 通過統(tǒng)計每個表達式中異或符號的個數(shù)，獲得每個表達式中乘積項的個數(shù)，并保存。根據(jù)每個表達式乘積項的個數(shù)在該表達式對應(yīng)的輔助線上畫上“異或圓”，形如，表示目標位。

步驟6 根據(jù)獲取每個表達式的乘積項的個數(shù)依次為每個函數(shù)添加對應(yīng)的MCMT(MCT)門個數(shù)。具體方法是:首先取第一個函數(shù)，函數(shù)中的每個變量都已轉(zhuǎn)換成了整型，通過將該變量減去字符‘A’所代表的整數(shù)值得到需要再哪條控制線上畫控制點，然后判斷該變量后是否有‘’’字符，如果有則畫空心圓，否則畫實心圓，表示該變量是取真還是取假有效。按此方法對每個函數(shù)進行處理。

步驟7 判斷所有的邏輯函數(shù)是否都已處理完畢，如果處理完畢則輸出最終電路圖。

4 編程實現(xiàn)與結(jié)果分析

在Windows7系統(tǒng)下，用VC++6.0對上述識別和圖示方法進行了編程實現(xiàn)。編程中特意引入EasyX庫，以便在VC++6.0中實現(xiàn)Turbo C的繪圖功能。

所編制的程序可讀對應(yīng)格式的文件作為輸入，也可通過人機對話輸入邏輯表達式。利用“*”代替鍵盤上無法直接輸入的異或“⊕”符號。在人機對話輸入提示中以及文本中，i表示輸入變量的個數(shù);o表示輸出變量的個數(shù)。為了驗證仿真方法的有效性，特針對多輸入多輸出以及多輸入單輸出函數(shù)分別進行如下實驗:

實驗1 通過讀取例1中四輸入四輸出邏輯函數(shù)表達式組的txt格式文件如圖7所示，運行結(jié)果如圖8所示。

圖7 四輸入四輸出異或邏輯表達式組的輸入

圖8 四輸入四輸出邏輯表達式組的可逆邏輯圖顯示結(jié)果

該例實際上涉及了非可逆邏輯表達式到可逆邏輯表達式的轉(zhuǎn)換。受到可逆性制約，可逆邏輯網(wǎng)絡(luò)的輸出數(shù)必須等于輸入數(shù)，所以需添加輔助位來保存邏輯函數(shù)的輸出值，在此添加4位輔助位存儲輸出，并初始化到0狀態(tài)，依次為每個積項(AND項)添加一個MCMT門，這個MCMT門的控制端作用于該積項中的各個變量，每個MCMT門的控制位作用于目標位，作為最后的輸出。通過與例1手工繪制的可逆邏輯原理圖比較，可得該顯示結(jié)果準確有效。

實驗2 針對3輸入單輸出異或邏輯表達式即例2的邏輯表達式 F(A，B，C)=AC⊕BC'⊕B'C⊕AB'C進行實驗，其輸入過程和運行結(jié)果分別如圖9，圖10所示。

圖9 三輸入單輸出異或邏輯表達式的輸入

圖10 三輸入單輸邏輯表達式的可逆邏輯圖顯示結(jié)果

該例涉及了非可逆邏輯表達式到可逆邏輯表達式的轉(zhuǎn)換。可逆邏輯電路的輸出數(shù)必須等于輸入數(shù)，所以需添加輔助位來保存邏輯函數(shù)的輸出值，在此添加1位輔助位存儲輸出，并初始化到0狀態(tài)。圖中A，B，C的3個控制端，白色實心圓表示該控制位取真有效，空心小圓表示該控制位取反有效，輔助位上大圓表示控制位對目標位的控制。通過與例2手工繪制的可逆邏輯原理圖進行比較，可知該顯示結(jié)果準確有效。

5 結(jié)束語

介紹了常用可逆邏輯門，針對可逆邏輯電路的特點，介紹了用擴展的可逆邏輯門構(gòu)造，可逆邏輯電路的方法和步驟。重點闡述了通過編程識別可逆邏輯函數(shù)異或表達式，提取可逆邏輯電路結(jié)構(gòu)信息的具體算法。通過C語言編程實現(xiàn)了對可逆邏輯電路原理圖的圖形化顯示，并通過實驗1和實驗2驗證了顯示結(jié)果的有效性。

［1］ Frank M P．Introduction to reversible computing:motivation，progress，and challenges［C］．Proceedings of the 2nd Conference on Computing Frontiers，2005:385 －390．

［2］ Landauer R．Irreversibility and heat generation of the computing process［J］．IBM Journal of Research and Development，1961，5(3):183 －191．

［3］ Bennett C H．Logical reversibility of computation［J］．IBM Journal of Research and Development，1973，17(6):525－532．

［4］ Andrel B Khlopotine，Perkowski M，Pawel Kerntopf．Reversible logic synthesis by iterative composition［C］．Proceedings of IWLS，2002:261 －266．

［5］ Miller D M，Maslov D，Dueck G W．A transformation based algorithm for reversible logic synthesis［C］．Anaheim California，USA:Design Automation Conference(DAC)，IEEE/ACM，2003:318 －323．

［6］ Fredkin E，Toffoli T．Conservative logic［J］．International Journal of Theoretical Physics，1982(21):219 －253．

［7］ Feynman R．Quantum mechanical computers［J］．Optic News，1985(6):11－20．

［8］ Toffoli T，De Bakker J W，Van Leeuwen Jeds．Reversible Computing Automata，Languages and Programming［M］．New York:Springer Conpration，1980．

［9］ 管致錦．可逆邏輯綜合［M］．北京:科學(xué)出版社，2010．