树型快速加法器的FPGA设计

一、名词解释

加法器：加法器是产生数的和的装置。加数和被加数为输入，和数与进位为输出的装置为半加器；若加数、被加数与低位的进位数为输入，而和数与进位为输出则为全加器。常用作计算机算术逻辑部件，执行逻辑操作、移位与指令调用。在电子学中，加法器是一种数位电路，其可进行数字的加法计算。在现代的电脑中，加法器存在于算术逻辑单元（ALU）之中。 加法器可以用来表示各种数值，如：BCD、加三码，主要的加法器是以二进制作运算。由于负数可用二的补数来表示，所以加减器也就不那么必要。

二、需求说明

加法运算是最基本的算术运算，很多复杂的运算如乘法、除法、FFT、CORDIC等，都可以用加法运算来实现，所以加法器的速度往往影响整个系统的速度，我们不得不关心其性能。现代计算机中，加法运算是最常用的指令之一，正如《计算机组成与设计——硬件/软件接口（第四版）》所提到的硬件设计原则3——加速执行常用操作，对加法器运算速度的提高显得更加重要了。

三、树型加法器

虽说是骡子是马——拉出来溜溜，但是我就不“溜”了，这里直接介绍树型加法器。

在一个一位全加器中，进位的产生有两个途径：1.两个加数都为“1”；2.两个加数有一个为“1”，且来自前一位的进位也为“1”。根据这两个产生进位的途径，可以写出如下表达式：

c_out = ab + (a + b)c_in

进而可以推广到第i位的计算产生第i+1位的进位：

c[i+1] = a[i]b[i] + (a[i] + b[i])c[i]

将g[i] = a[i]b[i]和p[i] = a[i] + b[i]带入其中：

c[i+1] = g[i] + p[i]c[i]

称g[i]为进位产生函数，称p[i]为进位传递函数。可以看到上式是一个递推公式，通过这个公式可以快速的求出任意一位的进位信号。同时，每一个进位产生函数与进位传递函数只与当前位有关，而与其他位无关，这个特点为并行化做好了铺垫。

树型的根部电路图如下，这里的g表示无论前一位的进位是多少，都产生进位信号，所以叫做进位产生信号；这里的p表示加数中只要有一个为高电平，就打开前一位进位向下一位进位的信号开关，所以称其为进位传递函数，其本质上是一个通道、开关。这两个概念很重要。

图1.一位加法器电路

下图为GP生成器电路图，其连接两个上一级产生的模块，输出有3个信号，其中c_out将回传，用以求出本位和；g_out与p_out向下一级传递进位产生和进位传递信息。

图2.GP生成器电路图

GP生成器接收两个“区域”的信息，我称之为高位区和低位区，并且接收低位区的前一级进位信息。GP生成器发出两个方向的信号，一个方向是向两个接收区域的高位区发送低位区向其的进位；另一个方向是向更高一级的GP生成器传递相应的信息。更高一级的GP生成器也要接收到来自两个区域的信息，如此便可以并行的向更高的一级传递其所需要的信息（进位信息），从而达到快速加法的目的。

图3.树型计算结构示意图

上述介绍肯能看起来比较难以理解，其实，快速传递的信息就是进位信息，进位信息的处理就关系到加法器速度的快慢，树型加法器就是用并行的方法实现加速，树型的并行计算结构就是满二叉树的样子，可以参考满二叉树的样子，在结合代码就可以理解树型加法器的概念。

四、分析总结

其实快速加法器可以用assign {c_out + sum} = a + b + c_in这么一个简单的语句实现了，但是了解其内部的原理还是比较有用的。查看网上的一些资料，发现关于快速加法器的介绍都不是特别容易看懂，所以这里参考李亚民先生的设计做为介绍。

五、参考资料

[1]李亚民.计算机原理与设计——Verilog HDL版.北京：清华大学出版社. 2011

注：代码详见上传资料《FPGA_树型快速加法器_verilog.zip》