文献标识码: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=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所示。
图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×21+1
assign x5={x_in,2′b00}+ x_in;//5=1×22+1
assign x7={x_in,3′b000}- x_in;//7=1×23-1
assign x11={x_in,3′b000}+ x3;//11=1×23+3
assign x13={x3,2′b00}+ x_in;//13=3×22+1
assign x47={x3,4′b0000}- x_in;//47=3×24-1
assign x89={x11,3′b000}+ x_in;//89=11×23+1
assign x91={x3,5′b00000}-x5;//91=3×25-5
assign x99={x3,5′b00000}+x3;//99=3×25+3
assign x193={x3,6′b000000}+ x_in;//193=3×26+1
assign x223={x7,5′b00000}- x_in;//223=7×25-1
assign x229={x7,5′b00000}+x5;//229=7×25+5
assign x241={x3,4′b0000}+x193;//241=3×24+193
assign x273={x91,1′b0}+x91;//273=91×21+91
assign x343={x89,2′b00}-x13;//343=89×22-13
assign x421={x13,5′b00000}+x5;//421=13×25+5
assign x587={x91,2′b00}+x223;//587=91×22+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.