新型BCD加法器及其可逆逻辑实现

周日贵，张满群，吴 茜，施 洋

（华东交通大学信息工程学院，江西南昌 330013）

新型BCD加法器及其可逆逻辑实现

周日贵，张满群，吴 茜，施 洋

（华东交通大学信息工程学院，江西南昌 330013）

可逆逻辑是最近几年迅速发展起来的新兴研究领域，由于它在传递信息时能减少能量损耗而引起各方面越来越多的关注。该文设计了一种新型的4×4可逆逻辑门——NC门，该门能够独立实现可逆BCD溢出检测逻辑电路。同时，借助作者曾经设计的4×4可逆加法电路——ZS门，设计出一种新型可逆BCD加法电路。设计的电路与以往的相比，无论是在门的数量上还是在垃圾输出的数量上都达到最优的效果。

可逆逻辑；ZS门；NC门；可逆BCD加法电路；垃圾输出

在过去的几十年中，人们一直关注计算机能量损耗问题。20世纪60年代，科学家Landauer［1］指出在高科技技术与系统中，当电路采用的是不可逆操作时，都会有能量损耗问题，并且每传递1 bit信息会损耗ln2kT的热量，k=1.38 ×10-23J·K-1，T是相对应的温度。能耗问题会导致计算机中的芯片发热，极大地影响了芯片的集成度，从而限制计算机的运行速度。1973年科学家Bennett［2］发现能耗问题来源于计算过程中的不可逆操作，当计算过程采用可逆操作时，就不会有能量损耗问题。因此，可逆逻辑在最近十几年中引起各方面越来越多的关注，并且已经运用在多种领域，如光学计算机、纳米技术、量子计算机等。可逆逻辑运用最突出的领域在于量子计算机。

量子计算机是以量子力学原理直接进行计算的计算机。量子计算机以量子物理的过程来运行，利用量子态的叠加、量子态的纠错及干涉等性质进行信息处理。量子计算机与经典计算机不同之处在于，对于经典图灵计算机来说，信息或者数据由二进制数据位存储，每一个二进制数据位由0或1表示，每个数据位要么是0，要么是1，两者必取其一。而量子计算机虽然也由存储器和逻辑门网络组成，但是量子计算机用自旋或者二能级态构造出量子计算机的数据位，称之为量子位（qubit）［3］。量子位采用二能级量子系统，二能态分别代表0和1。一个qubit就是一个二维希尔伯特空间（Hilbert），它的状态可以落在|0＞和|1＞之外，即叠加态，可表示为|Ψ＞ =α|0＞ +β|1＞ ，且|α|2+|β|2=1。得到0的概率为|α|2，得到1的概率为|β|2，其中α，β为复数，代表可连续取值几率幅。α，β不同，则量子位储存的信息不同，所以一个量子比特位所能表示的信息量远多于一个经典比特位。n个经典比特位只能储存n个一位二进制数或者一个n位二进制数，而n个量子位却可以同时储存2n个n量子比特二进制数，储存能力提高了2n倍。

在量子信息理论中，量子线路是由若干可逆逻辑门级联构成，它是对量子信息作一系列幺正变换以实现电路功能。n量子比特门可以用相应的2n×2n的矩阵来表示，就像单量子比特的量子门可以由2×2矩阵给出。这些量子比特门的相应矩阵U要满足的条件是酉性，即U+U=I。其中U+是U的共轭转置矩阵。一些经典线路特有的概念在量子线路中通常不出现。首先，量子线路不允许出现回路，即从线路的一部分到另一部分的反馈，也就是说量子线路是无环的。其次，经典线路允许连线汇合，即所谓扇入操作，导致单连线包括所有输入位的按位或，显然这个操作是不可逆的，因而也是非酉的，因此在量子线路中我们不允许出现扇入。最后，相反的操作，扇出，即产生一比特的对个拷贝在量子线路中也是不允许的［4-5］。

BCD码是最基本、最简单的一种编码方案，应用十分广泛。这种编码方案是将每个十进制数字用四位二进制数表示，按自然二进制的规律排列且指定前面10种代码依次表示0～9这10个数字［6］。文章设计了新的4×4可逆门——NC门，该门不但能够独立地完成BCD加法电路的溢出检测电路，而且将门数量和垃圾输出数量减到最优。并在此基础上，利用可逆ZS门［7］设计出可逆BCD加法电路。设计出的BCD加法电路无论在门的数量上还是在垃圾输出的数量上都是最优的。

1 基本可逆逻辑门的介绍

现在已经存在很多量子可逆逻辑门，如Feynman门［8］，New Toffoli门［9］，ZS门。

1.1 Feynman门

Feynman门（FG）有两个输入量子比特，分别是控制量子比特和目标量子比特。它所实现的功能为当控制量子比特为0时，目标量子比特不变；而当控制量子比特为1时，目标量子比特将反转。FG的线路如图1所示。其中，P，Q为FG的两个输出量子比特，FG能够实现线路的复制功能。当B=0时，可得到两个相同的输出A。因此，FG能够实现可逆逻辑线路的扇出。

1.2 New Toffoli门

New Toffoli门，又叫Peres门（PG）。该门有3个输入比特和3个输出比特，如图2所示。当设置C=0时，可实现一个半加法器的功能。

1.3 可逆ZS门

ZS门有4个输入量子比特和4个输出量子比特，如图3所示。当将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。如果想恢复原来的输入量子比特，只需在其输出端给出另一个NC门即可。给定输入可以确定其输出，同时给定输出可以得到其唯一的输入，从而可以验证该NC门满足可逆的要求。

2.2 可逆逻辑线路的特点

在设计新型可逆BCD加法电路之前，首先得弄清楚可逆逻辑线路的特点。从第一、二节介绍的可逆门中得出，可逆逻辑线路与经典线路有所不同，它具有如下特点［5］：

1输入线数与输出线数要相等；2没有扇出与扇入；3没有循环和反馈；4电路分层级联，有时为保证电路可逆性需要人为添加一些垃圾输出位，即没有用的数据位。

图4 NC门Fig.4 NC gate

当我们在设计可逆BCD加法电路时，为了将线路达到最优效果，设计时应考虑：

1运用最少的垃圾输出数量；2运用最少的输入常数；3保持最少的级联长度；4运用最少的门数量；5量子代价达到最优效果；6运用最少的逻辑线路的单位延迟。

2.3 经典BCD加法电路

BCD加法电路是两个一位BCD码相加，如果它们的相加之和小于或等于9，即二进制为1001时，则输出正确结果。如果相加之和大于或等于10，即二进制为1010时，则需要加6（0110）修正，并向高位进位。进位可以在首次相加或修正时产生。为此，需要一个校正电路，校正（修正）电路应是个判9电路，当和小于或等于9时加0000；当和大于9时加0110，这样就实现了校正。举例说明：例5+6=11，利用8421码相加时，应写为0101+0110=1011，正确结果为11，即00010001。但1011不是正确结果，并且大于9（1001），应加6（0110）进行修正。1011+0110=10001，结果正确。用S3S2S1S0来表示相加的和，C3表示相加结果产生的进位，可以得到它的校正函数为Cout=C3+S3(S2+S1)。因为BCD码的取值范围为0～9，相加的最大和为18，故C3与S3( )

S2+S1不能同时取到1，所以我们可以用“⊕”（异或）来取代“+”，故表达式可写成Cout=C3⊕S3(S2+S1)［6］。经典BCD加法电路如图5所示。

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

图5 经典BCD加法电路Fig.5 Classical BCD adder circuit

2.4 新型可逆BCD加法电路的设计与实现

从前面介绍的原理中可得出，可逆BCD加法电路分三个部分：1可逆串行进位四位二进制加法器；2可逆BCD加法器溢出检测逻辑电路；3可逆BCD加法器溢出校正逻辑电路。

2.4.1 可逆串行进位四位二进制加法器

利用所设计的一位量子全加法器串接，就可以实现位数大于1位的两个量子比特数相加的逻辑功能电路。因为给一个ZS门其相应的输入可设计出一位量子全加法器，并且只产生两个垃圾输出。因此为了得到4位串行进位四位二进制加法器的电路，该文将4个ZS门串行相接。其特点是被加数和加数的各位能同时进行输入到各全加器的加数输入端，而各位全加器的进位输入则是按照由低位向高位逐级串行传送的，各进位形成一个进位链。如图6所示，A3，A2，A1，A0是一个二进制加数；B3，B2，B1，B0是另一个二进制加数；C-1为低位的进位输入；C3为高位的进位输出；S3，S2，S1，S0为相加的和数，G1到G8为产生的垃圾输出。

2.4.2 可逆BCD加法器溢出检测逻辑电路

从上述介绍的原理看出，当S3S2S1S0≥1001时，就需要将和加上0110，得出它的校正函数为Cout=C3⊕S3(S2+S1)。将校正函数等换成：

图6 新型BCD加法电路Fig.6 New BCD adder circuit

2.4.3 可逆BCD加法器溢出校正逻辑电路

可逆BCD加法器溢出校正逻辑电路就是上面所述的校正（修正）电路，当检测结果判断Cout=0时，S3S2S1S0+0000；当检测结果判断Cout=1时，S3S2S1S0+0110。如图6所示，这里使用两个PG门做一个量子半加法器；ZS做一个量子全加法器；三个门通过级联的形式，完成了可逆BCD加法器溢出校正逻辑电路。将上述这三部分级联在一起就构成了可逆BCD加法电路，如图6所示。该图中层与层之间是相互级联的关系，每一层的输出都将作为下一层的输入，并充分考虑不同层次的线路的“级联”以减少线路的无用输出数量，从而达到该可逆BCD加法电路结构最优化。

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

在可逆BCD加法器溢出检测逻辑电路中，该文设计出新型的可逆门即NC门来完成可逆BCD加法器溢出检测逻辑电路，比现有的文献［10-13］中的可逆BCD加法器溢出检测逻辑电路，无论在门的数量上还是在垃圾输出数量上都达到最优的效果，具体如表2所示。

文献［11］运用了3个Toffoli门，文献［12］运用了3个New门，文献［13］运用了2个New门和1个Toffoli门，它们都产生了6个垃圾输出，3个单位延迟。文献［14］运用了2个Fredkin门和1个Toffoli门，产生了1个垃圾输出和3个单位延迟。

表2 可逆BCD加法器溢出检测逻辑电路的性能分析Tab.2 Parameters analysis of BCD overflow detection logic

这里，垃圾输出数量是指无用的输出数量。因为在可逆逻辑门其输入输出数量必须相等，同时其输入矩阵和输出矩阵必须呈现出一一对应的关系。也就是说，输入矩阵可以被输出矩阵唯一重构，而输出矩阵也可以被输入矩阵唯一表示。为了满足这种一一对应的关系，保证输入输出之间数量上的相等，不可避免的会产生出一些不需要的输出数量。在设计时将垃圾输出数量减到最少，电路的效果就越好。单位延迟是指从每个门作为单位时间来计算，信息从输入端开始传递到输出端开始接收之间的时间间隔。延迟越小，数据的传输率越高，性能就越好。

从图6中得出，本文设计的可逆BCD加法电路运用了4+1+3=8个可逆门、产生了8+0+3=11个垃圾输出、4+1+3=8个单位延迟；而现有的文献中，文献［10］中用了23个可逆门、产生22个垃圾输出、21个单位延迟；文献［11］中用了11个可逆门、产生22个垃圾输出、11个单位延迟；文献［12］中用了14个可逆门、22个垃圾输出、13个单位延迟；文献［13］中用了10个可逆门、产生11个垃圾输出、10个单位延迟。经过比较之后，发现文中设计的可逆BCD加法电路是无论在门的数量上，还是在垃圾输出，逻辑延时上都达到最优。具体比较于表3所示。

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

4 结论

主要介绍了在经典BCD加法电路的基础上用可逆门设计出可逆BCD加法电路。提出了新型4×4可逆逻辑门——NC门，该门不但能够独立实现可逆BCD溢出检测逻辑电路，还能减少电路中门数量和垃圾输出数量，将电路达到最优的效果。在此基础上，利用现有的可逆门——ZS门设计出可逆BCD加法电路，同时分析了该电路的门数量、垃圾输出数量、单位延迟，分析得出本文设计的可逆BCD加法电路不仅在门数量、垃圾输出数量还是在单位延迟上比现有的效果都要好。

可逆逻辑已经运用在光学计算机、纳米技术、量子计算机等多种领域。而本文可逆BCD加法电路正是在可逆计算领域的一些尝试，这些尝试对于设计更加复杂的量子系统，如量子CPU的运算部件和逻辑部件来说，或许是一个促进作用。

［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］.电子技术，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

国家自然科学基金项目（61065002）；江西省自然科学基金项目（2009GZS0013）；江西省教育厅科研基金项目（GJJ11433）

周日贵（1973－），男，教授，博士，研究方向为量子计算与量子神经网络。