关键词：FIR滤波器；分布式算法；FPGA；查找表

FIR介绍

在许多信息处理过程中，如对信号的过滤、检测、预测等，都要广泛地用到滤波器，数字滤波器是数字信号处理中使用最广泛的一种方法，实现方法主要有IIR滤波器（无限冲激响应数字滤波器）和FIR滤波器（有限冲激响应数字滤波器）两种，其中，IIR滤波器需要执行无限数量卷积，能得到较好的幅度特性，其相位特性是非线性的；而FIR滤波器由有限个采样值组成，具有严格的线性相位特性。由于在数据通讯、语音信号处理、图像处理等传输过程中不能有明显的相位失真，而FIR滤波器在满足一定对称条件下可以实现IIR滤波器难以实现的线性相位，因而得到广泛应用。

FIR滤波器的数学表达式可用K阶内积来表示：

公式（略）

其中：

K：FIR滤波器的抽头数；

h(k)：第k级抽头系数（单位脉冲响应）；

x(n-k)：延时k个抽头的输入信号。

FIR滤波器的单位脉冲响应h(k)均为实数，在幅度上只要满足下列两个条件之一，就能构成线性相位FIR滤波器。式（2）称为第一类线性相位的幅度条件（偶对称），式（3）称为第二类线性相位的幅度条件（奇对称）。

(k)=h(K-1-k) （2）

h(k)=-h(K-1-k) （3）

FIR滤波器最基本的结构是直接型，如图1所示。可以看出，FIR滤波器是由一个"抽头延迟线"的加法器和乘法器的集合构成，每个乘法器的操作数就是一个FIR系数。对每次采样y(n)都要进行K次连续的乘法和（K-1）次加法操作，能够提供这种算法性能的高性能硬件平台对大多数信号处理设计者来说都有很大的吸引力。

在滤波运算中，目前实现可采用两种方法：软件实现和硬件实现。软件实现是利用计算机把滤波器所要完成的运算编成程序通过计算机来执行。国内外的研究机构、公司已经推出了不同语言的信号处理软件包。但软件实现方法较慢，难以实时处理，主要用于教学和科研。硬件主要采用MCU（单片机）、DSP（数字信号处理器）和ASIC（专用集成电路）来实现。其中，单片机速度较慢；ASIC虽然性能良好，但灵活性差，只能实现一些特殊的功能；软件编程的DSP是一个典型的执行连续数学运算处理的可配置的信号处理硬件，目前应用较广。但是，DSP的串行指令执行方式，使其工作速度和效率大打折扣。因此，在一些高速应用中，系统性能不断增长，而DSP性能的提高却落后于需求的增长，从而产生了对新的数字信号处理实现方式的需求。

图1　直接型FIR滤波器结构图（略）


DA算法介绍

分布式算法（Distributed Arithmetic, DA）早在1973年就已经被Croisier提出来，由Peled和Liu进行了推广工作。直到现场可编程门阵列(Field Programmable Gate Array, FPGA)的查找表（Look Up Table, LUT）结构的出现，这种算法才重新受到重视，其主要原理如下。

为了分析简单起见，将FIR滤波器的表达式（1）改写为：

公式（略）

公式（略）

其中，x_{ab}表示x_{k}的第b位，x_{k}即x的第k次采样，则y可表示为：

公式（略）

改变式(6)的求和次序，结果可表示为：

公式（略）

可以看出，分布式算法是一种以实现乘加运算为目的的运算方法，与传统的乘累加运算不同在于执行部分积运算的先后顺序不同，这个过程可用图2的结构来实现。该算法可以利用一个查找表（LUT）实现映射，即用一个2K字宽（即2K行）、预先编好程序的LUT接受一个K位输入向量xb＝[x0b, x1b,…, x(K-1)b]的映射，经查找表的查找后直接输出部分积table_out(b)=\sum_{k=0}^{K-1}h_{k} x_{kb} 。算法中的乘以位权2b可以通过图中的寄存器和累加器完成。这个过程可以用递规表达式表示成式（8），在执行了B次查找和B次累加后输出结果。

公式（略）

图2　DA算法结构图（略）

上面所介绍的是输入序列为无符号数的DA算法，在实际使用中，对于有符号数，一般用补码来表示，最高有效位是符号位用来区分正数和负数的。只要将图2中的累加器修改为带有加减控制的累加器即可，当符号位是“0”时，最高位进行加运算，反之进行减运算。

DA算法的FPGA实现

FPGA的特点

DA算法的计算需要一系列的查表、加减法运算，FPGA是物理级编程结构的可编程逻辑器件，其基本结构由4输入的查找表构成，如Altera公司的FLEX10K器件中的基本逻辑单元（Logic Element, LE）包含一个4输入查找表，而且它的嵌入式阵列块（Embedded Array Block, EAB）是一个2048位的可配置RAM，可将其配置成只读模式，生成一个更大的查找表，相对于串行运算为主导的通用DSP芯片来说，FPGA的并行度和可扩展性都很好，逐渐成为构造可编程的高性能算法结构的新选择。

设计实现

下面以Altera公司的FLEX10K为例说明分布式算法FIR滤波器的设计方法。

设计指标及参数提取

设计指标

设计一个16阶的FIR滤波器，采样频率fS =2.5MHz，通带截止频率fC =200KHz，输入数据宽度8位，滤波器系数宽度16位，输出数据宽度20位。
参数提取

采用汉明窗（Hamming）设计，用Matlab仿真计算其单位取样响应

h(k)，并将其放大216倍，即乘65536后得到用二进制补码表示的h(k)

h(0)=h(15)=(-143)10=(FF71)16,h(1)=h(14)=(-53)10=(FFCB)16，

h(2)=h(13)=(353)10=(0161)16,h(3)=h(12)= (1548)10=(060C)16，

h(4)=h(11)=(3751)10=(0EA7)16，h(5)=h(10)=(6658)10=(1A02)16，

h(6)=h(9)=(9461)10=(24F5)16，h(7)=h(8)=(11191)10=(2BB7)16，

表分割法查找表的构成

如果滤波器的抽头数过多，那么查找表字宽为2K，查找表的规模随抽头数的增加成指数级增长，因此抽头数较多时用单个查找表是不能执行全字运算的，要想办法进行查找表的分割。本设计中，由于滤波器具有偶对称结构，可以将16阶降为8阶，但仍需构成8输入的查找表（字宽为28＝256）。我们可以从两个方面考虑进行查找表分割，一是减小查找表的规模；一是提高DA算法的速度。

为了缩小查找表的规模，可以将大LUT分割为一些小的LUT，由于FIR滤波器是线性滤波器，因此低阶滤波器输出可以相加，并且由此定义一个高阶滤波器的输出。我们可以把8输入的查找表分割成两个并行的4输入查找表，图3所示。依此类推，可以将更大LUT分割为多个小LUT，如果加上流水线，这一结构的改变并不会降低速度，却可以大大减小设计规模，本设计采用这种方法。

图3　简化规模的DA算法结构图（略）

另外，也可以采用另一种方法提高计算速度，就是将输入字段分割成K个子字段，然后并行处理这些子字段，这种完全流水的并行结构如图4所示。计算速度将随着表的分割多少而翻多少番，但这一方法需要K倍的查找表，从而导致存储需求大和成本的直线上升。在实际中可以将这两种方法结合起来，兼顾系统的资源和性能，以达到最优。

图4　速度最优的DA算法结构图（略）

总体结构

根据系统性能指标，设计该系统的总体结构如图5，其中：x(n)是输入序列，y(n)是输出序列，clk0是采样时钟，clk是算法时钟，reset是复位信号。

各模块的主要功能是：

图5　FIR滤波器的总体结构框图（略）

移位寄存器：将输入序列x(n)通过移位寄存器改为并行输入；

优化模块：根据FIR滤波器h(n)的对称特性将滤波器降阶，完成输入求和x(k)+x(K-1-k)，对于本例中的16抽头滤波器，即完成x(0)+x(15)，x(1)+x(14)，……，x(7)+x(8)；

乘法模块：用查找表的方法实现乘法运算。将8输入查找表分割成两个并行的4输入查找表分别运算，减小查找表的规模；

加法器：最后将2个DA算法的结果相加，得到输出y(n)。

设计结果

本文设计的滤波器采用EPF10K30RC240-3器件，在QuartusII下进行仿真，设输入序列为无符号数x(n)＝[0，2，0，0，4，1，0，3，2，1，1，4，0，1，1，2]，仿真输出依次为y(n)=[-286，-106，706，2524，……，-286]，波形如图6所示。图中，FFEE2为-286的二进制补码，其他数据相同。表1是输出序列y(n)仿真结果与Matlab计算值的对比（数据放大了65536倍），结果误差<4‰，主要是由于有限精度算法引起的。通过验证，系统运行速度53.76MHz，采样频率达3MHz，占用LC:617个，占全部资源的35%，达到了设计要求。

图6　系统功能仿真波形图（略）

表1：系统仿真结果与同Matlab计算值对照（略）


结束语

分布式算法是一种利用查找表将固定系数的乘累加转换为查表操作，本设计的FIR滤波器通过了电路验证，符合设计要求，现总结如下：

①采用4输入查找表进行分布式算法的设计，简化了传统的MAC设计；

②采用表分割法进行LUT分割，缩小了LUT规模，当实现更高阶的FIR时，可综合采用两种分割方法；

③LUT的参数独立于滤波器的结构，有较强的通用性，适于模块化设计；

④利用VHDL设计，可重复配置FPGA，降低成本，开发周期较短，系统易于维护和扩展。

长期以来，FPGA一直被用于逻辑或时序控制上，很少用于信号处理方面，主要原因是FPGA中没有直接的硬件乘法器。通过分布式算法，对于固定系数的乘法这个问题得到了很好的解决。而且由FPGA代替ASIC和DSP作为前端数字信号处理的运算，在规模、重量和功耗方面都有所降低，而且吞吐量更高，开发成本进一步缩短。可以预见，在未来，大量的FPGA将会统治更多的如FIR滤波、CORDIC算法或FFT等的前端应用。