加法器

维基百科,自由的百科全书
跳转至: 导航搜索

电子学中,加法器英语adder)是一种用于执行加法运算的数字电路部件,是构成电子计算机核心微处理器算术逻辑单元的基础。在这些电子系统中,加法器主要负责计算地址、索引等数据。除此之外,加法器也是其他一些硬件,例如二进制数乘法器的重要组成部分。

尽管可以为不同计数系统设计专门的加法器,但是由于数字电路通常以二进制为基础,因此二进制加法器在实际应用中最为普遍。在数字电路中,二进制数的减法可以通过加一个负数来间接完成。为了使负数的计算能够直接用加法器来完成,计算中的负数可以使用二补数(补码)来表示,具体的细节可以参考数字电路相关的书籍。[1]:244-248

半加器[编辑]

一位半加器的符号

半加器的功能是将两个一位二进制数相加。它具有两个输入和两个输出(分别是和、进位)。输出的进位信号代表了输入两个数相加溢出的高一位数值。因此,这两2个一位二级制数的和等于2C + S。根据两个一位二进制数相加的结果,可以通过真值表、卡诺图得到右图所描绘的简易半加器设计。它使用了一个异或门来产生和S,并使用了一个与门来产生进位信号C。如果再添加一个或门来接收低位的进位输出信号,则两个半加器就构成了一个全加器。[2]

全加器[编辑]

一位全加器的符号,它与半加器不同之处在于它还能接收一个低位进位输入信号Cin。图中的蓝框是为了表明它作为一个整体可以级联构成多位二进制数的加法器。

全加器将两个一位二进制数相加,并根据接收到的低位进位信号,输出和、进位输出。全加器的三个输入信号为两个加数AB和低位进位Cin[3]全加器通常可以通过级联(cascade)的方式,构成多位(如8位、16位、32位)二进制数加法器的基本部分。全加器的输出和半加器类似,包括向高位的进位信号Cout和本位的和信号S,相加结果的总和表达为\mathrm{sum} = 2 \times C_{out} + S。一位全加器的真值表为:

全加器的符号
输入 输出
A B Cin Cout S
0 0 0 0 0
1 0 0 0 1
0 1 0 0 1
1 1 0 1 0
0 0 1 0 1
1 0 1 1 0
0 1 1 1 0
1 1 1 1 1

在实际的应用中,全加器可以通过不同的方式制造,例如直接利用晶体管级的电路,或者由其他现成的逻辑门来构成。和、进位信号对应的逻辑函数表达式分别为S = A \oplus B \oplus C_{in}以及C_{out} = (A \cdot B) + (B \cdot C) + (A \cdot C)。另一种全加器电路与之前的方式略有不同,它用一个异或门来代替或门对其中两个输入信号进行求和,其进位信号对应的逻辑函数表达式分别为C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))。通过适当的逻辑函数变化,可以证明它与前面的计算方法结果一致。[1]:238, 260

将两个输入端AB连接到一个半加器上,然后将其和输出信号、进位输出信号分别作为第二个半加器的两个输入,并将两个进位输出信号进行逻辑或运算。可以使用一个三输入的异或门来求和,再使用一个两级与或结构来实现进位信号对应的积之和(sum of products)式。

更复杂的加法器[编辑]

漣波进位加法器[编辑]

用四个一位全加器构成的四位漣波进位加法器

可以使用多个一位全加器来构成N位加法器,其中对应低位的全加器将其进位输出信号Cout连接到高一位的全加器的进入输入端Cin。这种构成多位加法器的形式被称为“漣波进位加法器(ripple-carry adder)”,“漣波”形象地描述了进位信号依次向前传递的情形。如果不需要连接其他进位信号,则最低位的全加器可以用半加器替换。

脉动进位加法器(漣波進位加法器)的电路布局形式较为简单,设计这种电路花费时间较短。然而,漣波进位加法器的进位输出、输入所经过的路径上比其他布局方式具有较多的邏輯閘,高位的计算必须等待低位的进位输出信号被计算出来才能开始,因此造成了更大的延迟时间[4]:49

下面简单计算信号在加法器中的延迟。每一个全加器具有三级逻辑函数。在一个32位的漣波进位加法器中,随之产生的邏輯閘延迟则可以根据关键路径(critical path,即经历最多邏輯閘的路径)的延迟时间来决定,即3倍的最高位全加器输入信号、进位输出延迟,加上31乘以2倍的其他全加器上的延迟,总共等于65倍的邏輯閘延迟。通过使用其他的连接方式,可以减少延迟时间。[5]

超前进位加法器[编辑]

四位超前进位加法器
一种2级门4bit加法器的设计

为了减少多位二进制数加减计算所需的时间,工程师设计了一种比脉动进位加法器速度更快的加法器电路,这种加法器被称为“超前进位加法器(carry-lookahead adder)”。

下面简述超前进位加法器的主要原理。[6][1]:255-262我们先来考虑构成多位加法器的单个全加器从其低一位获得的进位信号c_{i+1} = (x_i \cdot y_i) + (x_i \cdot c_i) + (y_i \cdot c_i),我们可以将它变换为c_{i+1} = (x_i \cdot y_i) + ( x_i + y_i ) \cdot c_i。现在为二级制数的每一位构建两个新信号:

  • 生成(Generate)信号:G_i = x_i \cdot y_i
  • 传输(Propagate)信号:P_i = x_i \oplus y_i

于是,某位全加器从低一位获得的进位可以表示为c_{i+1} = G_i + P_i \cdot c_i,例如次低位全加器从最低位获得的进位为c_1 = G_0 + P_0 \cdot c_0,而从最低位开始第三位的那个全加器获得的进位信号则为c_2 = G_1 + P_1 \cdot c_1。在多位脉动进位加法器中,c_2必须连接到低一位的进位输出信号,如果使用这种方式构成多位全加器,则逻辑门的延迟会发生累加,导致降低电路的计算效率下降。超前进位加法器采取的方式是,将c_1的逻辑函数代入到c_2,即c_2 = G_1 + P_1 \cdot ( G_0 + P_0 \cdot c_0 ),于是,这一位的进位输出就只取决于x_1y_1x_0y_0c_0几个信号,而这几个信号都是计算电路外部的已知信号,而非低一位的计算结果。上面考虑的是从最低位开始第三位的情况。采用类似的代入方法,可以用各位的生成信号G_i、传输信号P_i,以及最低位从外部获取的进位信号c_0来表示多位全加器的所有进位信号。

六十四位全加器可以逻辑划分为四个十六位超前进位加法器

通过列出多位加法器各位的进位输出,可以发现高位的进位输出表达式(积之和式)涉及的变量更多,对应的逻辑电路连线会变得更复杂,而且在实际应用中会遭遇逻辑门的扇入问题。因此有必要对位数过高的全加器进行逻辑划分,如将六十四位全加器分为四个十六位超前进位加法器来实现(如右图)。多位二进制数加法器的标准芯片通常具有超前进位的组成形式,例如7400系列的7483、74283芯片。[4]:50

参考文献[编辑]

  1. ^ 1.0 1.1 1.2 Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. ISBN 0-07-283878-7. 
  2. ^ Geoffrey A. Lancaster. Excel HSC Software Design and Development. Pascal Press. 2004. 180. ISBN 9781741251753. 
  3. ^ M. Morris Mano. Digital Logic and Computer Design. Prentice-Hall. 1979. 119-123. ISBN 0-13-214510-3. 
  4. ^ 4.0 4.1 邓元庆,关宇,贾鹏,石会. 数字设计基础与应用. 清华大学出版社. ISBN 978-7-302-21406-9. 
  5. ^ Burgess, N. Fast Ripple-Carry Adders in Standard-Cell CMOS VLSI. 20th IEEE Symposium on Computer Arithmetic. 2011: 103–111. 
  6. ^ Fast Addition: Carry Lookahead Adders. University of Maryland. [2013-02-28]. 

外部链接[编辑]