段雪利，趙曙光，馮若飛

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

?

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

段雪利，趙曙光，馮若飛

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

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

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

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

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

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

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

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

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

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

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

步驟4 每個(gè)MCMT門(mén)的控制位作用于目標(biāo)位，作為最后的輸出。

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

其中，“●”和“○”表示控制端；“●”表示當(dāng)該控制位的值為真時(shí)才對(duì)目標(biāo)位起作用；“○”表示當(dāng)該控制位的值為假時(shí)才對(duì)目標(biāo)位起作用；“⊕”表示受控端。

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

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

三輸入-三輸出的邏輯電路表達(dá)式組為

(1)

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

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

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

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

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

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

(2)

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

圖2 txt中表達(dá)式輸入

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語(yǔ)

介紹了可逆邏輯電路，進(jìn)而闡述識(shí)別輸入的可逆邏輯表達(dá)式組生成可逆邏輯電路的具體步驟，以及通過(guò)仿真生成波形圖并加以圖示化的詳細(xì)過(guò)程，判斷生成真值表的可逆性，對(duì)于不可逆真值表進(jìn)行可逆化構(gòu)造。通過(guò)C語(yǔ)言實(shí)現(xiàn)上述算法，并用具體實(shí)例驗(yàn)證，實(shí)現(xiàn)了由邏輯表達(dá)式到邏輯電路、波形圖、真值表之間的轉(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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61271114)

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

10.16180/j.cnki.issn1007-7820.2016.11.002

TN79+

A