邱陈辉,李　锋,徐祖强

(1.浙江大学生物医学工程教育部重点实验室,杭州 310027;2.江苏科技大学电子信息学院,江苏 镇江 212003)



基于FPGA和符号LMS算法的自适应滤波器设计*

邱陈辉1,李锋2*,徐祖强2

(1.浙江大学生物医学工程教育部重点实验室,杭州 310027;2.江苏科技大学电子信息学院,江苏 镇江 212003)

摘要:为了减少实现基于FPGA和LMS算法的自适应滤波器过多消耗硬件资源的问题,提出了符号LMS算法,通过降低乘法运算的次数来提高自适应滤波器的运行速度,并使用流水线技术进行优化。软件仿真验证了符号LMS算法的可行性,硬件仿真证实了采用该算法和流水线技术的自适应滤波器的优越性。

关键词:数字信号处理;自适应滤波器;最小均方;符号最小均方;现场可编程门阵列;流水线

自适应滤波器在现代数字信号处理中的应用极为广泛,主要分成系统辨识、逆模型、预测和干扰消除4大类别[1]。对于实时性要求很高的场合,往往需要使用硬件设计自适应滤波器,并且自适应算法尽量简单、易实现[2]。基于现场可编程门阵列(FPGA)硬件和最小均方(LMS)自适应算法的自适应滤波器近年来被不断地研究和改进。

由于FPGA中嵌入了较多硬线乘法器和加减器,使用它们很容易实现乘累加(MAC)运算,故通常将采用LMS算法的自适应滤波器直接映射到FPGA芯片上。但这样消耗较多的硬件资源,也不能发挥FPGA并行处理的优势。故本文提出了利用符号LMS算法和流水线技术对上述自适应滤波器进行优化,从而减少嵌入式乘法器资源的消耗并且提高运行速度。

1　自适应滤波器算法

1.1LMS算法

设x(n)和w(n)分别表示自适应滤波器的输入信号和权值向量,定义

x(n)=[x(n),x(n-1),…,x(n-L+1)]T

w(n)=[w0(n),w1(n),…,wL-1(n)]T

则LMS算法的基本形式如下

滤波输出:

(1)

误差计算:

e(n)=d(n)-y(n)

(2)

权值更新:

w(n+1)=w(n)+μe(n)x(n)

(3)

其中y(n)是自适应滤波器的输出信号,d(n)是期望信号,e(n)表示误差信号,μ是收敛因子,L是自适应滤波器的阶数。因为LMS算法是严格顺序执行的,所以式(1)～式(3)的次序不能颠倒[3]。其模块图如图1所示。

图1　LMS算法的模块图

虽然LMS算法的推导过程涉及求梯度和微分,但是其最终形式只涉及乘法、加减和迭代3种运算,并且乘法运算量最多。而利用FPGA实现基于LMS算法的自适应滤波器时,硬件资源的消耗很大一部分来源于乘法运算。不管是利用FPGA中的基本逻辑单元LE(Logic Element)还是嵌入式乘法器模块实现乘法运算,基于硬件的乘法运算都将是高成本的,应尽可能地减少[4]。

1.2符号LMS算法

式(1)中的乘法是为了计算自适应均衡器的输出信号,不能删减。式(3)中的乘法是针对收敛因子μ、误差信号e(n)和输入矢量x(n)进行的,可以进行改进。针对一些特殊应用,e(n)和x(n)的乘积事实上无需两者都以全精度值参与计算,只取他们的符号进行运算即可[5]。

第1种方案是对e(n)取符号,利用正负号符号函数Signum(·)得 sign[e(n)],而x(n)保持全精度,这样两者相乘的结果就是x(n),要么是对x(n)取负值。第2种方案是对x(n)中的x(n)、x(n-1)、…、x(n-L+1)取符号,利用Signum(·)得sign[x(n)],此时两者的乘积要么就是e(n),要么就是对e(n)取负值。第3种方案是同时对e(n)和x(n)取符号,利用Signum(·)得sign[e(n)]和sign[x(n)],这样两者相乘的结果就是1或-1。这3种符号LMS算法方案的公式表示依次为

w(n+1)=w(n)+μsign[e(n)]x(n)

(4)

w(n+1)=w(n)+μe(n)sign[x(n)]

(5)

w(n+1)=w(n)+μsign[e(n)]sign[x(n)]

(6)

符号LMS算法其实是对LMS算法的一种改进,其模块图如图2所示,它可由随机梯度法推导而来,以均方误差E[|e(n)|2]为代价函数J(n),推导关键是对J(n)求梯度,然后对其权值w(n)进行自适应调整时,只考虑J(n)的梯度方向,忽略具体的梯度值。因此,牺牲输入信号或误差信号精度的符号LMS算法并不适用于所有的自适应系统[6],利用MATLAB对使用该算法的自适应滤波器进行前期的验证评估是十分必要的。

图2　符号LMS算法的模块图

假若μ的取值不是2的幂形式,那么第1、第2种方案节省的乘法器数量相同,而第3种方案节省的乘法器数量是它们的2倍。若将μ值设置为2的幂形式,与μ相乘可以利用移位运算代替[7],那么上述3种方案所节省的乘法器数量是相同的。但是针对自适应滤波器的具体应用场合,3种方案对自适应滤波器的稳定性、收敛速度的影响会有差异。

由文献[6]知第3种方案最受青睐,已被用作自适应差分脉冲编码调制传输的国际电信联盟标准,所以本文以它为例进行对比分析。图3给出了分别基于LMS算法和符号LMS算法的自适滤波器的均方误差曲线图,这里取L=8,μ=2-7。由图3可知采用符号LMS算法的自适应滤波器的均方误差收敛速度比采用LMS算法更快,并且更加趋近于零。这主要由于在每次迭代更新中,符号LMS算法进行的乘法计算量相对于LMS算法减少了一半。

图3　自适应滤波器的均方误差曲线

2　流水线技术

广义上讲,流水线技术就是将一个重复的过程分解为若干子过程,让每个子过程可以和其他的子过程同时进行,是一种并行处理技术。就FPGA而言,流水线技术是指将组合逻辑电路的延时路径进行系统性地分级,并且在各个分级之间插入寄存器来暂存中间数据。这样便缩短了信号在一个周期内通过组合逻辑电路的延时路径长度,从而提高了时钟频率。对于应用最广泛的同步时序电路而言,其处理速度就是指它的时钟频率。时钟频率越快,处理数据的时间间隔就越短,在单位时间内处理的数据量就越大,也就提高了处理速度[8]。

图4形象说明了流水线技术的基本原理,假设图中的组合逻辑电路具有较大的延时,于是将其分割成具有较小延时的组合逻辑电路1和2,并插入2个同步寄存器。这样组合逻辑电路1和2在同一时间内处理的信号就会不同,因为经过了寄存器的锁存。2个组合逻辑电路1和2就可以并行执行[9]。该图也说明了流水线技术实际上是以增加硬件资源的消耗来换取更高处理速度的。

图4　流水线技术基本原理图

在FPGA中使用流水线技术,需要的额外成本不多,因为每个LE本身就包含一个寄存器和寄存器链逻辑。提升基于FPGA的自适应滤波器的运行速度关键在于提高乘法器的处理速度。由文献[6]可知,对于FPGA中的一个N位×N位的乘法器,若想达到最高处理速度,那么需要的流水线级数是log2(N)。本文自适应滤波器输入信号的位宽设置成16位,故采用4级流水线时可以充分发挥流水线技术的速度优势。

3　FPGA实现

FPGA是通过采用可编程的查找表(LUT)结构来实现可编程逻辑的。LE是Cyclone系列FPGA芯片中最基本的可编程单元,主要由一个4输入的LUT、一个可编程的寄存器、进位链逻辑和寄存器链逻辑构成[10]。因此,我们通常使用 在同一时钟的驱动下 某信号通过源寄存器至目的寄存器的最短路径所消耗的最少时间(Tmin或者Fmax)来表示对信号的处理速度,使用设计所需LE的总数量来表示FPGA硬件资源的消耗情况[11-12]。

为了跟本文1.2节最后的MATLAB仿真实验保持一致,基于Altera公司CycloneⅢEP3C10U256C8FPGA芯片的自适应滤波器仍然设为8阶,收敛因子仍取2-7,系统时钟clk的频率设成数据输入频率的6倍,自适应算法分别采用LMS算法和符号LMS算法。使用超高速集成电路硬件描述语言(VHDL)进行对分别基于2种算法的自适应滤波器进行编程,主要包括初始化模块,信号输入模块,时钟分频模块,权值更新模块,误差计算模块,滤波输出模块。接着利用QuartusⅡ和ModelSim软件对它们分别进行编译、综合、适配、时序分析。设定x(n)、d(n)、e(n)和y(n)的二进制位宽分别是16位,其中x(n)和d(n)的取值是通过对本文1.2节利用MATLAB仿真时的x(n)和d(n)数据进行16位量化得到的。

图5是基于FPGA和LMS算法的自适应滤波器的ModelSim时序验证图,对该自适应滤波器进行VHDL编程时,没有使用流水线技术进行优化,系统时钟的最高频率是76.75MHz,总共消耗了32个嵌入式乘法器。详细的资源消耗情况如表1所示。图5中误差信号e的波形开始时抖动幅度较大,之后慢慢平缓,该设计达到了预期效果。

图5　基于LMS算法的自适应滤波器的时序波形图

图6是基于FPGA和符号LMS算法的自适应滤波器的ModelSim时序验证图,在VHDL编程时添加了4级流水线对该自适应滤波器进行优化,图6中误差信号el的波形开始时抖动幅度很大,随后渐趋平缓。和图5中的e波形相比,图6中el波形的抖动更小,这跟1.2节中的MATLAB仿真结果是完全一致的,因此本设计是正确的。表1也给出了该自适应滤波器的资源消耗情况和处理速度。

图6　基于LMS算法的自适应滤波器的时序波形图

表1基于2种算法的自适应滤波器的资源消耗和速度比较

算法LEsRegistersEmbeddedmultiplierFmax/MHzLMS141213213276．75符号LMS103793916123．93

由表1可知,基于LMS算法的自适应滤波器所消耗的LE和寄存器数量分别比基于符号LMS算法的多了375个和382个,并且前者所消耗的嵌入式乘法器数量是后者的2倍,但是前者的处理速度却比后者慢很多。足见基于符号LMS算法的自适应滤波器在使用流水线技术优化后的优越性,并且这种优越性随着自适应滤波器阶数的升高、输入位宽的增大将更加明显。

事实上如果不使用流水线技术对基于符号LMS算法的自适应滤波器进行优化,那么它所消耗的LE和寄存器数量分别只有576个和412个,嵌入式乘法器的数量依然是16个,但此时自适应滤波器的处理速度明显降低。这恰恰印证了本文第2节中流水线技术是以面积换取速度的论断。

4　结束语

本文首先阐述了自适应滤波器常用的LMS算法和改进后的符号LMS算法,并且使用MATLAB作了前期对比分析,然后简述流水线技术,最后将基于LMS算法和符号LMS算法的自适应滤波器在FPGA硬件上实现,并且使用流水线技术对基于符号LMS算法的自适应滤波器进行了优化。QuartusⅡ验证得到了各种资源消耗情况和最高时钟频率,ModelSim仿真得到了基于2种算法的自适应滤波器的时序波形图。将实验数据进行对比分析,本文采用符号LMS算法和流水线技术的自适应滤波器在资源消耗和运行速度方面的确更具优势。

参考文献:

[1]Simon Haykin.自适应滤波器原理[M].郑宝玉,译.北京:电子工业出版社,2010:159-238.

[2]高亚军.基于FPGA的数字信号处理[M].北京:电子工业出版社,2012:79-104.

[3]Bernard Widrow,Samuel D Stearns.自适应信号处理[M].王永德,龙宪惠,译.北京:机械工业出版社,2008:68-76.

[4]吴高奎.数字信号处理算法的FPGA高速实现研究[D].成都:电子科技大学,2011:7-21.

[5]祝燕华,刘建业,赖际舟,等.FOG信号的变步长符号LMS自适应消噪方法[J].成都:光电工程.2008,35(11):122-127.

[6]Uwe Meyer-Baese.数字信号处理的FPGA实现[M].刘凌,译.北京:清华大学出版社,2011:425-468.

[7]Rui Guo,DeBrunner L S.A Novel Adaptive Filter Implementation Scheme Using Distributed Arithmetic[J].IEEE Signals,Systems and Computers,2011(11):160-164.

[8]Pramod Kumar Meher,Sang Yoon Park.High Throughput Pipelined Realization of Adaptive FIR Filter Based on Distributed Arithmetic[J].IEEE Transactions on VLSI and System-on-Chip,2013,60(6):346-350.

[9]潘松,黄继业,潘明.EDA技术实用教程-Verilog HDL[M].北京:科学出版社,2010:232-236.

[10]杨海钢,孙嘉斌,王慰.FPGA器件设计技术发展综述[J].北京:电子与信息学报,2010(3):714-723.

[11]张春生,苏开友.FPGA数字信号处理与工程应用实践[M].北京:中国铁道出版社,2013:149-156.

[12]Stephen Brown,Zvonko Vranesic.数字逻辑基础与VHDL设计[M].伍微,译.北京:清华大学出版社,2011:230-248.

邱陈辉(1988-)男,汉族,江苏南通人,博士研究生,研究方向为基于FPGA的数字信号处理生物医学信号处理,qch19881114@126.com;

李锋(1970-)男,汉族,陕西商洛人,博士,副教授,硕士生导师,研究方向为光电信息处理,lifengsl@126.com;

徐祖强(1988-)男,汉族,江西赣州人,硕士研究生,研究方向为数字信号处理及其FPGA实现,930233502@qq.com。

DesignofAdaptiveFilterBasedonFPGAandSignum-LMSAlgorithm*

QIUChenhui1,LIFeng2*,XUZuqiang2

(1.The Key Lab of Biomedical Engineering of Ministry of Education,Zhejiang University,Hangzhou 310027,China;2.College of Electronics and Information,Jiangsu University of Science and Technology,Zhenjiang Jiangsu 212003,China)

Abstract:To decrease the consumption of hardware resource of adaptive filter based on FPGA and LMS algorithm,signum-LMS algorithm is proposed.The processing speed of adaptive filter is increased by reducing the number of multiplications and optimized by pipelining technology.Software simulation verifies the feasibility of signum-LMS algorithm.Hardware simulation proves the superiorities of the adaptive filter using the proposed algorithm and pipelining technology.

Key words:digital signal processing;adaptive filter;least mean square(LMS);signum-least mean square(SLMS);field programmable gate array(FPGA);pipelining

doi:EEACC:127010.3969/j.issn.1005-9490.2014.05.023

中图分类号:TN911.72

文献标识码:A

文章编号:1005-9490(2014)05-0904-04

收稿日期:2013-10-20修改日期:2013-11-13

项目来源:国家自然科学基金项目(11204109);国家自然科学基金项目(51307074)