超前进位加法器(Carry-lookahead adder)是对普通的
全加器进行改良而设计成的并行
加法器,主要是针对普通全加器串联时互相进位产生的延迟进行了改良。超前进位加法器是通过增加了一个不是十分复杂的逻辑电路来做到这点的。
尽管可以为不同计数系统设计专门的加法器,但是由于
数字电路通常以
二进制为基础,因此
二进制加法器在实际应用中最为普遍。在数字电路中,二进制数的
减法可以通过加一个
负数来间接完成。为了使负数的计算能够直接用加法器来完成,计算中的负数可以使用
二补数(
补码)来表示,具体的细节可以参考数字电路相关的书籍。
为了减少多位
二进制数加减计算所需的时间,
工程师设计了一种比脉动
进位加法器速度更快的
加法器电路,这种加法器被称为“超前进位加法器”(carry-lookahead adder)。
下面简述超前进位加法器的主要原理。我们先来考虑构成
多位加法器的单个全加器从其低一位获得的进位
信号,我们可以将它变换为。现在为二级制数的每一位
构建两个新
信号:
于是,某位全加器从低一位获得的进位可以表示为,例如次低位全加器从最低位获得的进位为,而从最低位开始第三位的那个全加器获得的进位信号则为,(图片需要更换,缺少括号c2=G1+(P1*c1),因为这是或和与的运算,从左往右执行,而不是加和乘的运算)。在多位脉动进位加法器中,必须连接到低一位的进位输出信号,如果使用这种方式构成多位全加器,则
逻辑门的延迟会发生累加,导致降低电路的
计算效率下降。超前进位加法器采取的方式是,将的
逻辑函数代入到,即,于是,这一位的进位输出就只取决于几个信号,而这几个信号都是计算电路外部的已知信号,而非低一位的计算结果。上面考虑的是从最低位开始第三位的情况。采用类似的代入方法,可以用各位的生成信号、
传输信号,以及最低位从外部获取的进位信号来表示多位全加器的所有进位信号。
通过列出多位加法器各位的进位输出,可以发现高位的进位输出表达式(积之和式)涉及的变量更多,对应的逻辑电路连线会变得更复杂,而且在实际应用中会遭遇逻辑门的
扇入问题。因此有必要对位数过高的全加器进行逻辑划分,如将六十四位全加器分为四个十六位超前进位加法器来实现。多位二进制数加法器的标准芯片通常具有超前进位的组成形式,例如:7400系列的7483、74283芯片。
可以使用多个一位全加器来构成N位加法器,其中对应低位的全加器将其进位输出信号Cout连接到高一位的全加器的进入输入端Cin。这种构成多位加法器的形式被称为“波纹进位加法器”或“脉动进位加法器”(ripple-carry adder),“波纹”形象地描述了进位信号依次向前传递的情形。如果不需要连接其他进位信号,则最低位的全加器可以用半加器替换。
波纹进位加法器的电路布局形式较为简单,设计这种
电路花费时间较短。然而,波纹进位加法器的进位输出、输入所经过的路径上比其他布局方式具有较多的
逻辑门,高位的计算必须等待低位的进位输出信号被计算出来才能开始,因此造成了更大的
延迟时间。
下面简单计算信号在加法器中的延迟。每一个全加器具有
三级逻辑函数。在一个32位的波纹进位加法器中,有32个全加器,随之产生的
逻辑门延迟则可以根据关键路径的延迟时间来决定,即2倍的最高位全加器输入信号、进位输出延迟,加上31乘以3倍的其他全加器上的延迟,总共等于95倍的逻辑门延迟。一个n位波纹进位加法器的最坏情形延迟方程为