超前进位加法器原理理解

超前进位加法器(Carry-lookahead adder)是对普通的全加器进行改良而设计成的并行加法器,主要是针对普通全加器串联时互相进位产生的延迟进行了改良。超前进位加法器是通过增加了一个不是十分复杂的逻辑电路来做到这点的。

 

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

超前进位加法器原理理解

(图片来源于互联网)

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

 

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

 

我们用这公式来描述所有2进制加法的进位的计算公式:
ci+1 = xiyi + xici + yici,这里c表示的是进位,举个列子来说就是第一位的进位c1,他是由第零位的x0*y0+x0*c0+y0*c0,这里很明显c1= x0*y0,然后这个提取公因子公式就变成了ci+1 = xiyi + ci(xi + yi),然后这样—来只有ci是不确定的。其他的xi和yi都是直接输入。

 

但是ci通过循环inline的一个替换,其实会变成类似ci+1 = xiyi +(xi + yi) (xi-1yi)-1 + ci-1(xi-1 + yi-1)>,然后可以一直这样替换下去,直到c0这一层。或者是最右端的输入。一般的通常会把这几个变量成为g,p变量。gi - xiyipi - xi + yi。

 

这样理论上可以实现任何位数都在有限次内完成,但是这样的代价是位数越多需要的电路也就越多。这里附上一张wiki中的图来说明
这里第一步的时候,所有的4个全加器对每一位计算出自身的和si,gi和pi然后第二部,超前进位器计算出c1,c2,c3,c4,当然这里的c1,c2,c3,c4计算需要的逻辑门数量是逐步选然后c1,c2,c3对s1,s2,S3进行进位,c4会传递给更上面的位。

 

但是由于成本的问题一般都会把32位或者64位的切割成多个16位的超前进位来进行计算,能取得一个成本和性能上得平衡。

超前进位加法器原理理解

(图片来源于互联网)