3.2 Wallace树加法

　　在采用改进Booth算法将部分积数目减少为原来的一半之后，乘法运算的主要问题就是处理多个多比特二进制操作数相加的问题。最直观的算法是将多个部分积逐一累加，但效率很低，运算时延巨大。

　　Wallace在1964年提出采用树形结构减少多个数累加次数的方法，称为Wallace树结构加法器。Wallace树充分利用全加器3-2压缩的特性，随时将可利用的所有输入和中间结果及时并行计算，因而可以将N个部分积的累加次数从N-1次减少到log2N次，大大节省了计算时延。如图2所示为Wallace树结构与CSA结构的对照，其结构的关键特征在于利用不规则的树形结构对所有准备好输人数据的运算及时并行处理。

　　Wallace树结构一般用于设计高速乘法器，其显著优点是速度快，尤其对处理多个数相加的情况具有相当的优越性，缺点是其逻辑结构形式不规整，在VLSI设计中对布局布线的影响较大。

3.3 进位的快速传递

　　考虑到提高两个多比特操作数相加运算的速度，关键在于解决进位传递时延较大的问题。采用以牺牲硬件资源面积换取速度的方式，以独立的逻辑结构单独计算各个加法位需要的进位输入以及产生的进位输出，提高进位传递的速度，从而提高加法运算速度。

3.3.1 四位超前进位加法器的设计

　　两个加数分别为A3A2A1A0，B3B2BB1B0，C-1为低位进位。令两个辅助变量分别为G3G2G1G0和P3P2P1P0：Gi=Ai&Bi，Pi=Ai+Bi。G和P可用与门、或门实现。

　　一位全加器的逻辑表达式可化为：

　　利用上述关系，一个4比特加法器的进位计算就变化为下式：

　　由式(7)可以看出每一个进位的计算都直接依赖于整个加法器的最初输入，而不需要等待相邻低位的进位传递。理论上，每一个进位的计算都只需要3个门延迟时间，即同时产生G[i]，P[i]的与门以及或门，输入为G[i]，P[i]，C-1的与门，以及最终的或门。同样道理，理论上最终结果sum的得到只需要5个门延迟时间。

　　实际上，当加数位数较大时，输入需要驱动的门数较多，其VLSI实现的输出时延增加很多，考虑互联线延时的情况将会更加糟糕。因此，通常在芯片实现中设计位数较少的超前进位加法器结构，而后以此为基本结构构造位数较大的加法器。

3.3.2 进位选择加法器结构

　　实际上，超前进位加法器只是提高了进位传递的速度，其计算过程与行波进位加法器同样需要等待进位传递的完成。借鉴并行计算的思想，人们提出了进位选择加法器结构，其算法的实质是增加硬件面积换取速度性能的提高。利用二进制加法的特点，进位或者为逻辑1，或者为逻辑0，二者必居其一。将进位链较长的加法器分为M块分别进行加法计算，对除去包含最低位计算的M-1块加法结构复制两份，其进位输入分别预定为逻辑1和逻辑0，于是M块加法器可以同时并行进行各自的加法运算，然后根据各自相邻低位加法运算结果产生的进位输出，选择正确的加法结果输出。

4 基于FPGA设计FIR数字滤波器

　　clk2为FIR数字滤波器的工作时钟，clk2频率远大于clk1频率。其工作过程：clk1时钟的上升沿启动一次计算过程，控制器输出reset信号使触发器1清0；其后每个clk2周期计算一个h(i)[x(i)+x(N-i-1)]并进行累加，共需N／2个clk2周期完成计算，完成计算后控制器输出OE信号将结果输出。

　　(1) 对冲激响应系数h的处理：由Matlab设计FIR滤波器系数是一系列的浮点数，而FPGA不支持浮点数的运算，因此浮点数需转换成定点数，设计可采用Q值量化法，把系数扩大了27=128倍，然后转化为8位二进制数补码。最终结果再右移7位就可等到真正结果。

　　(2) 本设计对于有符号数采用补码表示的方法，在设计中多次出现加法运算，可能会产生溢出，所以应进行符号位扩展。将符号位扩展到输出统一的最高位，才能够保证计算结果的正确性。

　　扩展方法为：

　P9P8P7P6P5P4P3P2P1P0

　=P9P9P9P9P9P8P7P6P5P4P3P2P1P0

　　其中：P9为补码的符号位。

　　(3) Booth编码处理由于存在求“-x”的运算，需进行求反加1。如果每1次调用Booth编码都进行加1运算，不仅使资源大大浪费，而且由于位数较长，也会大大影响乘法器的速度。而本设计将加1放在Wallace树中计算，尽管多了1级Wallace树，但速度和资源上都大大提高了。

　　(4) 由于FIR是线性相位，h(i)=h(15-i)，可以将乘法运算由16次减少到8次；再通过对h(i)进行Booth编码可以将部分积减少到4个；最终利用Wallace树以及超快速加法器将4个部分积的相加，得到8*8乘法器的结果。由于将Booth编码中的加1放在Wallace树中，经过分析需要3级Wallace树。

5 FIR滤波器的频率特性分析

　　利用Matlab中rand()和round()函数产生-128～128之间中100个整随机数。

　　比较输入x与输出y的幅频特性，可以看出FIR滤波器为低通滤波，指标符合设计要求。

6 用ISE综合分析FIR滤波器的性能分析

　　分析设计框图可以看出，占用时间最长的路径为8位加法器——乘法器——累加器，这是影响工作频率最主要的部分。设计中采用流水线技术，在这条路径中增加寄存器，将最长路径拆分成较短路径，可以取得比较好的效果，提高系统的工作频率。