基于改进的DA算法实现高阶FIR滤波器

摘 要： 介绍了几种应用于高阶FIR滤波器的算法，着重介绍DA算法，该算法主要基于LUT形式，从根本上减少了乘法器资源的消耗，提高了系统的实时性。并以此为基础介绍了几种改进的算法，分别是基于LUT分解、基于OBC编码以及基于双向选择器的da改进算法，这些算法都从不同程度上降低了资源的使用，提高了信号处理速度，降低了系统复杂性。最后，对FIR滤波器的改进算法进行了全面的分析比较和仿真，仿真结果均正确并且符合设计要求。

关键字： DA算法； FIR滤波器； LUT分解； OBC编码； 双向选择器

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）04?0008?05

Realization of high?order FIR filter based on improved DA algorithm

WANG Zhe， ZHOU Qian?neng

（College of Photoelectric engineering， Chongqing University of Posts and Telecommunications， Chongqing 400065， China）

Abstract： Several kinds of algorithms applied to high?order FIR filter are introduced， among which the DA algorithm is emphatically introduced. The algorithm mainly based on the form of LUT reduced the resource consumption of multiplier radically and improved the real?time performance of the system. On this basis， several kinds of improved algorithms are presented in this paper. They are the improved DA algorithms， respectively based on LUT decomposition， OBC coding and two?way selector. They improved the speed of signal processing and reduced the system complexity. The comprehensive analysis， comparison and simulation for the improved DA algorithms applied to FIR filter are carried out. The results of simulation are correct and meet the design requirements.

Keywords： DA algorithm； FIR filter； LUT decomposition； OBC coding； two?way selector

数字滤波器是很多数字信号处理系统的基本单元，它们广泛的应用于通信、信号处理、图像处理、模式识别等很多领域。目前有多种实现FIR滤波器的方法，诸如使用DSP芯片、专用集成电路ASIC以及FPGA等，利用DSP来实现将会受限于运行速度以及较漫长的开发时间，ASIC将会受限于开发周期、成本以及通用性等问题，而FPGA的实现将会平衡这些因素，由于其开发周期短、实现方式容易、通用性强等特点，在很多领域都有着广泛的应用，并且发展潜力巨大。

FIR滤波器的主要的设计方法就是利用乘累加来实现。这个方法的实现主要有两种方式，一种是直接乘加的结构，N阶的FIR要完成N次乘法和N-1次加法操作，这种结构将会消耗大量的硬件资源和面积；另一种则是利用DA算法来实现，它将乘累加的计算形式转换为对查找表的寻址以及移位求和来实现，这种解决办法基于FPGA的查找表结构并且可以显著提高系统的运行效率，但是在减少乘法器使用的同时会增加大量LUT的使用，同样是一种面积换速度思想的体现[1]。

为了达到更高的运行速度，优化系统资源消耗，目前对FIR滤波器算法以及DA算法的改进有很多方法，包括部分串行结构、分割查找表、OBC编码、多路选择分解、CSD编码等。此外对于FIR滤波的运行效率和资源优化还可以通过使用流水线、状态控制机等方式来满足。本文分别介绍了DA算法、基于查找表分割的DA算法、基于OBC编码的DA算法、基于多路选择的分解算法，并在ISE中进行Verilog硬件代码的编写，并编写Testbench进行波形仿真，最后与传统的FIR滤波器算法进行了性能、资源以及实时性处理的比较和分析。

1 DA算法简介

分布式算法是一种应用广泛的FIR滤波器设计方法，主要基于查找表寻址来实现乘累加。分布式算法在完成乘加功能时是通过将各输入数据每一比特位对LUT进行寻址，LUT本质上就是一个RAM。目前FPGA中多使用4输入的LUT，即为四位地址线，所以每一个LUT可以看成一个有4位地址线的16×1的RAM。如表1所示，当用户通过原理图或HDL语言描述了一个逻辑电路以后，并计算好逻辑电路所有可能的结果，并把结果事先写入RAM，这样，每输入一个信号进行逻辑运算就等于输入一个地址进行查表，找出地址对应的内容，然后输出即可。

图1 实际逻辑与LUT实现方式对比

因此，LUT中需要预先存储FIR所有系数的所有可能组合之和，单个LUT的结构则需要构建[2N，]N为系数个数。每一次输入数据得到部分积后，再对各部分积进行累加得到最终结果。设[wi]是滤波器设计的系数，[xi（n）]是变量，可以看作是n时刻的第i个采样输入数据，y（n）代表n时刻的系统响应。那么它们的内积为：

[y（n）=i=0N-1wixi（n）] （1）

用二进制补码来表示输入数据[xi（n）]：

[xi=-xi，m-1+j=0m-1xi，m-1-j2-j] （2）

式中[xi，m-1]是[xi]的最高位，也就是符号位。将式（2）代入式（1）可得：

[y（n）=i=0N-1wi[-xi，m-1+j=0m-1xi，m-1-j2-j] =i=0N-1j=0m-1wixi，m-1-j2-j-i=0N-1wixi，m-1] （3）

因为[xi，m-1-j]的值只有两种可能性：1和0，所以[i=0N-1wixi，m-1-j]的计算结果有[2N]个不同的结果，单个LUT存储下所有[i=0N-1wixi，m-1-j]的可能结果，并且利用来自位移存储器[xi，m-1-j]作为LUT的地址信号从LUT中取出每一个比特位与系数的乘积。因此y（n）的值可以通过不断的移位和累加操作得到[2]。四个系数的基于LUT的DA算法结构如图2所示。

图2 DA算法基本结构

以上简要介绍了DA算法的基本原理，就是实现方式而言，分布式算法又可以分为并行方式、串行方式和串并结合的方式。并行方式首先要建立一个n×m的输入缓冲阵列，将数据读入，并对其进行排列，用所有n个输入数据的相同位对分布式查找表进行寻址，全并行方式实现需要消耗大量的分布式查找表，将会消耗很多的系统资源，但是可以很容易采用流水线方式来实现，所以可以得到很高的运算速度，它是一种资源换取效率的方法[3]。如图3所示。

图3 并行方式实现DA算法

串行方式只使用一个分布式查找表，先从最低位开始处理，用所有的n个输入变量的最低位对分布式查找表进行寻址，得到部分和后右移一位，放入寄存器中，与此同时，n个输入变量的次低位已经开始对分布式查找表进行二次寻址，等得到另一个部分和，并将其同样右移一位，与前一个部分和相加，重复以上步骤，直至得到最终的和，并用前面累加的结果减去符号位的部分和。与全并行方式相比，速度降低了很多，但是消耗的系统资源较少，设计思想简单，是一种效率换资源的方法。图2所示的即为串行形式。串并结合的方式则是对前面两种方式的平衡。

2 DA算法的改进

当滤波器阶数较小的时候，DA算法的查找表规模对资源的消耗可以接受，但是随着滤波器阶数的增加，查找表的规模会随着滤波器阶数的增大而呈指数增长，如果还是使用传统的DA算法来实现FIR，其资源将会消耗巨大，所以在高阶滤波器的设计中必须对DA算法进行改进。

为了缩小LUT，对LUT的地址线的数量进行分割，可以将规模较大的LUT分割为一些规模较小的LUT，由于fir滤波器是线性滤波器，因此低阶滤波器的输出可以相加，并且由此实现一个高阶滤波器的输出。如果再额外的加上流水线寄存器，这一结构的改变不仅不会降低运行速度，而且可以极大的减小设计规模。

如图4所示，实现一个4N的DA设计需要3个辅助的加法器，LUT表格的规模从1个[B×24N]的查找表减低到4个[B×2N]的查找表，查找表规模[4]减小到了原来的[14]。图4即为对查找表的分割，每一级加法器前还可以加流水线，缩短延时路径，提高时钟频率和数据吞吐率。

图4 基于查找表分割的DA算法

OBC编码即偏移二进制编码，基本原理即在分布算法中，将输入数据通过OBC编码由{0，1}映射到{1，-1}，使得ROM表的上下两部分具有镜像对称性关系，利用这种对称性可以将ROM表的大小从原来的压[2N]缩到[2N-1]，即压缩一半[5]。下面来推导基于OBC编码的DA算法：输入数据可以表示为 ：

[xi=12[xi-（-xi）]] （4）

式中：[-xi]可以表示为式（5）：

[-x1，m-1+j=0m-1x1，m-1-j2-j+2-（m-1）] （5）

将式（5）和式（2）代入式（4）可得：[xi=12[xi-（-xi）] =12[-xi，m-1+j=0m-1xi，m-1-j2-j+xi，m-1-j=0m-1xi，m-1-j2-j-2-（m-1）] =12[-（xi，m-1-xi，m-1）+j=0m-1（xi，m-1-j-xi，m-1-j）2-j-2-（m-1）]] （6）

为了让式子更简洁，将两部分整合为一个式子，定义[di，j]，其取值范围为[-1，1]。

[di，j=xi，j-xi，j， j≠m-1-（xi，m-1-xi，m-1）， j=m-1] （7）

所以得到：

[xi=12j=0m-1di，m-1-j2-j+2-（m-1）] （8）

所以：

[y=j=0m-1i=0N-112widi，m-1-j2-j-12i=0N-1wi2-（m-1）] （9）

为了让式子更简洁，再次定义[Cj=i=0N-112widi，j]，[Cex=i=0N-112wi]，所以输出数据可以写成：

[y=j=0m-1Cj2-j-Cex2-（m-1）] （10）

基于OBC查找表的LUT表如图5所示，优化后的OBC查找表如图6所示。

图5 基于OBC查找表的LUT表

图6 优化后的OBC查找表

可以观察到LUT的系数组合成镜像，可以通过对[x0j]的控制来减小LUT的规模，当[x0j]=0时，其他阶数相同比特位上的数据与其异或后的值不变；当[x0j=1]时，其他阶数相同比特位上的数据异或后的值将取反[6]。S1为最高位标志位，当S1=1时，LUT的输出取反，当S1=0时，LUT表的值不变。所以LUT表的最终输出由[x0j]和S1共同决定；S2双向选择器控制着输入移位寄存器的方向和[Cex]。上述原理结构如图7所示。

最后要介绍的方法的核心思想就是使用多个双向选择器，利用系数的对称性逐步代替掉LUT。该结构的推导如式（11）所示：

[ LUT（bk-1，bk-2，…，b1，b0）=LUT（bk-2，…，b1，b0）+wk-1，0= LUT（bk-3，...，b1，b0）+wk-1，0+wk-2，0=…= wk-1，0+wk-2，0+…+w0，0]

从式（11）可以看出，该算法就是把寄存器的输出的最高位不断反复的从LUT分离出来，由一个双向选择器和一个全加器来代替这部分LUT，从而达到减小LUT的目的，如图8所示；然后再次通过使用选择开关逐步替换掉次高位，再次减小LUT的容量，在对LUT进行反复的简化之后，原来LUT结构被双向选择器和加法器完全代替掉，最后得到不包含LUT的DA算法结构[7]，如图9所示。

图7 基于OBC编码的DA算法的实现

图8 最高位被替换掉的LUT

3 各算法实现比较和性能分析

根据项目需求，该滤波器主要应用于基站中频处理模块中，FIR滤波器放置于低采样率的一端，并完成多个窄带子载波的整形滤波，用于补偿前端滤波器滤波特性的不足，同时完成一定倍数的插值（抽取）滤波。由于该滤波器设计抽取插值倍数很高，通带频率也只有十几kHz，此外，该模块用于多个子载波的处理，因此对资源占用的要求也非常苛刻。综上所述，为了满足通带的性能指标以及尽量减少资源消耗的要求，本文需要设计一个基于DA算法的120阶FIR滤波器才能满足参数要求。首先使用FDATool导出120阶，定点数据类型为（16，-2，18）的FIR滤波器系数，并全部转换为16进制数，使用Verilog进行代码编写，在ISE环境下分别综合仿真以上几种算法。

图9 改进的最终DA结构

得到资源消耗如表1所示。

表1 各算法资源消耗对比

从表1的资源分析可以看出，并行FIR滤波器主要通过大量乘法器来并行处理数据，消耗大量逻辑资源，但是处理速度最快；串行FIR滤波器复用单个乘法器来完成120次乘法运算，输入一个数据需要8个时钟周期，输出一个数据需要120个时钟周期，快慢时钟相差120倍，但是满足了15倍下采样的时钟需求，处理速度最慢但消耗LUT资源最少；部分串行结构平衡了二者的利弊，通过对时序的控制复用了8个乘法器，但是依然需要消耗乘法器资源；DA算法完全不在使用乘法器资源，但是会消耗大量的LUT资源，处理速度处于中等水平；LUT分解将大规模的查找表分割为了多个小规模的查找表，增加了流水线，处理速度要快于传统的DA算法，而且还减少了LUT的资源消耗；基于双向选择器的改进算法进一步减小了查找表消耗，但是却增加了寄存器的使用，处理速度趋于传统的DA算法和LUT分解改进算法之间。如图10～图13所示。

在有相同控制信号的Testbench的仿真下，对比各波形传输延迟可以看出，各算法的处理速度大致相互关系为：

全并行>DA改进（LUT分解）≥DA分解（双向选择器）>传统DA算法>全串行。

图10 并行FIR滤波器

图11 串行FIR滤波器

图12 DA算法的FIR滤波器

图13 改进的DA算法的FIR滤波器

4 结 论

通过对FIR滤波器传统算法、DA算法及其改进的算法进行比较，当FPGA乘法器资源充足的情况下及滤波器阶数较低的情况下，使用传统算法比较理想，实现起来也较为容易；而本文提到的三种改进的DA算法很适用于在高阶FIR滤波器的设计情况，基于OBC编码的DA算法可以减少一半的LUT使用；在滤波器阶数较大时（16阶以上），LUT规模将会呈指数增加，基于查找表分解的改进算法可以从很大程度上减小LUT的规模，对而基于选择器的DA算法可以完全不再占用更多的LUT和乘法器，可以节省LUT的资源到达50%以上，显著降低了系统的复杂程度并提高了运行的速度。三种算法在资源紧缺和滤波器阶数很高的情况下还可以结合使用，再加上流水线寄存器，可以在保证资源消耗不多的情况下，整合资源利用效率，提高整个信号处理的速度，减少传输延迟，减小系统复杂度，因此改进后的算法将会优于传统算法。目前，改进DA算法的FIR滤波器已经应用于系统设计中。

参考文献

[1] 田耕.无线通信FPGA设计[M].北京：电子工业出版社，2007.

[2] 程佩青.数字信号处理教程[M].北京：清华大学出版社，2010.

[3] 刘朋全.基于FPGA的FIR数字滤波器的设计与实现[D].西安：西北工业大学，2006.

[4] 孙友军.基于FPGA的FIR数字滤波器算法研究与设计实现[D].北京：冶金自动化研究设计院，2010.

[5] 顾文奕.FIR数字滤波器的优化与验证[J].电子测量技术，2008（5）：183?189.

[6] GUO Rui， DEBRUNNER L S. A novel adaptive filter implementation scheme using distributed arithmetic [C]// Proceedings of the Forty Fifth Asilomar Conference on Signals， Systems and Computers. Pacific Grove， CA： [s.n.]， 2011： 160?164.

[7] YOO Heejong， ANDERSIN D V. Hardware?efficient distributed arithmetic architecture for high?order digital filters [C]// Proceedings of IEEE International Conference on Acoustics， Speech， and Signal Processing. [S.l.]： IEEE. 2005：125?128.