四位可逆数值比较器

摘要

本发明公开了一种四位可逆数值比较器，包括：四个1位可逆数值比较器单元、两个作为1位可逆与门的New门，两个3位可逆与门电路单元、三个4位可逆与门电路单元、两个4位可逆或门电路单元以及作为复制的若干个Feynman门。利用本发明的四位可逆数值比较器，采用并联扩展方式，可以实现数值比较器的位数扩展问题，实现位数更多的可逆数值比较器。

说明书

技术领域

本发明涉及信息技术领域的低功耗的组合逻辑电路设计，特别涉及一种低功耗的四位可逆数值比较器。

背景技术

在数字电路中，经常需要对两个位数相同的二进制数进行比较，以判断它们的相对大小或者是否相等，用来实现这一功能的逻辑电路就成为数值比较器。但传统的数值比较器是不可逆的，并且存在信息位的丢失，能耗较大。

Landauer已证实，由与门、异或门等这些不可逆的传统逻辑门构造的电路在运行过程中，不可避免的会产生能量的损耗。因为在计算过程中，每比特信息的丢失会消耗kT*ln2焦耳的能量，其中k是波尔茨曼常量，T是绝对温度。尽管与其它形式的能耗相比，kT*ln2是一个非常小的量，但在计算中消耗的总能量同信息丢失的个数是成正比的，也就是说，随着信息丢失个数的增加，能耗也随之增加，所以在进行低能耗电路设计时，这一能耗不能忽视。

1973年，Bennett指出，在电路中，为了避免因每比特信息丢失而产生的kT*ln2能耗，必须使用可逆逻辑门。可逆逻辑电路是无信息损失的，在理论上能实现零能耗。因此，用可逆逻辑门设计成的比较器可以大大的降低系统能耗。

发明内容

本发明的目的是提供一种信息位不丢失、能耗较小的四位可逆数值比较器，本发明是通过以下的技术方案实现的：

一种四位可逆数值比较器，包括：四个1位可逆数值比较器单元、两个作为1位可逆与门的NG1、NG2，两个3位可逆与门单元、三个4位可逆与门单元、两个4位可逆或门单元以及作为复制的若干个Feynman门，所述四位可逆数值比较器对两个四位数进行比较，设这两个数为A＝(A₃A₂A₁A₀)和B＝(B₃B₂B₁B₀)，其中最高位A₃和B₃作为第一1位可逆数值比较器单元的两个输入，它的第一输出作为第一4位可逆或门单元的第一输入，第二输出分别作为NG1、NG2、第一3位可逆与门单元、第二3位可逆与门单元、第一4位可逆与门单元、第二4位可逆与门单元、第三4位可逆与门单元的输入之一，第三输出作为第二4位可逆或门单元的第一输入；A₂和B₂作为第二1位可逆数值比较器单元的两个输入，它的第一输出作为NG1的第二输入，NG1的第二输出作为第一4位可逆或门单元的第二输入，第二1位可逆数值比较器单元的第二输出分别作为第一3位可逆与门单元、第二3位可逆与门单元、第一4位可逆与门单元、第二4位可逆与门单元、第三4位可逆与门单元的输入之一，第二1位可逆数值比较器单元的第三输出作为NG2的第二输入，通过NG2后，NG2的第二输出作为第二4位可逆或门单元的第二输入；A₁和B₁作为第三1位可逆数值比较器单元的两个输入，它的第一输出作为第一3位可逆与门单元的第三输入，该第一3位可逆与门单元的第一输出作为第一4位可逆或门单元的第三输入，第三1位可逆数值比较器单元的第二输出分别作为第一4位可逆与门单元、第二4位可逆与门单元、第三4位可逆与门单元的输入之一，第三1位可逆数值比较器单元的第三输出作为第二3位可逆与门单元的第三输入，该第二3位可逆与门单元的第一输出作为第二4位可逆或门单元的第四输入；A₀和B₀作为第四1位可逆数值比较器单元的两个输入，它的第一输出作为第一4位可逆与门单元的第四输入，该第一4可逆与门单元的第一输出作为第一4位可逆或门单元的第四输入，第四1位可逆数值比较器单元的第二输出作为第三4位可逆与门单元的第四输入，第三输出作为第二4位可逆与门单元的第四输入，该第二4位可逆与门单元的第一输出作为第二4位可逆或门单元的第三输入；第一4位可逆或门单元的第一输出是第二4位可逆或门单元的第一输出是第三4位可逆与门单元的第一输出是F_A＝B。

利用本发明所述的四位可逆数值比较器，采用并联扩展方式，可以实现数值比较器的位数扩展、信息位不丢失、能耗减小等问题，实现位数更多的可逆数值比较器。

附图说明：

图1：用来复制信号的Feynman门；

图2：实现1位与功能的New门；

图3：NLG门；

图4：URG门；

图5a：1位可逆数值比较器；

图5b：1位可逆数值比较器单元；

图6a：实现n位与功能的可逆电路；

图6b：n位可逆与门单元；

图7a：实现n位或功能的可逆电路；

图7b：n位可逆或门单元；

图8：四位可逆数值比较器。

具体实施方式：

为了加深对本发明的理解，下面将结合实施例和附图对本发明作进一步详述，该实施例仅用于解释本发明，并不构成对本发明保护范围的限定。

本发明所述四位可逆数值比较器包括：1位可逆数值比较器、3位可逆与门单元、4位可逆与门单元、4位可逆或门单元，New门及若干Feynman门。

下面分别介绍每个模块的构建：

1、一位可逆数值比较器。一位可逆数值比较器的功能表如表1所示，其结构框图见图5a。

表1一位可逆数值比较器的功能表

由图5a可知，该1位可逆数值比较器由两个Feynman门、两个非门、两个New门(NG)及一个NLG门级联而成。Feynman门在本发明中都是用来复制信号的(见图1)，当其中一个输入为A，另一个输入置零时，得到的两个输出都为A。New门在本发明中都是用来实现1位与功能的(见图2)，当New门的第三输入置零，第一输入为A，第二输入为B时，它的第二输出就实现了与的功能，即输出为AB，另外，其第一个输出为A，第三输出为这两个输出都视为无用输出。NLG门如图3所示，它的第一输入为A，第二输入为B时，它实现的功能是：当输入A＝B时，输出Q＝1；当输入A≠B时，输出Q＝0。

在图5a中，A作为第一Feynman门的第一输入，第二输入置零；同理，B作为第二Feynman门的第一输入，第二输入置零。第一Feynman门的第一输出作为第一非门的输入，第一非门的输出作为第一New门的第一输入，第二Feynman门的第二输出作为第一New门的第二输入，第一New门的第三输入置零；第一Feynman门的第二输出作为第二New门的第二输入，第二Feynman门的第一输出作为第二非门的输入，第二非门的输出作为第二New门的第一输入，第二New门的第三输入置零。第一New门的第一输出作为NLG门的第一输入，第二New门的第一输出作为NLG门的第二输入。第一New门的第二输出为F_A＜B，第三输出为无用输出g₁；第二New门的第二输出为F_A＞B，第三输出为无用输出g₂；NLG的第二输出为F_A＝B，第一输出为无用输出g₃。其相应的可逆单元见图5b。

2、实现n位与功能的可逆电路。该可逆电路由(n-1)个New门级联实现(见图6a)，附带(2n-2)个无用输出。其相应的可逆单元见图6b。

3、实现n位或功能的可逆电路。该可逆电路由(n-1)个URG门级联实现(见图7a)，附带(2n-2)个无用输出。其相应的可逆单元见图7b。

URG门在本发明中是用来实现1位或功能的，其结构如图4所示。当URG门的第三个输入置零，第一个输入为A，第二个输入为B时，它的第一个输出为A+B，实现了或功能。另外，其第二个输出为B，第三个输出为AB，这两个输出都视为无用输出。

4、四位可逆数值比较器。本发明中的四位可逆数值比较器的功能表见表2，其电路结构如图8所示。该数值比较器是对两个二进制数A、B进行比较，其中A＝(A₃，A₂，A₁，A₀)，B＝(B₃，B₂，B₁，B₀)。A₃作为第一1位可逆数值比较器单元的第一输入，B₃作为其第二输入，第三输入置零；A₂作为第二1位可逆数值比较器单元的第一输入，B₂作为其第二输入，第三输入置零；A₁作为第三1位可逆数值比较器单元的第一输入，B₁作为其第二输入，第三输入置零；A₀作为第四1位可逆数值比较器单元的第一输入，B₀作为其第二输入，第三输入置零。

表2四位可逆数值比较器的功能表

第一1位可逆数值比较器单元的第一输出为只使用一次，所以直接作为第一4位可逆或门单元的第一输入。第一1位可逆数值比较器单元的第二输出为需要重复利用七次，即分别作为NG1、NG2、第一3位可逆与门单元、第二3位可逆与门单元、第一4位可逆与门单元、第二4位可逆与门单元及第三4位可逆与门单元的输入之一，所以需要用到六个Feynman门来实现，避免可逆逻辑中的扇出问题。

具体说明，第一1位可逆数值比较器单元的第二输出作为Fey01的第一输入，其第二输入置零，它的第一输出作为Fey03的第一输入，其第二输出作为Fey02的第一输入。Fey02的第二输入置零，Fey02的第一输出作为第三4位可逆与门单元的第一输入，其第二输出作为Fey04的第一输入。Fey03的第二输入置零，它的第一输出作为NG1的第一输入，第二输出作为Fey05的第一输入。Fey04的第二输入置零，第一输出作为NG2的第一输入，第二输出作为Fey06的第一输入。Fey05的第二输入置零，第一输出作为第一3位可逆与门单元的第一输入，第二输出作为第一4位可逆与门单元的第一输入。Fey06的第二输入置零，第一输出作为第二3位可逆与门单元的第一输入，第二输出作为第二4位可逆与门单元的第一输入。

第一1位可逆数值比较器单元的第三输出为只使用一次，直接作为第二4位可逆或门单元的第一输入。

第二1位可逆数值比较器单元的第一输出为它作为NG1的第二输入。

第二1位可逆数值比较器单元的第二输出为需要重复利用5次，即分别作为第一3位可逆与门单元、第二3位可逆与门单元、第一4位可逆与门单元、第二4位可逆与门单元及第三4位可逆与门单元的输入之一，所以需要用到四个Feynman门来实现，避免可逆逻辑中的扇出问题。

具体说明，第二1位可逆数值比较器单元的第二输出作为Fey11的第一输入，第二输入置零，它的第一输出作为Fey13的第一输入，第二输出作为Fey12的第一输入。Fey12的第二输入置零，第一输出作为第三4位可逆与门单元的第二输入，第二输出作为Fey14的第一输入。Fey13的第二输入置零，它的第一输出作为第一3位可逆与门单元的第二输入，第二输出作为第一4位可逆与门单元的第二输入。Fey14的第二输入置零，第一输出作为第二4位可逆与门单元的第二输入，第二输出作为第二3位可逆与门单元的第二输入。

第二1位可逆数值比较器单元的第三输出为它只需使用一次，作为NG2的第二输入。

第三1位可逆数值比较器单元的第一输出为它只需使用一次，作为第一3位可逆与门单元的第三输入。

第三1位可逆数值比较器单元的第二输出为需要重复利用3次，即分别作为第一4位可逆与门单元、第二4位可逆与门单元及第三4位可逆与门单元的输入之一，所以需要用到2个Feynman门来实现，避免可逆逻辑中的扇出问题。

具体说明，第三1位可逆数值比较器单元的第二输出作为Fey21的第一输入。Fey21的第二输入置零，它的第一输出作为第一4位可逆与门单元的第三输入，第二输出作为Fey22的第一输入。Fey22的第二输入置零，第一输出作为第二4位可逆与门单元的第三输入，第二输出作为第三位可逆与门单元的第三输入。

第三1位可逆数值比较器单元的第三输出为它只需使用一次，作为第二3位可逆与门单元的第三输入。

第四1位可逆数值比较器单元的第一输出为它只需使用一次，作为第一4位可逆与门单元的第四输入。

第四1位可逆数值比较器单元的第二输出为它只需使用一次，作为第二4位可逆与门单元的第四输入。

第四1位可逆数值比较器单元的第三输出为它只需使用一次，作为第三4位可逆与门单元的第四输入。

NG1的第三输入置零，第一输出及第三输出都是无用输出，第二输出作为四位可逆或门单元1的第二输入。NG2的第三输入置零，第一输出及第三输出都是无用输出，第二输出作为第二4位可逆或门单元的第二输入。

第一3位可逆与门单元的第一输出作为第一4位可逆或门单元的第三输入，第二输出及第三输出作为无用输出。

第二3位可逆与门单元的第一输出作为第二4位可逆或门单元的第四输入，第二输出及第三输出作为无用输出。

第一4位可逆与门单元的第一输出作为第一4位可逆或门单元的第四输入，第二输出、第三输出及第四输出作为无用输出。

第二4位可逆与门单元的第一输出作为第二4位可逆或门单元的第三输入，第二输出、第三输出及第四输出作为无用输出。

第一4位可逆或门单元的第一输出为F_A＞B，第二输出、第三输出及第四输出作为无用输出。

第二4位可逆或门单元的第一输出为F_A＜B，第二输出、第三输出及第四输出作为无用输出。

第三4位可逆与门单元的第一输出为F_A＝B，第二输出、第三输出及第四输出作为无用输出。

从上述可知，本发明是对两个四位数进行比较，设这两个数为A＝(A₃A₂A₁A₀)和B＝(B₃B₂B₁B₀)，其中最高位A₃和B₃作为第一1位可逆数值比较器单元的两个输入，它的第一输出作为第一4位可逆或门单元的第一输入。第二输出分别作为NG1、NG2、第一3位可逆与门单元、第二3位可逆与门单元、第三4位可逆与门单元、第四4位可逆与门单元、第五4位可逆与门单元的输入之一，也就是一共用到了7次，利用6个Feynman门来实现对第二输出的六次复制。第三输出作为第二4位可逆或门单元的第一输入。

A₂和B₂作为第二1位可逆数值比较器单元的两个输入，它的第一输出作为NG1的第二输入。通过NG1后，它的第二输出是和的与运算结果，并将这一结果作为第一4位可逆或门单元的第二输入。第二输出分别作为第一3位可逆与门单元、第二3位可逆与门单元、第一4位可逆与门单元、第二4位可逆与门单元、第三4位可逆与门单元的输入之一，也就是一共用到了5次，利用4个Feynman门来实现对第二输出的4次复制。第三输出作为NG2的第二输入。通过NG2后，它的第二输出是和的与运算结果，并将这一结果作为第二4位可逆或门单元的第二输入。

A₁和B₁作为第三1位可逆数值比较器单元的两个输入，它的第一输出作为第一3位可逆与门单元的第三输入。通过该第一3位可逆与门单元后，它的第一输出是和的与运算结果，并将这一结果作为第一4位可逆或门单元的第三输入。第二输出分别作为第一4位可逆与门单元、第二4位可逆与门单元、第三4位可逆与门单元的输入之一，也就是一共用到了3次，利用2个Feynman门来实现对第二输出的2次复制。第三输出作为第二3位可逆与门单元的第三输入。通过该第二3位可逆与门单元后，它的第一输出是和的与运算结果，并将这一结果作为第二4位可逆或门单元的第四输入。

A₀和B₀作为第四1位可逆数值比较器单元的两个输入，它的第一输出作为第一4位可逆与门单元的第四输入。通过该第一4位可逆与门单元后，它的第一输出是和的与运算结果，并将这一结果作为第一4位可逆或门单元的第四输入。第二输出作为第三4位可逆与门单元的第四输入。第三输出作为第二4位可逆与门单元的第四输入，通过该第二4位可逆与门单元后，它的第一输出是和的与运算结果，并将这一结果作为第二4位可逆或门单元的第三输入。

第一4位可逆或门单元的第一输出是F_A＞B；第二4位可逆或门单元的第一输出是F_A＜B；第三可逆与门单元的第一输出是F_A＝B。

本发明所述四位可逆数值比较器的工作原理为：

四位可逆数值比较器电路利用了四个1位可逆数值比较器的输出作为中间结果。它所依据的原理是，如果四位数A₃A₂A₁A₀和B₃B₂B₁B₀的最高位不相等，则最高位比较结果就是两数的比较结果，与低位无关。举例说明：如果此时则第一4位可逆或门单元打开，且低位比较结果不能影响第一4位可逆或门单元，最高位比较结果从第一4位可逆或门单元直接输出，即得输出结果为F_A＞B＝1。因为此时所以所有4位可逆与门单元均封锁，它们的有用输出都为0，所以可得F_A＝B＝0。此时第二4位可逆或门单元的输入都为0，所以可得F_A＜B＝0。

若最高位A₃＝B₃，则再次比较次高位A₂和B₂。举例说明：如果此时且则NG1的第二输出为1，作为第一4位可逆或门单元的第二输入，这是次或门打开，且低位比较结果不能影响第一4位可逆或门单元，比较结果从第一4位可逆或门单元直接输出，即得输出结果为F_A＞B＝1。因为此时所以除了NG1打开外，其它所有的4位可逆与门单元均封锁，它们的有用输出都为0，所以可得F_A＝B＝0。此时第二4位可逆或门单元的输入都为0，所以可得F_A＜B＝0。

其它的情况分析类似。显然，如果两数相等，那么，必须将比较进行到最低位才能得到结果。