新型BCD加法器及其可逆邏輯實(shí)現(xiàn)

周日貴，張滿群，吳 茜，施 洋

（華東交通大學(xué)信息工程學(xué)院，江西南昌 330013）

新型BCD加法器及其可逆邏輯實(shí)現(xiàn)

周日貴，張滿群，吳 茜，施 洋

（華東交通大學(xué)信息工程學(xué)院，江西南昌 330013）

可逆邏輯是最近幾年迅速發(fā)展起來的新興研究領(lǐng)域，由于它在傳遞信息時(shí)能減少能量損耗而引起各方面越來越多的關(guān)注。該文設(shè)計(jì)了一種新型的4×4可逆邏輯門——NC門，該門能夠獨(dú)立實(shí)現(xiàn)可逆BCD溢出檢測邏輯電路。同時(shí)，借助作者曾經(jīng)設(shè)計(jì)的4×4可逆加法電路——ZS門，設(shè)計(jì)出一種新型可逆BCD加法電路。設(shè)計(jì)的電路與以往的相比，無論是在門的數(shù)量上還是在垃圾輸出的數(shù)量上都達(dá)到最優(yōu)的效果。

可逆邏輯；ZS門；NC門；可逆BCD加法電路；垃圾輸出

在過去的幾十年中，人們一直關(guān)注計(jì)算機(jī)能量損耗問題。20世紀(jì)60年代，科學(xué)家Landauer［1］指出在高科技技術(shù)與系統(tǒng)中，當(dāng)電路采用的是不可逆操作時(shí)，都會有能量損耗問題，并且每傳遞1 bit信息會損耗ln2kT的熱量，k=1.38 ×10-23J·K-1，T是相對應(yīng)的溫度。能耗問題會導(dǎo)致計(jì)算機(jī)中的芯片發(fā)熱，極大地影響了芯片的集成度，從而限制計(jì)算機(jī)的運(yùn)行速度。1973年科學(xué)家Bennett［2］發(fā)現(xiàn)能耗問題來源于計(jì)算過程中的不可逆操作，當(dāng)計(jì)算過程采用可逆操作時(shí)，就不會有能量損耗問題。因此，可逆邏輯在最近十幾年中引起各方面越來越多的關(guān)注，并且已經(jīng)運(yùn)用在多種領(lǐng)域，如光學(xué)計(jì)算機(jī)、納米技術(shù)、量子計(jì)算機(jī)等。可逆邏輯運(yùn)用最突出的領(lǐng)域在于量子計(jì)算機(jī)。

量子計(jì)算機(jī)是以量子力學(xué)原理直接進(jìn)行計(jì)算的計(jì)算機(jī)。量子計(jì)算機(jī)以量子物理的過程來運(yùn)行，利用量子態(tài)的疊加、量子態(tài)的糾錯及干涉等性質(zhì)進(jìn)行信息處理。量子計(jì)算機(jī)與經(jīng)典計(jì)算機(jī)不同之處在于，對于經(jīng)典圖靈計(jì)算機(jī)來說，信息或者數(shù)據(jù)由二進(jìn)制數(shù)據(jù)位存儲，每一個二進(jìn)制數(shù)據(jù)位由0或1表示，每個數(shù)據(jù)位要么是0，要么是1，兩者必取其一。而量子計(jì)算機(jī)雖然也由存儲器和邏輯門網(wǎng)絡(luò)組成，但是量子計(jì)算機(jī)用自旋或者二能級態(tài)構(gòu)造出量子計(jì)算機(jī)的數(shù)據(jù)位，稱之為量子位（qubit）［3］。量子位采用二能級量子系統(tǒng)，二能態(tài)分別代表0和1。一個qubit就是一個二維希爾伯特空間（Hilbert），它的狀態(tài)可以落在|0＞和|1＞之外，即疊加態(tài)，可表示為|Ψ＞ =α|0＞ +β|1＞ ，且|α|2+|β|2=1。得到0的概率為|α|2，得到1的概率為|β|2，其中α，β為復(fù)數(shù)，代表可連續(xù)取值幾率幅。α，β不同，則量子位儲存的信息不同，所以一個量子比特位所能表示的信息量遠(yuǎn)多于一個經(jīng)典比特位。n個經(jīng)典比特位只能儲存n個一位二進(jìn)制數(shù)或者一個n位二進(jìn)制數(shù)，而n個量子位卻可以同時(shí)儲存2n個n量子比特二進(jìn)制數(shù)，儲存能力提高了2n倍。

在量子信息理論中，量子線路是由若干可逆邏輯門級聯(lián)構(gòu)成，它是對量子信息作一系列幺正變換以實(shí)現(xiàn)電路功能。n量子比特門可以用相應(yīng)的2n×2n的矩陣來表示，就像單量子比特的量子門可以由2×2矩陣給出。這些量子比特門的相應(yīng)矩陣U要滿足的條件是酉性，即U+U=I。其中U+是U的共軛轉(zhuǎn)置矩陣。一些經(jīng)典線路特有的概念在量子線路中通常不出現(xiàn)。首先，量子線路不允許出現(xiàn)回路，即從線路的一部分到另一部分的反饋，也就是說量子線路是無環(huán)的。其次，經(jīng)典線路允許連線匯合，即所謂扇入操作，導(dǎo)致單連線包括所有輸入位的按位或，顯然這個操作是不可逆的，因而也是非酉的，因此在量子線路中我們不允許出現(xiàn)扇入。最后，相反的操作，扇出，即產(chǎn)生一比特的對個拷貝在量子線路中也是不允許的［4-5］。

BCD碼是最基本、最簡單的一種編碼方案，應(yīng)用十分廣泛。這種編碼方案是將每個十進(jìn)制數(shù)字用四位二進(jìn)制數(shù)表示，按自然二進(jìn)制的規(guī)律排列且指定前面10種代碼依次表示0～9這10個數(shù)字［6］。文章設(shè)計(jì)了新的4×4可逆門——NC門，該門不但能夠獨(dú)立地完成BCD加法電路的溢出檢測電路，而且將門數(shù)量和垃圾輸出數(shù)量減到最優(yōu)。并在此基礎(chǔ)上，利用可逆ZS門［7］設(shè)計(jì)出可逆BCD加法電路。設(shè)計(jì)出的BCD加法電路無論在門的數(shù)量上還是在垃圾輸出的數(shù)量上都是最優(yōu)的。

1 基本可逆邏輯門的介紹

現(xiàn)在已經(jīng)存在很多量子可逆邏輯門，如Feynman門［8］，New Toffoli門［9］，ZS門。

1.1 Feynman門

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

1.2 New Toffoli門

New Toffoli門，又叫Peres門（PG）。該門有3個輸入比特和3個輸出比特，如圖2所示。當(dāng)設(shè)置C=0時(shí)，可實(shí)現(xiàn)一個半加法器的功能。

1.3 可逆ZS門

ZS門有4個輸入量子比特和4個輸出量子比特，如圖3所示。當(dāng)將ZS門的第四輸入置0，便可以得到量子全加法器［7］。

圖1 Feynman門Fig.1 Feynman gate

圖2 Peres門Fig.2 Peres gate

2 新型可逆BCD加法電路

圖3 ZS門Fig.3 ZS gate

2.1 新型4×4可逆NC門

NC門（NCG）有4個輸入量子比特和4個輸出量子比特，如圖4所示。該電路是從左向右讀，電路中每一行代表一個量子線路。其真值表如表1所示，從真值表中可看出NC門的給定輸入量子比特A，B，C，D可唯一確定其輸出量子比特P，Q，R，S。如果想恢復(fù)原來的輸入量子比特，只需在其輸出端給出另一個NC門即可。給定輸入可以確定其輸出，同時(shí)給定輸出可以得到其唯一的輸入，從而可以驗(yàn)證該NC門滿足可逆的要求。

2.2 可逆邏輯線路的特點(diǎn)

在設(shè)計(jì)新型可逆BCD加法電路之前，首先得弄清楚可逆邏輯線路的特點(diǎn)。從第一、二節(jié)介紹的可逆門中得出，可逆邏輯線路與經(jīng)典線路有所不同，它具有如下特點(diǎn)［5］：

1輸入線數(shù)與輸出線數(shù)要相等；2沒有扇出與扇入；3沒有循環(huán)和反饋；4電路分層級聯(lián)，有時(shí)為保證電路可逆性需要人為添加一些垃圾輸出位，即沒有用的數(shù)據(jù)位。

圖4 NC門Fig.4 NC gate

當(dāng)我們在設(shè)計(jì)可逆BCD加法電路時(shí)，為了將線路達(dá)到最優(yōu)效果，設(shè)計(jì)時(shí)應(yīng)考慮：

1運(yùn)用最少的垃圾輸出數(shù)量；2運(yùn)用最少的輸入常數(shù)；3保持最少的級聯(lián)長度；4運(yùn)用最少的門數(shù)量；5量子代價(jià)達(dá)到最優(yōu)效果；6運(yùn)用最少的邏輯線路的單位延遲。

2.3 經(jīng)典BCD加法電路

BCD加法電路是兩個一位BCD碼相加，如果它們的相加之和小于或等于9，即二進(jìn)制為1001時(shí)，則輸出正確結(jié)果。如果相加之和大于或等于10，即二進(jìn)制為1010時(shí)，則需要加6（0110）修正，并向高位進(jìn)位。進(jìn)位可以在首次相加或修正時(shí)產(chǎn)生。為此，需要一個校正電路，校正（修正）電路應(yīng)是個判9電路，當(dāng)和小于或等于9時(shí)加0000；當(dāng)和大于9時(shí)加0110，這樣就實(shí)現(xiàn)了校正。舉例說明：例5+6=11，利用8421碼相加時(shí)，應(yīng)寫為0101+0110=1011，正確結(jié)果為11，即00010001。但1011不是正確結(jié)果，并且大于9（1001），應(yīng)加6（0110）進(jìn)行修正。1011+0110=10001，結(jié)果正確。用S3S2S1S0來表示相加的和，C3表示相加結(jié)果產(chǎn)生的進(jìn)位，可以得到它的校正函數(shù)為Cout=C3+S3(S2+S1)。因?yàn)锽CD碼的取值范圍為0～9，相加的最大和為18，故C3與S3( )

S2+S1不能同時(shí)取到1，所以我們可以用“⊕”（異或）來取代“+”，故表達(dá)式可寫成Cout=C3⊕S3(S2+S1)［6］。經(jīng)典BCD加法電路如圖5所示。

表1 NC門真值表Tab.1 True table of NC gate

圖5 經(jīng)典BCD加法電路Fig.5 Classical BCD adder circuit

2.4 新型可逆BCD加法電路的設(shè)計(jì)與實(shí)現(xiàn)

從前面介紹的原理中可得出，可逆BCD加法電路分三個部分：1可逆串行進(jìn)位四位二進(jìn)制加法器；2可逆BCD加法器溢出檢測邏輯電路；3可逆BCD加法器溢出校正邏輯電路。

2.4.1 可逆串行進(jìn)位四位二進(jìn)制加法器

利用所設(shè)計(jì)的一位量子全加法器串接，就可以實(shí)現(xiàn)位數(shù)大于1位的兩個量子比特?cái)?shù)相加的邏輯功能電路。因?yàn)榻o一個ZS門其相應(yīng)的輸入可設(shè)計(jì)出一位量子全加法器，并且只產(chǎn)生兩個垃圾輸出。因此為了得到4位串行進(jìn)位四位二進(jìn)制加法器的電路，該文將4個ZS門串行相接。其特點(diǎn)是被加數(shù)和加數(shù)的各位能同時(shí)進(jìn)行輸入到各全加器的加數(shù)輸入端，而各位全加器的進(jìn)位輸入則是按照由低位向高位逐級串行傳送的，各進(jìn)位形成一個進(jìn)位鏈。如圖6所示，A3，A2，A1，A0是一個二進(jìn)制加數(shù)；B3，B2，B1，B0是另一個二進(jìn)制加數(shù)；C-1為低位的進(jìn)位輸入；C3為高位的進(jìn)位輸出；S3，S2，S1，S0為相加的和數(shù)，G1到G8為產(chǎn)生的垃圾輸出。

2.4.2 可逆BCD加法器溢出檢測邏輯電路

從上述介紹的原理看出，當(dāng)S3S2S1S0≥1001時(shí)，就需要將和加上0110，得出它的校正函數(shù)為Cout=C3⊕S3(S2+S1)。將校正函數(shù)等換成：

圖6 新型BCD加法電路Fig.6 New BCD adder circuit

2.4.3 可逆BCD加法器溢出校正邏輯電路

可逆BCD加法器溢出校正邏輯電路就是上面所述的校正（修正）電路，當(dāng)檢測結(jié)果判斷Cout=0時(shí)，S3S2S1S0+0000；當(dāng)檢測結(jié)果判斷Cout=1時(shí)，S3S2S1S0+0110。如圖6所示，這里使用兩個PG門做一個量子半加法器；ZS做一個量子全加法器；三個門通過級聯(lián)的形式，完成了可逆BCD加法器溢出校正邏輯電路。將上述這三部分級聯(lián)在一起就構(gòu)成了可逆BCD加法電路，如圖6所示。該圖中層與層之間是相互級聯(lián)的關(guān)系，每一層的輸出都將作為下一層的輸入，并充分考慮不同層次的線路的“級聯(lián)”以減少線路的無用輸出數(shù)量，從而達(dá)到該可逆BCD加法電路結(jié)構(gòu)最優(yōu)化。

3 新型可逆BCD加法電路的性能分析

在可逆BCD加法器溢出檢測邏輯電路中，該文設(shè)計(jì)出新型的可逆門即NC門來完成可逆BCD加法器溢出檢測邏輯電路，比現(xiàn)有的文獻(xiàn)［10-13］中的可逆BCD加法器溢出檢測邏輯電路，無論在門的數(shù)量上還是在垃圾輸出數(shù)量上都達(dá)到最優(yōu)的效果，具體如表2所示。

文獻(xiàn)［11］運(yùn)用了3個Toffoli門，文獻(xiàn)［12］運(yùn)用了3個New門，文獻(xiàn)［13］運(yùn)用了2個New門和1個Toffoli門，它們都產(chǎn)生了6個垃圾輸出，3個單位延遲。文獻(xiàn)［14］運(yùn)用了2個Fredkin門和1個Toffoli門，產(chǎn)生了1個垃圾輸出和3個單位延遲。

表2 可逆BCD加法器溢出檢測邏輯電路的性能分析Tab.2 Parameters analysis of BCD overflow detection logic

這里，垃圾輸出數(shù)量是指無用的輸出數(shù)量。因?yàn)樵诳赡孢壿嬮T其輸入輸出數(shù)量必須相等，同時(shí)其輸入矩陣和輸出矩陣必須呈現(xiàn)出一一對應(yīng)的關(guān)系。也就是說，輸入矩陣可以被輸出矩陣唯一重構(gòu)，而輸出矩陣也可以被輸入矩陣唯一表示。為了滿足這種一一對應(yīng)的關(guān)系，保證輸入輸出之間數(shù)量上的相等，不可避免的會產(chǎn)生出一些不需要的輸出數(shù)量。在設(shè)計(jì)時(shí)將垃圾輸出數(shù)量減到最少，電路的效果就越好。單位延遲是指從每個門作為單位時(shí)間來計(jì)算，信息從輸入端開始傳遞到輸出端開始接收之間的時(shí)間間隔。延遲越小，數(shù)據(jù)的傳輸率越高，性能就越好。

從圖6中得出，本文設(shè)計(jì)的可逆BCD加法電路運(yùn)用了4+1+3=8個可逆門、產(chǎn)生了8+0+3=11個垃圾輸出、4+1+3=8個單位延遲；而現(xiàn)有的文獻(xiàn)中，文獻(xiàn)［10］中用了23個可逆門、產(chǎn)生22個垃圾輸出、21個單位延遲；文獻(xiàn)［11］中用了11個可逆門、產(chǎn)生22個垃圾輸出、11個單位延遲；文獻(xiàn)［12］中用了14個可逆門、22個垃圾輸出、13個單位延遲；文獻(xiàn)［13］中用了10個可逆門、產(chǎn)生11個垃圾輸出、10個單位延遲。經(jīng)過比較之后，發(fā)現(xiàn)文中設(shè)計(jì)的可逆BCD加法電路是無論在門的數(shù)量上，還是在垃圾輸出，邏輯延時(shí)上都達(dá)到最優(yōu)。具體比較于表3所示。

表3 新型BCD加法電路的性能分析Tab.3 Parameters analysis of novel BCD adder circuit

4 結(jié)論

主要介紹了在經(jīng)典BCD加法電路的基礎(chǔ)上用可逆門設(shè)計(jì)出可逆BCD加法電路。提出了新型4×4可逆邏輯門——NC門，該門不但能夠獨(dú)立實(shí)現(xiàn)可逆BCD溢出檢測邏輯電路，還能減少電路中門數(shù)量和垃圾輸出數(shù)量，將電路達(dá)到最優(yōu)的效果。在此基礎(chǔ)上，利用現(xiàn)有的可逆門——ZS門設(shè)計(jì)出可逆BCD加法電路，同時(shí)分析了該電路的門數(shù)量、垃圾輸出數(shù)量、單位延遲，分析得出本文設(shè)計(jì)的可逆BCD加法電路不僅在門數(shù)量、垃圾輸出數(shù)量還是在單位延遲上比現(xiàn)有的效果都要好。

可逆邏輯已經(jīng)運(yùn)用在光學(xué)計(jì)算機(jī)、納米技術(shù)、量子計(jì)算機(jī)等多種領(lǐng)域。而本文可逆BCD加法電路正是在可逆計(jì)算領(lǐng)域的一些嘗試，這些嘗試對于設(shè)計(jì)更加復(fù)雜的量子系統(tǒng)，如量子CPU的運(yùn)算部件和邏輯部件來說，或許是一個促進(jìn)作用。

［1］ LANDAUER R.Irreversibility and heat generation in the computational process’s［J］.IBM Journal Research and Development，1961（5）：183-191.

［2］ BENNETT C H.Logical reversibility of computation［J］.IBM J Research and Development，1973（17）：525-532.

［3］ NIELSEN M A，CHUANG I L.Quantum computation and quantum information［M］.Cambridge：Cambridge University Press，2000.

［4］AGARWALA，JHA N K.Synthesis of reversible logic［C］//Design，Automation and Test in Europe Conference and Exhibition，Washington：Proceedings of IEEE，2004：1384-1385.

［5］VOS AD，RENTERGEM YV.Reversible computing：from mathematical group theory to electronical circuit experiment［C］//Proceedings of the 2nd Conference on Computing Frontiers，New York：Association for Comuting Machinery，2005：35-45.

［6］劉傳隆.BCD碼的十進(jìn)制加法電路［J］.電子技術(shù)，2009（10）：87.

［7］ZHOU RIGUI，SHI YANG，WANG HUIAN，et al.Transistor realization of reversible“ZS”series gates and reversible array multiplier［J］.Microelectronics J，2011，42（2）：305-315

［8］ FEYNMAN R.Quantum mechanical computers［J］.Opt News，1985（11）：11-20.

［9］ PERESA.Reversible logic and quantum computers［J］.Phys Rev，1985，32（6）：3266-3276.

［10］BABU H M H，CHOWDHURY A R.Design of a compact reversible binary coded decimal adder circuit［J］.Elsevier J Syst Archit，2006，52（5）：272-282.

［11］THAPLIYAL H，SRINIVAS M B.Novel reversible TSG gate and its application for designing reversible carry look ahead adder and other adder architectures［J］.Computer SystemsArchitecture，2005，3740：805-817.

［12］ HAGHPARAST M，NAVI K.A novel reversible BCD adder for nanotechnology based systems［J］.Am J Applied Sci，2008,5（3）：282-288.

［13］ASHIS KUMER BISWAS，MAHMUDUL MD HASAN，AHSAN RAJA CHOWDHURY，et al.Ef fi cient approaches for designing reversible binary coded decimal adders［J］.Microelectronics Journal，2008（39）：1693-1703.

New BCDAdders and Their Reversible Logic Implementation

Zhou Rigui，Zhang Manqun，Wu Qian，Shi Yang
（School of Information Engineering，East China Jiaotong University，Nanchang 330013，China）

Reversible logic is a new research area that has developed rapidly in recent years.It has

great attention in all aspects due to their ability to reduce the power dissipation.This paper proposes a new reversible logic gate—NC gate.This gate can independently complete Binary Coded Decimal（BCD）adder overflow detection logic.Meanwhile，with 4×4 reversible adder circuits—ZS gate which was designed by the author，a new reversible BCD adder is designed in this paper.The proposed reversible BCD adder is optimized in terms of number of reversible gates and garbage outputs compared to the previous counterparts.

reversible logic；ZS gate；NC gate；reversible BCD adders；garbage output

TP331.1

A

1005-0523（2011）04-0001-06

2011-05-03

國家自然科學(xué)基金項(xiàng)目（61065002）；江西省自然科學(xué)基金項(xiàng)目（2009GZS0013）；江西省教育廳科研基金項(xiàng)目（GJJ11433）

周日貴（1973－），男，教授，博士，研究方向?yàn)榱孔佑?jì)算與量子神經(jīng)網(wǎng)絡(luò)。