基于RAG-n算法的低成本FIR滤波器实现

徐 红1，叶 丰2，黄朝耿3

（1.浙江工业大学 信息工程学院，浙江 杭州310023；

2.杭州国芯科技股份有限公司，浙江 杭州310012；3.浙江财经大学 信息学院，浙江 杭州310018）

摘 要：基于FIR数字滤波器多常数乘法的图表示法，利用MATLAB对RAG-n算法进行了实现。通过仿真该算法在大多数情况下都可以高效地解决加法器优化问题，有效降低了FIR滤波器常系数乘法的复杂度。在FPGA上用Verilog HDL语言对优化实例进行了实现，其综合结果表明，该方法可以有效减少逻辑单元的消耗，适用于低成本数字系统设计。

中图分类号：TN713

文献标识码：A

DOI：10.16157/j.issn.0258-7998.2016.05.009

中文引用格式： 徐红，叶丰，黄朝耿. 基于RAG-n算法的低成本FIR滤波器实现[J].电子技术应用，2016，42(5)：32-35.

英文引用格式：Xu Hong，Ye Feng，Huang Chaogeng. Implementation of low-cost FIR digital filters based on RAG-n algorithm[J].Application of Electronic Technique，2016，42(5)：32-35.

0 引言

有限冲激响应（FIR）滤波器具有能保证绝对稳定和线性相位等优点，在数字系统设计中应用广泛。对于某一应用需求，FIR滤波器相对于无限冲激响应（IIR）滤波器往往需要更长的阶数，从而在实现时需要更多的乘法和延时等操作，因此如何降低FIR滤波器的硬件实现成本一直具有实际的研究意义。近几年一些研究者注重在确定参数阶段就将最后的硬件实现成本（主要是加法器的个数）考虑进去，即在实现成本和频率响应两方面约束下进行滤波器的优化设计。这些方法往往算法复杂，运行时间长，且不能保证得到最优结果，因此进行实际应用的技术人员很难有效利用这些方法。更普遍的情况是对应具体的应用需求，应用MATLAB等数学工具已经设计出满足需求的有限字长固定系数FIR滤波器，其实现时的硬件成本是很多应用工程师关心的问题。因此本文着眼于固定系数的FIR滤波器实现问题，利用高效的RAG-n算法，降低加法器个数，从而有效降低FIR滤波器的硬件实现成本。

1 FIR滤波器多常数乘法的图表示法

1.1 多常数乘法

图1为FIR滤波器的转置型结构。

如图1所示，输入信号首先与滤波器的各个常系数相乘后被送入延时单元，这种操作通常称为多常数乘法（Multiple Constants Multiplication，MCM）问题。常数乘法可以通过无乘法（multiplierless）技术来实现，即用移位寄存器和加（减）法器代替乘法器。因此，加法器可以进一步分为乘法模块（Multiplier Block，MB）的加法器和延迟单元的加法器（Structural Adders，SA）。一旦给定滤波器阶数，延时单元和SA的数量就相对固定，因此，FIR滤波器实现复杂度主要决定于MB。

1.2 多常数乘法的图表示法

以常系数集合[1，7，16，21，33]为例，要实现与同一个输入信号的乘法，可以用一个有向无环图来集中产生所有系数乘法^[1]，如图2所示。

从图2我们看出：

(1)已经产生的节点（Fundamentals）可以用来产生还未产生的系数，例如21可以通过7产生，只要再增加一个加法器就可以，否则单独产生21需要两个加法器：21=2⁴+2²+1。因此高效的图表示法可以减少整个乘法模块总的加法器个数。

(2)不同的图表示方式需要的加法器个数可能不同，图2(a)用了4个加法器，而图2(b)只用了3个加法器。

2 RAG-n算法

RAG-n算法是一种非常高效的多常数乘法图表示法，图2(b)的结果就是由它得到的。RAG-n算法包含两部分：最优部分和启发部分[1]。在算法执行过程中需要用到两个查找表：第一个表对应系数单独实现时需要的最少加法器个数（即单个系数的最优代价），第二个表对应系数最优代价实现的具体方法，可能不止一种，如3=2+1或是3=4-1。

2.1 最优部分算法流程

“incomplete”集合初始为空；“graph”集合初始元素只有“1”；cost表示加法器代价，算法步骤如下。

(1)将所有系数通过除以2（或-2）的操作得到对应的正奇数，其结果存入“incomplete”集合；

(2)查表得到所有单个系数的最优代价；

(3)去掉“incomplete”集合中代价为零的系数以及重复的系数；

(4)将“incomplete”集合中cost=1的系数移除并存入“graph”集合，例如7=8-1；

(5)计算在有限字长范围内“graph”集合元素能产生的所有cost=0的正整数，存入“cost0”集合，然后进行两两相加（或减），如果得到了“incomplete”集合中的某一个系数，则将该系数从“incomplete”集合移除存入“graph”集合。

(6)重复步骤(5)，直到没有系数添加到“graph”集合。

在上述步骤中，如果“incomplete”集合为空，即所有的系数都已经被综合，则算法结束。

例如，原始系数集合=[1，7，16，-21，33，42，83]，算法执行过程如下：

(1)“incomplete”集合=[1，7，1，21，33，21，83]；

(2)[1，7，1，21，33，21，83]的代价分别为：[0，1，0，2，1，2，3]；

(3)“incomplete”集合=[7，21，33，83]；

(4)“incomplete”集合=[21，83]，“graph”集合=[1，7，33]；

(5)第一次执行：“cost0”集合=[1，2，4，…；7，14，28，…；33，66，132，…]，21=14+7，所以“incomplete”集合=[83]，“graph”集合=[1，7，21，33]；

(6)第二次执行：“cost0”集合=[1，2，4，…；7，14，28，…；21，42，84，…；33，66，132，…]，83=84-1，所以“incomplete”集合=，“graph”集合=[1，7，21，33，83]，算法结束。

2.2 启发部分算法流程

延续2.1节流程，以下第(7)～(10)步骤为启发部分算法流程。

(7)如果有系数没有在最优部分被综合，则是因为已有节点只通过一个加法器得不到该系数，表明该系数与现有节点的加法距离大于等于2，即distance≥2。首先搜索两种distance=2的情况：

①该系数和已有节点值的差值是否存在cost=1的数；

②该系数和任意两个节点值的差值是否存在cost=0的数；

以上两种情况都可以通过增加两个加法器得到该系数。

例如，若原始系数集合=[1，7，16，-21，33，42，83，341]，341在最优部分不能被综合，但是341-21=320，320是一个cost=1的数，则341=21+(1+4)×26；若原始系数集合=[1，7，16，-21，33，42，83，283]，283在最优部分不能被综合，但是283-(33+21)/2=256，256是一个cost=0的数，则283=(33+21)/2+256。

(8)重复执行步骤(6)和步骤(7)，直到没有系数再被综合。

(9)如果达到这一步，说明存在与已有节点distance>2的系数或是步骤(7)中没有被搜索到distance=2的情况，这时需要加入一些节点来增大搜索范围，一般以单个系数cost值从小到大的顺序产生，这个过程具有随意性。

(10)重复执行步骤(6)至步骤(9)，直到所有的系数都被综合。

如果所有的系数都能在最优部分被综合，则得到的结果可以保证总的加法器个数是最少的，否则，剩下的系数将在启发部分被综合，不能保证结果最优。启发部分计算量大、计算时间长且具有随意性。为了增强算法的实用性，我们通过MATLAB软件设计实现了RAG-n算法的步骤(1)~步骤(8)，并对综合系数占总系数的百分比进行了仿真，如图3和图4所示。滤波器系数的数目从10到80间隔10取值，字长从6到12间隔2取值，每个点随机产生500组滤波器系数用RAG-n算法进行优化，最后将百分比结果进行统计平均，得到一个仿真点的值，具体数值如表1所示。

图4和表1的仿真结果表明，一般情况下步骤(1)~步骤(8)都能够综合大部分或者全部的系数，42.5%的结果没有太多实际意义，因为在字长比较大的时候，阶数通常比较高。因此在实际应用中，采用最优部分加上distance=2的启发部分可以解决绝大多数加法器优化问题，且运行效率较高。

3 实现举例

以文献[2]中60阶滤波器S2为例，对给定系数通过MATLAB编写的RAG-n算法进行加法器优化，然后采用Verilog HDL语言进行滤波器的RTL级描述，并在FPGA上进行综合比较。S2滤波器的通带边界频率为0.042π，阻带边界频率为0.14π，通带波动小于0.012，阻带波动小于0.001。具体系数见表2。

以上系数正奇数化并且去掉cost=0的项和重复项后，需要RAG-n算法优化的系数集合从小到大排列为：[3，5，7，11，13，47，89，91，99，193，223，229，241，273，343，421，587]，共有17个不同的奇数，所需加法器的下限为17，通过RAG-n算法优化得到的加法器个数也是17个，而文献[2]中通过子项共享方法得到的加法器是19个。通过Verilog HDL语言实现时对应的语句如下，x_in为滤波器输入信号：

assign x3={x_in,1′b0}+ x_in；//3=1×2¹+1

assign x5={x_in,2′b00}+ x_in；//5=1×2²+1

assign x7={x_in,3′b000}- x_in；//7=1×2³-1

assign x11={x_in,3′b000}+ x3；//11=1×2³+3

assign x13={x3,2′b00}+ x_in；//13=3×2²+1

assign x47={x3,4′b0000}- x_in；//47=3×2⁴-1

assign x89={x11,3′b000}+ x_in；//89=11×2³+1

assign x91={x3,5′b00000}-x5；//91=3×2⁵-5

assign x99={x3,5′b00000}+x3；//99=3×2⁵+3

assign x193={x3,6′b000000}+ x_in；//193=3×2⁶+1

assign x223={x7,5′b00000}- x_in；//223=7×2⁵-1

assign x229={x7,5′b00000}+x5；//229=7×2⁵+5

assign x241={x3,4′b0000}+x193；//241=3×2⁴+193

assign x273={x91,1′b0}+x91；//273=91×2¹+91

assign x343={x89,2′b00}-x13；//343=89×2²-13

assign x421={x13,5′b00000}+x5；//421=13×2⁵+5

assign x587={x91,2′b00}+x223；//587=91×2²+223

以上结果通过移位操作就可以得到原系数h(n)与输入信号x_in的多常系数乘法。

4 硬件综合结果

FPGA硬件资源的消耗可以通过综合后逻辑单元（Logic Element，LE）的数量来衡量。应用3种不同的方法对上例进行实现比较：

(1)直接实现，即输入与滤波器系数h(n)直接相乘实现；

(2)子项共享实现，即根据文献[2]中的子项共享结果实现^[3]；

(3)RAG-n算法优化实现。

我们分别选择Cyclone系列的EP1C12Q240C8和APEX20KE系列的 EP20K600EBC652-3两种型号的FPGA，综合工具选用Quartus II，结果如表3。

从表3可以看出，RAG-n算法由于加法器个数的减少节省了FIR滤波器FPGA硬件实现时的成本。

5 结论

本文通过MATLAB编程实现了RAG-n算法的最优部分和distance=2的启发部分，并对算法的优化实例用硬件描述语言在FPGA上进行了实现。RAG-n算法能有效降低加法器个数，从而有效节省FIR滤波器的硬件资源消耗，对FIR滤波器的低成本设计实现具有应用意义。

参考文献

[1] DEMPSTER A G，MACLEOD M D.Use of minimum-adder multiplier blocks in FIR digital filters.Circuits and Systems II：Analog and Digital Signal Processing[J].IEEE Transactions on，1995，42(9)：569-577.

[2] YU Y J，LIM Y C.Design of linear phase FIR filters in subexpression space using mixed integer linear programming[J].IEEE Trans.Circuits Syst.I，Reg.Papers，2007，54(10)：2330-2338.

[3] 徐红，叶丰，黄朝耿.基于子项空间技术的低复杂度FIR滤波器实现[J].电子技术应用，2014，40(6)；33-35.