超前进位加法器

  首先画出2位全加器的真值表与卡诺图

  根据真值表可知二进制加法与十进制加法一样,进位值是逢二进一.而和值则是上级进位值跟被加数跟加数总和模二的余数.根据卡诺图化简得到S与Ci+1的全加器电路为:

   多位加法器可以用行波进位加法器实现,也就是第一位的Ci为0,第二位开始,Ci就连接着上一级的Ci+1,这样时钟从第一位开始,一直到第N位.但是这样有个时延的问题,一级的Ci需要经过两个门,假设有个32位加法器,要计算第32位时需要经过64个门后才能得到第32个Ci.

   有了加法自然就有减法.减法的实现为被加数加上加数的2的补码.一个N位数X的2的补码K求得为:K=((2的N次方)-1)-X+1.也可以说以基数为2的补码.举个栗子:无符号四位数8-5,8的二进制为1000,5的二进制为0101,现在需要求5的2的补码,2的4次方为16,二进制为10000,减1后为1111,用1111减去0101后得到1010,再加上1,就是1011,现在用1000加上1011就是0011(忽略进位),10进制结果为3.

   有符号和无符号的加法是一样的,需要区别的是结果的最高符号位为0还是1,如果为0则是正数,如果为1则是负数,需要用2的补码方式得到该负数的绝对值.举个栗子:-3-(-2),-3的2的补码为1101,-2的补码为1110,因为是减法,需要得到减数的2的补码,又为0010,1101加0010等于1111,最高位为1,结果是负数,按2的补码方式取绝对值为0001,结果是-1.

   不论加减法都存在算术溢出,也就是两个4位数相加或相减,其结果可能会超出4位的范围.那么判断算术是否有溢出只需要判断结果的符号位与数值最高位是否一致即可,如果一致则表示无溢出,如果不一致,则表示有溢出.

   前面说的行波进位加法器在加上级进位时必须等待上级电路执行完才有结果,而超前进位加法器则不需要等待上一位的执行即可得到前面的进位.可以从本级进位公式中看出:

   Ci+1 = XiYi+(Xi+Yi)Ci

   Ci = Xi-1Yi-1+(Xi-1+Yi-1)Ci-1 

   Ci = Xi-1Yi-1+(Xi-1+Yi-1)(Xi-2Yi-2+(Xi-2+Yi-2)Ci-2)

   这样以此递归下去,直到第0位.其中XiYi是生成函数,记作Gi,因为当被加数和加数都等于1时,不管有没上级进位,本级也一定会进位的,而Xi+Yi是传播函数记作Pi,也就是Xi或Yi其中一个等于1,并且有上级进位,那么那本级也会进位.举个栗子:一个8位超前进位加法器,求它的第八位的上级进位值的函数为:

   C8 = G7+P7C7

   C8 = G7+P7(G6+P6C6)

   C8 = G7+P7(G6+P6(G5+P5C5))

   C8 = G7+P7(G6+P6(G5+P5(G4+P4C4)))
   C8 = G7+P7(G6+P6(G5+P5(G4+P4(G3+P3C3))))

   C8 = G7+P7(G6+P6(G5+P5(G4+P4(G3+P3(G2+P2C2)))))

   C8 = G7+P7(G6+P6(G5+P5(G4+P4(G3+P3(G2+P2(G1+P1C1))))))

   C8 = G7+P7(G6+P6(G5+P5(G4+P4(G3+P3(G2+P2(G1+P1(G0+P0C0)))))))

   因为C0是第一位数值,没有上级可进位,固定为0,把最后面公式从最里面的括号展开转成积之和形式为:

   C8 = G7+P7G6+P7P6G5+P7P6P5G4+P7P6P5P4G3+P7P6P5P4P3G2+P7P6P5P4P3P2G1+P7P6P5P4P3P2P1G0+P7P6P5P4P3P2P1P0C0

   用9个与门和一个或门即可知道C8的的结果值.而C64,C32,C7,C6,C5...也是用以上方式展开,在同一时间,各个位即可知道它的上级进位,而不需要等到它的上一级执行完了才得到进位值.这样并行的加法器大大地缩短了电路时延.

   如果是一个32或者64位的超前进位加法器这样按如上公式写的话会变得长而复杂,所以可以分开8位为一组.用4个八位超前进位加法器即可组成一个32位的.对于以上公式G7+P7G6+P7P6G5+P7P6P5G4+P7P6P5P4G3+P7P6P5P4P3G2+P7P6P5P4P3P2G1+P7P6P5P4P3P2P1G0是生成函数记作S,因为其中每一个乘积项都有一个位生成函数,换句话说只要其中一个乘积项的Xi与Yi都为1,并且它的后续位的Xi或Yi只要其中一个为1,那么本级进位值就为1.而P7P6P5P4P3P2P1P0则是传播函数记作B,只要每一位其中Xi或Yi为1,并且第一位的进位值为1,那么本级进位值就为1.所以以上公式也可以写成C8 = S0+B0C0.就有:

   C32 = S3+B3C3

   C32 = S3+B3(S2+B2C2)

   C32 = S3+B3(S2+B2(S1+B1C1))

   C32 = S3+B3(S2+B2(S1+B1(S0+B0C0)))