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

徐　红，叶　丰，黄朝耿

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

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

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

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

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

FIR数字滤波器；乘法器的图表示法；RAG-n算法；FPGA

0　引言

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

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

1.1多常数乘法

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

图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　多常系数乘法的图表示

从图2我们看出：

(1)已经产生的节点（Fundamentals）可以用来产生还未产生的系数，例如21可以通过7产生，只要再增加一个加法器就可以，否则单独产生21需要两个加法器：21=24+22+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所示。

图3　步骤(1)～步骤(6)（即最优部分）综合系数的百分比曲线

图4　步骤(1)～步骤(8)综合系数的百分比曲线

表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。

表2　滤波器S2的系数，h(n)=h(59-n)，30≤n≤59；通带增益=10 945.336 1

以上系数正奇数化并且去掉 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为滤波器输入信号：

以上结果通过移位操作就可以得到原系数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　FPGA综合结果比较

从表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.

Implementation of low-cost FIR digital filters based on RAG-n algorithm

Xu Hong1，Ye Feng2，Huang Chaogeng3
（1.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China；2.Hangzhou Nationalchip Science&Technology Co.Ltd.，Hangzhou 310012，China；3.School of Information，Zhejiang University of Finance&Economics，Hangzhou 310018，China）

Based on graph representation of multiple constants multiplication,RAG-n algorithm is implemented by MATLAB.RAG-n algorithm can solve optimization problem of adder number in most cases efficiently,and reduce the complexity of FIR filter constant coefficient multiplication.The results of FPGA hardware synthesis show that this method can greatly reduce the number of logic elements applicable to low-cost design of digital systems.

FIR digital filter；graph representation of multipliers；n-dimensional reduced adder graph algorithm；FPGA

TN713

A

10.16157/j.issn.0258-7998.2016.05.009

浙江省自然科学基金（LY16F030057），国家科技支撑计划课题（2013BAF07B00）

2015-10-08)

徐红(1978-)，女，工学硕士，讲师，主要研究方向：数字滤波器设计、FPGA及 ASIC开发技术。

叶丰(1975-)，男，技术总监，主要研究方向：数字电视技术、集成电路设计。

中文引用格式：徐红，叶丰，黄朝耿.基于 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.