【摘 要】目前使用分布式算法是FPGA设计FIR数字滤波器常用的结构，本文主要对基于FPGA分布式算法的三种常用实现结构进行了深入的分析与研究，在此基础上，针对三种结构存在的缺陷与不足，提出了优化改进方案，并分析了改进方案的优势，对设计数字滤波器具有一定参考意义和实用价值。

　　【关键词】FPGA 分布式算法（DA） 查找表 数字滤波器

　　一、引言

　　分布式算法（distributed arithmetic，DA）是在上个世纪70年代初被首次提出的，但直到Xilinx公司发明FPGA（现场可编程门阵列，Field Programmable Gate Array）的查找表结构以后，DA算法才广泛应用在计算乘积和之中。与传统算法相比，分布式算法可以极大地减少硬件电路规模，很容易实现流水线处理，提高电路的执行速度。这种方法是目前比较常用的基于FPGA设计FIR滤波器的方法。

　　分布式算法与传统的乘法器结构相比，因巧妙的利用ROM查找表将固定系数的乘累加运算转化为查表操作，消除了消耗资源的乘法器，因此，当数据的位宽比较小时，就实现FIR滤波器的速度而言，DA算法要明显比乘累加运算快。但对于分布式算法的三种常用实现结构，不论是串行的、串并结合，还是全并行流水结构来实现基于DA算法的滤波器，当阶N很大时，需要的硬件资源很多，有时是不可能实现的，所以需要寻找一种改进的实现结构来降低硬件资源的消耗。

　　二、分布式算法实现结构分析

　　DA算法能用多种的结构来实现，最简单、直观的方法如图1所示。

　　下面，仔细分析一下分布式算法的性能：首先，从图1中可以看出基于DA算法的滤波器，不需要通用乘法器。其次，基于此种结构，由B为输入数据的位宽，完成一次滤波需要B次累加，也即需要B个时钟周期来完成一次运算，所以这种结构的滤波器对处理B较小的系统有比较明显的优势。最后，因为此种结构的滤波器的查找表的大小有阶数N决定，共需个LUT单元，又每个单元的位宽由系数的量化位宽决定，设系数量化位宽是，所以每个单元位宽为（），则共需要（）*2N字节的查找表单元，也即当N较大时，消耗太多的LUT单元，所以这种结构的不适合N比较大的情况。下面再分析全并行（即速度最优化）DA算法的实现，其实质是图1的一种变换形式，即将基于DA算法的LUT复制B份，而每一份的内容相同，这样就可以同时对B份LUT进行查找，同时得到B个中间结果，再对这B个结果采用加法器树相加，就构成了如图2结构的滤波器。

　　这种结构的DA算法完成滤波只需要一个时钟周期，然而，它必须消耗更多的硬件资源，如设计N阶滤波器，输入变量为B个字节，则共需（）**B字节的RAM资源，当N更大时，消耗更多，且还要增加额外的寄存器和加法器，所以我们可知，此种结构是以消耗硬件资源来换取高速度，显然是很不经济的做法。

　　基于上图还有一种变换形式是介于上述两种实现结构之间，也即串并结合的实现结构，这种结构是把DA算法的LUT复制C份，且2<=C　　综上所述，不论是串行的、串并结合的还是全并行流水结构来实现基于DA算法的滤波器，它们的每个查找树的大小均需（）*字节的RAM，并且都有各自的缺点，即当N很大时，需要的硬件资源很多，有时是不可能实现的。所以需要寻找一种改进的实现结构来降低硬件资源的消耗。

　　三、 改进的DA解决方案

　　如果系数N过大，则可把系数进行分组，再利用部分查找表并将结果相加，假设在加上流水线寄存器，显然在没有降低速度的情况下，却可以极大地减少设计规模，因为查找表单元随着滤波器系数N的增加而呈指数增加。

　　假设长度为LN，则：

　　可用一个DA单元结构实现，且将和分配到L个独立的N阶并行DA的查找表单元中，如下式：

　　举例如下，设L=4，即设计一个4N的滤波器，则需3额外的加法器，结构如图3：

　　如图3可知，将输入数据按阶数分组，分解成L个小滤波器，显然对于一个固定N系数的滤波器有多种不同的分组方法，即N=L×n，因此每组可有n（小滤波器的阶数）个数据，分成L组，则共需要的LUT单元数为L×个。分析可知，分的组数越多，所需的LUT单元数越少，但是，同时所需的加法器也增加。所以，在实际应用中，划分的组数要依据实际的情况来分析，节省资源是我们必须考虑的总原则。

　　四、结束语

　　对基于FPGA分布式算法实现结构的分析和改进，理论上可以大大提高资源的利用率，为进一步优化FIR数字滤波器的设计提供了新的思路。下一步可根据改进的DA方案进行仿真和设计，但由于滤波器本身的复杂性，其实际效果还与许多因素有关，还有待进一步的检验。

　　参考文献：

　　[1]Macpherson，K N，Stewart，R W Low FPGA area multiplier blocks for full parallel FIR filters[J].Field-Programmable Technology，2004 IEEE International Conference on 2004 Page（s）

　　[2]王传旭，刘云。FIR低通数字滤波器设计[J].电子测量技术，2003{4}

　　[3]Huang W，Krighnan V，Allred D.Design analysis of a distributed arithmetic adaptive FIR filter on an FPGA[J].U.S.Signals， Ssytems&Computers， 2003， Vol.1；

　　[4]徐年，张剑英。基于FPGA的FIR数字滤波器的实现[J].煤炭工程，2007，4：