周影輝，王友仁

（南京航空航天大學(xué) 自動(dòng)化學(xué)院，江蘇 南京 210016）

隨著集成電路規(guī)模的增加，其能耗問(wèn)題已經(jīng)愈發(fā)引起研究者的注意。Bennett[1]最早證明能耗來(lái)源于計(jì)算過(guò)程中的不可逆操作，傳統(tǒng)數(shù)字電路由于不可逆計(jì)算導(dǎo)致信息的擦除導(dǎo)致能量的消耗，Landauer[2]指出，每一個(gè)信息位的丟失對(duì)應(yīng)KT*Ln2 焦耳的熱量產(chǎn)生，式中K 是波爾茲曼常量，T 是絕對(duì)溫度。雖然單個(gè)信息位散失能量很少，但對(duì)于超大規(guī)模集成電路，功耗不能忽略。如果組成電路的所有門均能夠執(zhí)行可逆計(jì)算，即不存在信息位的擦除，理論上可以實(shí)現(xiàn)集成電路的零損耗。目前廣泛研究的量子運(yùn)算是一種具體的可逆計(jì)算，即能夠從根本上解決集成電路功耗問(wèn)題。

量子計(jì)算可以由可逆邏輯電路實(shí)現(xiàn)，現(xiàn)有的研究對(duì)可逆邏輯電路研究很多，但大都集中在可逆組合邏輯電路方面[3-5]，時(shí)序邏輯電路方面研究的比較少[6-8]，文獻(xiàn)[6]首次提出了可逆觸發(fā)器的設(shè)計(jì)方法，但沒(méi)有考慮電路的性能指標(biāo)。文獻(xiàn)[7]提出了可逆主從觸發(fā)器的設(shè)計(jì)方法。文獻(xiàn)[8]設(shè)計(jì)了對(duì)數(shù)式移位寄存器設(shè)計(jì)方法，但是僅能適用于此類寄存器?，F(xiàn)在沒(méi)有通用的設(shè)計(jì)方法可以適用不同種類的可逆時(shí)序邏輯電路設(shè)計(jì)。

針對(duì)可逆邏輯電路現(xiàn)有的問(wèn)題，提出了一種方法，將傳統(tǒng)的不可逆時(shí)序邏輯電路轉(zhuǎn)化為可逆時(shí)序邏輯電路。并且以典型的可逆時(shí)序邏輯電路中的脈沖分配器的設(shè)計(jì)方為例，設(shè)計(jì)了可逆脈沖分配器，通過(guò)將不可逆脈沖分配器中的基本邏輯門替換成可逆邏輯門，達(dá)到將不可逆時(shí)序電路轉(zhuǎn)換為可逆時(shí)序電路的目的。

1 可逆邏輯電路的基本概念

量子計(jì)算機(jī)中，信息的基本單元是量子比特，即量子位，信息的基本操作元件是可逆邏輯門。量子比特是信息的載體，量子比特的信息經(jīng)可逆邏輯門操作處理后，最后得到計(jì)算結(jié)果。

定義1 組成可逆邏輯電路的基本單元必須是可逆邏輯門，并且還需要滿足以下約束條件：1）電路中無(wú)扇入扇出操作，2）輸入與輸出位數(shù)相等，3）對(duì)應(yīng)電路真值表滿足一一映射。

定義2 任何一個(gè)較復(fù)雜的可逆邏輯門均是由或基本可逆邏輯門構(gòu)成。量子代價(jià)用來(lái)衡量一個(gè)量可逆邏輯電路的復(fù)雜性，用實(shí)現(xiàn)一個(gè)可逆邏輯電路所需要的或者 基本可逆邏輯門的數(shù)量表示，不管內(nèi)部結(jié)構(gòu)如何，一個(gè)基本可逆邏輯門的量子損耗是1。

定義3 在可逆邏輯電路中，除期望輸出外的剩余輸出稱為垃圾位。垃圾位是無(wú)用輸出位，也是電路能耗產(chǎn)生的根源。因此垃圾位數(shù)量的多少是評(píng)價(jià)可逆邏輯電路的一個(gè)最重要的性能指標(biāo)。當(dāng)添加垃圾位輸出后，為使量子可逆邏輯電路的輸入輸出位數(shù)相等，需在輸入端添加一定數(shù)量的常量輸入，常量輸入的位數(shù)也影響到可逆邏輯電路綜合的量子代價(jià)，常量輸入取0 或1。

常用可逆邏輯門如圖1 所示。

圖1 常用可逆邏輯門Fig.1 Common reversible logic gates

Feynman 門（FG 門）有兩個(gè)輸入量子比特，分別是控制量子比特和目標(biāo)量子比特。它所實(shí)現(xiàn)的功能為當(dāng)控制量子比特為0 時(shí)，目標(biāo)量子比特不變；而當(dāng)控制量子比特為1 時(shí)，目標(biāo)量子比特將反轉(zhuǎn)。FG 門的線路如圖1（a）所示。其中，P、Q為FG 門的兩個(gè)輸出量子比特，F(xiàn)G 門能夠?qū)崿F(xiàn)線路的復(fù)制功能。當(dāng)B=0 時(shí)，可得到兩個(gè)相同的輸出A。因此，F(xiàn)G 門能夠?qū)崿F(xiàn)可逆邏輯量子比特的復(fù)制。

F2G 門又叫做Feynman Double gate）F2G），有3個(gè)輸入比特，能完成輸入比特的兩位復(fù)制。

FRG 門，又稱受控交換門，是一種三輸入輸出的可逆邏輯門，如圖所示。當(dāng)控制端為0 時(shí)，F(xiàn)RG為三輸入輸出的直通門，即P=A、Q=B、R=C。當(dāng)控制端A 輸入信號(hào)為1 時(shí)，P=A，Q=C，R=B。

TG 門是最常用的多比特可逆邏輯門，輸入位由兩個(gè)控制比特位和一個(gè)被控比特來(lái)構(gòu)建符合特定要求的可逆邏輯電路。此外，門可以通過(guò)修改控制位數(shù)量，構(gòu)成具有不同數(shù)量控制位TG 門系列，以此來(lái)構(gòu)建符合特定要求的可逆邏輯電路。

2 可逆脈沖分配器的設(shè)計(jì)

在傳統(tǒng)的不可逆時(shí)序電路中，使用的邏輯門是不可逆的。要設(shè)計(jì)可逆邏輯電路，就要使用可逆邏輯門進(jìn)行構(gòu)造。本文將傳統(tǒng)的不可逆時(shí)序電路中的邏輯門替換成可逆邏輯門，不改變?cè)须娐返脑O(shè)計(jì)原理，從而將不可逆邏輯電路轉(zhuǎn)化為可逆邏輯電路。

傳統(tǒng)的可逆脈沖分配器主要是由計(jì)數(shù)器和相應(yīng)的譯碼器組成，基于扭環(huán)計(jì)數(shù)器的脈沖分配器如圖2 所示。其中計(jì)數(shù)器又由觸發(fā)器級(jí)聯(lián)而成，所以要將其中的觸發(fā)器和基本的與門轉(zhuǎn)換成相應(yīng)的可逆邏輯門，另外，由于可逆邏輯電路不能有扇入或者扇出，所以圖2 中的扇入扇出信號(hào)要用可逆邏輯門對(duì)信號(hào)進(jìn)行復(fù)制。

首先要將傳統(tǒng)的D 觸發(fā)器轉(zhuǎn)化可逆D 觸發(fā)器?？紤]到量子代價(jià)和量子門數(shù)的影響，設(shè)計(jì)了由圖1 中的FRG 門、F2G門構(gòu)成的可逆D 觸發(fā)器，具體結(jié)構(gòu)如圖3 所示。

由圖3（a）所示，當(dāng)C 輸入為0 時(shí)，輸出Q 保持不變，當(dāng)C輸入為1 時(shí)，輸出Q 和D 的信號(hào)相同。將圖3（a）中的電路封裝成圖3（b）所示的模塊。本文設(shè)計(jì)的可逆D 觸發(fā)器（圖3）的性能指標(biāo)和文獻(xiàn)[7]中設(shè)計(jì)的可逆D 觸發(fā)器比較如表1 所示。

圖2 基于扭環(huán)計(jì)數(shù)器的脈沖發(fā)生器Fig.2 Pulse distributor based on twisted ring counter

圖3 可逆D 觸發(fā)器Fig.3 Reversible D flip-flop

表1 D觸發(fā)器性能指標(biāo)比較Tab.1 The performance comparison of reversible D flip-flop designed by ours and others methods

由表1 可以看出本文設(shè)計(jì)的量子可逆D 觸發(fā)器比文獻(xiàn)[8]所用的量子門數(shù)減少了5個(gè)，量子代價(jià)減少了40，垃圾位減少了6個(gè)。在設(shè)計(jì)多位脈沖分配器時(shí)，量子門數(shù)、量子代價(jià)和垃圾位會(huì)有明顯降低。

圖2 所示的計(jì)數(shù)器是扭環(huán)計(jì)數(shù)器，根據(jù)設(shè)計(jì)原則，將計(jì)數(shù)器中的觸發(fā)器替換成可逆D 觸發(fā)器，從而設(shè)計(jì)出可逆扭環(huán)計(jì)數(shù)器。如圖4 所示。

圖4 可逆扭環(huán)計(jì)數(shù)器Fig.4 Reversible twisted ring counter

可逆扭環(huán)計(jì)數(shù)器和譯碼器共同組成脈沖分配器，譯碼器主要由與門構(gòu)成，而可逆邏輯電路中沒(méi)有相應(yīng)的與門，必須用常用可逆邏輯門構(gòu)造，Toffoli 門可以完成此功能，兩輸入的與門要三輸入的Toffoli 門構(gòu)成。另外，不可逆脈沖分配器的扇入扇出需要進(jìn)行重新設(shè)計(jì)，每個(gè)扇入或者扇出的節(jié)點(diǎn)要用Feynman 門對(duì)信號(hào)進(jìn)行復(fù)制。

結(jié)合圖2 所示的可逆扭環(huán)計(jì)數(shù)器和圖4 所示的可逆扭環(huán)計(jì)數(shù)器，構(gòu)建的量子可逆脈沖分配器如圖5 所示。

圖5 可逆脈沖分配器Fig.5 Reversible pulse distributor

3 仿真結(jié)果分析和物理實(shí)現(xiàn)

由圖5 可以看出，本文所設(shè)計(jì)的量子可逆脈沖分配器所用量子門數(shù)為32，量子代價(jià)為96，垃圾位24。

可逆脈沖分配器的結(jié)構(gòu)在實(shí)驗(yàn)中用VHDL 進(jìn)行描述封裝，代碼通過(guò)Xilinx ISE9.1i 下載到Spartan-6 LX FPGA 芯片上進(jìn)行運(yùn)行仿真，目標(biāo)器件為XC6SLX9?？赡婷}沖分配器的仿真結(jié)果如圖6 所示。

圖6 可逆脈沖分配器仿真結(jié)果Fig.6 Simulation of reversible pulse distributor

由圖6 可以看出，本文設(shè)計(jì)的可逆脈沖分配器可以實(shí)現(xiàn)8 節(jié)拍脈沖輸出功能，并且無(wú)冒險(xiǎn)與競(jìng)爭(zhēng)現(xiàn)象。

目前已經(jīng)提出了多種可逆邏輯電路的物理構(gòu)建方法，如利用低功耗CMOS 晶體管構(gòu)建可逆邏輯門，而利用電子波導(dǎo)Y-分支開(kāi)關(guān)）Y-Branch Switch YBS）構(gòu)建可逆邏輯門可以用更少的能量改變開(kāi)關(guān)狀態(tài)，它的打開(kāi)和關(guān)閉是通過(guò)改變電子傳輸兩個(gè)方向中的一個(gè)，而不是切換當(dāng)前的開(kāi)關(guān)，在正常情況下，YBS 的一次開(kāi)關(guān)動(dòng)作大約散失0.6meV 的熱量，一個(gè)信息位丟失所損耗的能量為KT*Ln2，大約等價(jià)為18meV，利用YBS 作為基本單元構(gòu)建可逆邏輯門會(huì)更加節(jié)能[9]。如圖7 所示，為利用YBS 作為基本單元構(gòu)建的FG 門和Toffoli 門，由于所有的可逆邏輯電路都能有Toffoli 門實(shí)現(xiàn)，所以可逆脈沖分配器可以由圖7 所示的可逆邏輯門設(shè)計(jì)物理電路。

4 結(jié)論

文中提出了一種可逆時(shí)序電路的設(shè)計(jì)方法，以不可逆脈沖分配器為例，將其轉(zhuǎn)化為可逆脈沖分配器，分析了所設(shè)計(jì)的可逆脈沖發(fā)生器的有關(guān)性能指標(biāo)并對(duì)其功能進(jìn)行了仿真。另外提出了可逆脈沖分配器的物理實(shí)現(xiàn)方法[10]。結(jié)果表明，設(shè)計(jì)的可逆脈沖分配器能完成脈沖輸出的功能。此方法還可以用于其它可逆時(shí)序邏輯電路的設(shè)計(jì)。

圖7 基于YBS 的可逆邏輯門實(shí)現(xiàn)Fig.7 The implementation of reversible logic gate based on YBS

[1]Laudauer R.Irreversibility and heat generation of the computing process[J].IBM Journal of Research and Development，1961，5（3）：183-219.

[2]Bennett C H.Notes on Landauer’s principle，reversible computation and Maxwell’s demon[J].Studies In History and Philosophy of Science Part B：Studies In History and Philosophy of Modern Physics，2003，34（3）：501-510.

[3]管致錦，秦小麟，陶濤，等.可逆門網(wǎng)絡(luò)的表示與級(jí)聯(lián)[J].電子學(xué)報(bào)，2010，38（10）：2370-2376.GUAN Zhi-jin，QIN Xiao-lin，TAO Tao，et al.Representation and cascade for reversible gate network[J].Acta Electronica Sinica，2010，38（10）：2370-2376.

[4]呂洪君，樂(lè)亮，韓良順，等.基于遺傳算法的量子可逆邏輯電路綜合方法研究[J].量子電子學(xué)報(bào)，2011，28（5）：596-604.LV Hong-jun，YUE Liang，HAN Liang-shun，et al.Quantum reversible logic circuits synthesis based on genetic algorithm[J].Chinese Journal of Quantum Electronics，2011，28（5）：596-604.

[5]Soeken M，Wille R，Hilken C，et al.Synthesis of reversible circuits with minimal lines for large functions [C].17th Asia and South Pacific Design Automation Conference，Sydney，Australia，2012：85-92.

[6]Rice J E.A new look at reversible memory elements[C]//IEEE International Symposium on Circuits and Systems，Island of Kos，Greece，2006：1243-1246

[7]Thapliyal H，Srinivas M B.A beginning in the reversible logic synthesis of sequential circuits[C]//Proc.of Military and Aerospace Programmable Logic Devices International Conference，Washington D.C.，2005，summision，1012.

[8]Rajmohan V，Ranganathan V.Design of counters using reversible logic [C]//2011 3rd International Conference on Electronics Computer Technology（ICECT），Kanyakumari，India，2011：138-142.

[9]CHUANG Min-lun，WANG Chun-yao.Synthesis of reversible sequential elements[J].ACM Journal on Emerging Technologies in Computing Systems，2008，3（4）：1-19.

[10]張偉，陳鋒，馬軍強(qiáng)，等.軌/姿控發(fā)動(dòng)機(jī)脈沖后效沖量快速算法的研究及應(yīng)用[J].火箭推進(jìn)，2012（1）：51-56.ZHANG Wei，CHEN Feng，MA Jun-qiang，et al.Research and application of fast algorithm for pulse residual impulse of divert and attitude control engine[J].Journal of Rocket Propulsion，2012（1）：51-56.