基于基于RAG-n算法的低成本算法的低成本FIR滤波器实现滤波器实现
基于FIR数字滤波器多常数乘法的图表示法,利用MATLAB对RAG-n算法进行了实现。通过仿真该算法在大多数
情况下都可以高效地解决加法器优化问题,有效降低了FIR滤波器常系数乘法的复杂度。在FPGA上用Verilog
HDL语言对优化实例进行了实现,其综合结果表明,该方法可以有效减少逻辑单元的消耗,适用于低成本数字
系统设计。
0 引言引言
有限冲激响应(FIR)滤波器具有能保证绝对稳定和线性相位等优点,在数字系统设计中应用广泛。对于某一应用需
求,FIR滤波器相对于无限冲激响应(IIR)滤波器往往需要更长的阶数,从而在实现时需要更多的乘法和延时等操作,因此如
何降低FIR滤波器的硬件实现成本一直具有实际的研究意义。近几年一些研究者注重在确定参数阶段就将最后的硬件实现成本
(主要是加法器的个数)考虑进去,即在实现成本和频率响应两方面约束下进行滤波器的优化设计。这些方法往往算法复杂,
运行时间长,且不能保证得到最优结果,因此进行实际应用的技术人员很难有效利用这些方法。更普遍的情况是对应具体的应
用需求,应用MATLAB等数学工具已经设计出满足需求的有限字长固定系数FIR滤波器,其实现时的硬件成本是很多应用工程
师关心的问题。因此本文着眼于固定系数的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
4
+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表示加法器代价,算法步骤如下。