段雪利，趙曙光，馮若飛

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

?

可逆邏輯電路邏輯圖及波形圖圖示化方法

段雪利，趙曙光，馮若飛

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

針對以邏輯表達式給定的可逆邏輯電路進行分析，并繪制出其可逆邏輯電路圖，仿真出波形圖，并將由仿真結(jié)果得到的真值表進行可逆化構(gòu)造。利用C語言編程實現(xiàn)，將相關(guān)結(jié)果以更直觀的形式展現(xiàn)，這在可逆邏輯電路的研究中具有創(chuàng)新性。

可逆邏輯電路；邏輯電路圖；仿真波形圖；可逆真值表

可逆邏輯電路及相關(guān)問題的研究源于對可逆計算理論的探索?？赡嬗嬎鉡1]是一門新興的研究領(lǐng)域?？赡孢壿嬰娐穂2-3](Reversible Logic Circuit)是能實現(xiàn)可逆計算的電路，由若干量子邏輯門[4]級聯(lián)而成，是對量子信息作一系列幺正變換以實現(xiàn)指定的邏輯功能，代表著可逆信息處理中以軟/硬件實現(xiàn)的可逆操作序列。雖對于可逆邏輯的研究，國內(nèi)外均取得了一定的研究成果，但可逆邏輯電路的研究仍處于初級階段。

本文針對以可逆邏輯表達式組給定的可逆邏輯電路，通過智能分析繪制出其可逆邏輯電路圖，進而根據(jù)其輸入狀態(tài)進行仿真，將仿真結(jié)果圖形化顯示，并對其真值表可逆性進行判斷，針對不可逆的真值表進行可逆化構(gòu)造。以上算法通過C語言實現(xiàn)，并通過具體的實驗實例來對結(jié)果進行驗證。

1 可逆邏輯電路圖及波形圖圖示化方法

1.1 可逆邏輯電路圖構(gòu)造

可逆邏輯門的表示方法是以異或運算為基礎(chǔ)，可逆邏輯函數(shù)采用“積之異或和”(ESOP)表達式取代“積之和”(SOP)表達式，所以可逆邏輯電路的構(gòu)造采用ESOP表達式(組)進行可逆邏輯門的級聯(lián)[5]。利用MCMT門即可實現(xiàn)可逆邏輯電路圖的構(gòu)造[6]，具體步驟如下：

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

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

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

步驟4 每個MCMT門的控制位作用于目標位，作為最后的輸出。

圖1 用MCMT門構(gòu)造可逆電路

其中，“●”和“○”表示控制端；“●”表示當該控制位的值為真時才對目標位起作用；“○”表示當該控制位的值為假時才對目標位起作用；“⊕”表示受控端。

1.2 電路仿真及真值表可逆化構(gòu)造

因可逆邏輯電路的邏輯函數(shù)[7]是以“積之異或和”(ESOP)表達式給出的，所以針對給定的可逆邏輯電路表達式組，在對其仿真之前要先獲取其的全部輸入狀態(tài)，然后根據(jù)其給定的具體表達式進行相應(yīng)的邏輯運算，即可仿真出其全部輸出狀態(tài)。

三輸入-三輸出的邏輯電路表達式組為

(1)

此電路表達式的輸入狀態(tài)分別為000、001、010、011、100、101、110、111。將8個狀態(tài)代入表達式中,進行相應(yīng)的邏輯運算得到該三輸入三輸出表達式的真值表。輸出狀態(tài)中有4個同時為000，這就違背了可逆邏輯電路輸入與輸出相映射的原則[8]。因此，要對該邏輯函數(shù)的真值表進行可逆化構(gòu)造[9]，構(gòu)造的基本原則是添加輔助位，其中,c為輸入輔助位；g為輸出輔助位，輸入添至前端，輸出添至后端。構(gòu)造后的真值表如表1所示。

表1 構(gòu)建后的可逆真值表

2 編程實現(xiàn)與結(jié)果驗證

上文闡述了針對給定的可逆邏輯表達式組，繪制其可逆邏輯電路、仿真以及對非可逆真值表可逆化構(gòu)造的詳細步驟，以下將用C語言實現(xiàn)上述功能，以更形象的方式表現(xiàn)可逆邏輯組合電路的輸入輸出關(guān)系，并分析可逆邏輯電路的功能與需求。

2.1 可逆邏輯電路圖構(gòu)造

步驟1 表達式輸入?？赡孢壿嬰娐返谋磉_式為“積之異或和”(ESOP)形式，輸入表達式時無法直接輸入“⊕”，故采用鍵盤上的“*”鍵替代，并用A、B、C、D等字母代替各輸入(其中大寫字母代表輸入為真，小寫字母代表輸入為假)，上文中三輸入三輸出函數(shù)即可表示為

(2)

步驟2 表達式讀入與檢測。將步驟1中的表達式在txt文件中輸入，如圖2所示。由程序來訪問該txt文件，程序依次讀入3個表達式，得出輸入和輸出的個數(shù)，并將輸入中相應(yīng)的“A”、“B”、“C”、“D”等字母轉(zhuǎn)化為對應(yīng)的ASCII碼存入數(shù)組中待用。根據(jù)輸入和輸出的個數(shù)確定控制線和目標線的個數(shù)。

圖2 txt中表達式輸入

步驟3 繪制區(qū)域劃分。根據(jù)屏幕的分辨率劃分繪制區(qū)域，并根據(jù)輸入輸出數(shù)的多少決定可逆邏輯網(wǎng)絡(luò)中每一個乘積項之間的距離；

步驟4 控制線繪制。根據(jù)輸入個數(shù)繪制輸入控制線，并根據(jù)輸入輸出的個數(shù)確定控制線下方輔助線的個數(shù)，在控制線及輔助線的左端標注字母進行區(qū)分，控制線的左端標注字母從“A”開始依次類推，輔助線左端全部置“0”；

步驟5 控制點繪制。從邏輯函數(shù)中的“F1”開始繪制控制點，其中大寫字母表示輸入為真，在相應(yīng)位置繪制實心圓，小寫字母表示輸入為假，在相應(yīng)位置繪制空心圓，繪制的具體位置根據(jù)每個字母的ASCII碼與“A”的ASCII差值決定。

步驟6 目標位繪制。根據(jù)“F1”、“F2”、“F3”3個表達式中“*”符號的個數(shù)，在該表達式對應(yīng)的輔助線上繪制異或圓，異或圓的半徑要大于控制點的半徑以便區(qū)分。

此時所有步驟完成，點擊程序運行按鍵開始執(zhí)行，繪制出的可逆邏輯電路如圖3所示。

圖3 可逆邏輯電路圖顯示結(jié)果

2.2 電路仿真及可逆化真值表構(gòu)造

識別表達式后根據(jù)表達式中輸入的個數(shù)生成輸入狀態(tài)，如有3個狀態(tài)則輸入狀態(tài)為000～111，有4個輸入則輸入狀態(tài)為0000～1111，依此類推。然后根據(jù)輸入狀態(tài)進行相應(yīng)的邏輯運算生成輸出狀態(tài)：計算出單獨每個積項的值之后，再根據(jù)異或運算的規(guī)則運算出該輸出的狀態(tài)。根據(jù)輸入輸出狀態(tài)繪制的仿真波形圖，如圖4所示。

圖4 仿真波形圖結(jié)果

下面將對該仿真結(jié)果的可逆性進行檢測：將輸出狀態(tài)由二進制轉(zhuǎn)化為十進制存放于數(shù)組，然后對數(shù)組中數(shù)字檢測是否有相同數(shù)字，并將該相同數(shù)字的二進制輸出。該例中檢測出有3個相同的“0”，輸出其二進制“000”，其對應(yīng)的真值表不可逆，需為其添加輔助位進行可逆化構(gòu)造。判斷相同輸出的個數(shù)，并根據(jù)相同的個數(shù)決定添加輔助位的個數(shù)，其中輸入輔助位添加至輸入前端，輸出輔助位添加至輸出后端[10]，本例具體添加情況詳見表1。最后將可逆構(gòu)造后的真值表輸出至txt文件中，如圖5所示。

圖5 構(gòu)造后的可逆真值表輸出結(jié)果

其中，“i”、“o”分別表示輸入和輸出，經(jīng)過可逆化構(gòu)造后輸入和輸出實現(xiàn)了相互映射。

3 結(jié)束語

介紹了可逆邏輯電路，進而闡述識別輸入的可逆邏輯表達式組生成可逆邏輯電路的具體步驟，以及通過仿真生成波形圖并加以圖示化的詳細過程，判斷生成真值表的可逆性，對于不可逆真值表進行可逆化構(gòu)造。通過C語言實現(xiàn)上述算法，并用具體實例驗證，實現(xiàn)了由邏輯表達式到邏輯電路、波形圖、真值表之間的轉(zhuǎn)化，這些研究為分析、理解和優(yōu)化可逆邏輯電路提供了幫助。

[1] Nielsen M,Chuang I. Quantum computation and quantum information[M]. Cambridge:Cambridge University Press, 2000.

[2] Bennett C H. Logical reversibility of computation[J].IBM Journal of Research & Development, 1973, 17(6):525-532.

[3] Shende V V, Prasad A K, Markov I L, et al. Synthesis of reversible logic circuits[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22(6):710-722.

[4] Fu Youfan,Chao Zhao,Qian Qile.The research on matrix transformation of 2-level quantum logic gates[C].Lanzhou:International Computer Conference on Wavelet Active Media Technology & Information Processing, 2013,9(3):231-234.

[5] 管致錦.可逆邏輯綜合[M].北京:科學(xué)出版社,2011.

[6] Maslov D, Dueck G W. Reversible cascades with minimal garbage[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23(11):1497-1509.

[7] Sleator T, Weinfurter H. Realizable universal quantum logic gates [J]. Physical Review Letters, 1995, 74(20):4087-4090.

[8] Rosenblum A. The quantum mechanical computer[M].MA,USA:Information Dynamics, Springer US, 1991.

[9] Gupta P, Agrawal A, Jha N K. An algorithm for synthesis of reversible logic circuits[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(11):2317-2330.

[10] Iwama K, Kambayashi Y, Yamashita S. Transformation rules for designing CNOT-based quantum circuits[C].Soul:Design Automation Conference,IEEE, 2002.

Method of Logic Diagram and Waveform Visualizing of Reversible Logic Circuit

DUAN Xueli, ZHAO Shuguang, FENG Ruofei

(School of Information Science and Technology, Donghua University, Shanghai 201620, China)

The logic expressions for the reversible logic circuit are analyzed, and the reversible logic circuit diagram and the simulation waveform are given. The reversible structure of the truth table obtained from the simulation results is provided. The relevant results are presented in an intuitive form by the use of C language programming, an innovative approach in the reversible logic circuit research.

reversible logic circuit; logic circuit diagram; simulation waveform; reversible truth table

2016- 01- 01

國家自然科學(xué)基金資助項目(61271114)

段雪利(1987-)，男，碩士研究生。研究方向：電子設(shè)計等。

10.16180/j.cnki.issn1007-7820.2016.11.002

TN79+

A