邱陳輝,李　鋒,徐祖強(qiáng)

(1.浙江大學(xué)生物醫(yī)學(xué)工程教育部重點(diǎn)實(shí)驗(yàn)室,杭州 310027;2.江蘇科技大學(xué)電子信息學(xué)院,江蘇 鎮(zhèn)江 212003)

?

基于FPGA和符號(hào)LMS算法的自適應(yīng)濾波器設(shè)計(jì)*

邱陳輝1,李鋒2*,徐祖強(qiáng)2

(1.浙江大學(xué)生物醫(yī)學(xué)工程教育部重點(diǎn)實(shí)驗(yàn)室,杭州 310027;2.江蘇科技大學(xué)電子信息學(xué)院,江蘇 鎮(zhèn)江 212003)

摘要:為了減少實(shí)現(xiàn)基于FPGA和LMS算法的自適應(yīng)濾波器過(guò)多消耗硬件資源的問(wèn)題,提出了符號(hào)LMS算法,通過(guò)降低乘法運(yùn)算的次數(shù)來(lái)提高自適應(yīng)濾波器的運(yùn)行速度,并使用流水線技術(shù)進(jìn)行優(yōu)化。軟件仿真驗(yàn)證了符號(hào)LMS算法的可行性,硬件仿真證實(shí)了采用該算法和流水線技術(shù)的自適應(yīng)濾波器的優(yōu)越性。

關(guān)鍵詞:數(shù)字信號(hào)處理;自適應(yīng)濾波器;最小均方;符號(hào)最小均方;現(xiàn)場(chǎng)可編程門(mén)陣列;流水線

自適應(yīng)濾波器在現(xiàn)代數(shù)字信號(hào)處理中的應(yīng)用極為廣泛,主要分成系統(tǒng)辨識(shí)、逆模型、預(yù)測(cè)和干擾消除4大類(lèi)別[1]。對(duì)于實(shí)時(shí)性要求很高的場(chǎng)合,往往需要使用硬件設(shè)計(jì)自適應(yīng)濾波器,并且自適應(yīng)算法盡量簡(jiǎn)單、易實(shí)現(xiàn)[2]。基于現(xiàn)場(chǎng)可編程門(mén)陣列(FPGA)硬件和最小均方(LMS)自適應(yīng)算法的自適應(yīng)濾波器近年來(lái)被不斷地研究和改進(jìn)。

由于FPGA中嵌入了較多硬線乘法器和加減器,使用它們很容易實(shí)現(xiàn)乘累加(MAC)運(yùn)算,故通常將采用LMS算法的自適應(yīng)濾波器直接映射到FPGA芯片上。但這樣消耗較多的硬件資源,也不能發(fā)揮FPGA并行處理的優(yōu)勢(shì)。故本文提出了利用符號(hào)LMS算法和流水線技術(shù)對(duì)上述自適應(yīng)濾波器進(jìn)行優(yōu)化,從而減少嵌入式乘法器資源的消耗并且提高運(yùn)行速度。

1　自適應(yīng)濾波器算法

1.1LMS算法

設(shè)x(n)和w(n)分別表示自適應(yīng)濾波器的輸入信號(hào)和權(quá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)

誤差計(jì)算:

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

(2)

權(quán)值更新:

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

(3)

其中y(n)是自適應(yīng)濾波器的輸出信號(hào),d(n)是期望信號(hào),e(n)表示誤差信號(hào),μ是收斂因子,L是自適應(yīng)濾波器的階數(shù)。因?yàn)長(zhǎng)MS算法是嚴(yán)格順序執(zhí)行的,所以式(1)～式(3)的次序不能顛倒[3]。其模塊圖如圖1所示。

圖1　LMS算法的模塊圖

雖然LMS算法的推導(dǎo)過(guò)程涉及求梯度和微分,但是其最終形式只涉及乘法、加減和迭代3種運(yùn)算,并且乘法運(yùn)算量最多。而利用FPGA實(shí)現(xiàn)基于LMS算法的自適應(yīng)濾波器時(shí),硬件資源的消耗很大一部分來(lái)源于乘法運(yùn)算。不管是利用FPGA中的基本邏輯單元LE(Logic Element)還是嵌入式乘法器模塊實(shí)現(xiàn)乘法運(yùn)算,基于硬件的乘法運(yùn)算都將是高成本的,應(yīng)盡可能地減少[4]。

1.2符號(hào)LMS算法

式(1)中的乘法是為了計(jì)算自適應(yīng)均衡器的輸出信號(hào),不能刪減。式(3)中的乘法是針對(duì)收斂因子μ、誤差信號(hào)e(n)和輸入矢量x(n)進(jìn)行的,可以進(jìn)行改進(jìn)。針對(duì)一些特殊應(yīng)用,e(n)和x(n)的乘積事實(shí)上無(wú)需兩者都以全精度值參與計(jì)算,只取他們的符號(hào)進(jìn)行運(yùn)算即可[5]。

第1種方案是對(duì)e(n)取符號(hào),利用正負(fù)號(hào)符號(hào)函數(shù)Signum(·)得 sign[e(n)],而x(n)保持全精度,這樣兩者相乘的結(jié)果就是x(n),要么是對(duì)x(n)取負(fù)值。第2種方案是對(duì)x(n)中的x(n)、x(n-1)、…、x(n-L+1)取符號(hào),利用Signum(·)得sign[x(n)],此時(shí)兩者的乘積要么就是e(n),要么就是對(duì)e(n)取負(fù)值。第3種方案是同時(shí)對(duì)e(n)和x(n)取符號(hào),利用Signum(·)得sign[e(n)]和sign[x(n)],這樣兩者相乘的結(jié)果就是1或-1。這3種符號(hào)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)

符號(hào)LMS算法其實(shí)是對(duì)LMS算法的一種改進(jìn),其模塊圖如圖2所示,它可由隨機(jī)梯度法推導(dǎo)而來(lái),以均方誤差E[|e(n)|2]為代價(jià)函數(shù)J(n),推導(dǎo)關(guān)鍵是對(duì)J(n)求梯度,然后對(duì)其權(quán)值w(n)進(jìn)行自適應(yīng)調(diào)整時(shí),只考慮J(n)的梯度方向,忽略具體的梯度值。因此,犧牲輸入信號(hào)或誤差信號(hào)精度的符號(hào)LMS算法并不適用于所有的自適應(yīng)系統(tǒng)[6],利用MATLAB對(duì)使用該算法的自適應(yīng)濾波器進(jìn)行前期的驗(yàn)證評(píng)估是十分必要的。

圖2　符號(hào)LMS算法的模塊圖

假若μ的取值不是2的冪形式,那么第1、第2種方案節(jié)省的乘法器數(shù)量相同,而第3種方案節(jié)省的乘法器數(shù)量是它們的2倍。若將μ值設(shè)置為2的冪形式,與μ相乘可以利用移位運(yùn)算代替[7],那么上述3種方案所節(jié)省的乘法器數(shù)量是相同的。但是針對(duì)自適應(yīng)濾波器的具體應(yīng)用場(chǎng)合,3種方案對(duì)自適應(yīng)濾波器的穩(wěn)定性、收斂速度的影響會(huì)有差異。

由文獻(xiàn)[6]知第3種方案最受青睞,已被用作自適應(yīng)差分脈沖編碼調(diào)制傳輸?shù)膰?guó)際電信聯(lián)盟標(biāo)準(zhǔn),所以本文以它為例進(jìn)行對(duì)比分析。圖3給出了分別基于LMS算法和符號(hào)LMS算法的自適濾波器的均方誤差曲線圖,這里取L=8,μ=2-7。由圖3可知采用符號(hào)LMS算法的自適應(yīng)濾波器的均方誤差收斂速度比采用LMS算法更快,并且更加趨近于零。這主要由于在每次迭代更新中,符號(hào)LMS算法進(jìn)行的乘法計(jì)算量相對(duì)于LMS算法減少了一半。

圖3　自適應(yīng)濾波器的均方誤差曲線

2　流水線技術(shù)

廣義上講,流水線技術(shù)就是將一個(gè)重復(fù)的過(guò)程分解為若干子過(guò)程,讓每個(gè)子過(guò)程可以和其他的子過(guò)程同時(shí)進(jìn)行,是一種并行處理技術(shù)。就FPGA而言,流水線技術(shù)是指將組合邏輯電路的延時(shí)路徑進(jìn)行系統(tǒng)性地分級(jí),并且在各個(gè)分級(jí)之間插入寄存器來(lái)暫存中間數(shù)據(jù)。這樣便縮短了信號(hào)在一個(gè)周期內(nèi)通過(guò)組合邏輯電路的延時(shí)路徑長(zhǎng)度,從而提高了時(shí)鐘頻率。對(duì)于應(yīng)用最廣泛的同步時(shí)序電路而言,其處理速度就是指它的時(shí)鐘頻率。時(shí)鐘頻率越快,處理數(shù)據(jù)的時(shí)間間隔就越短,在單位時(shí)間內(nèi)處理的數(shù)據(jù)量就越大,也就提高了處理速度[8]。

圖4形象說(shuō)明了流水線技術(shù)的基本原理,假設(shè)圖中的組合邏輯電路具有較大的延時(shí),于是將其分割成具有較小延時(shí)的組合邏輯電路1和2,并插入2個(gè)同步寄存器。這樣組合邏輯電路1和2在同一時(shí)間內(nèi)處理的信號(hào)就會(huì)不同,因?yàn)榻?jīng)過(guò)了寄存器的鎖存。2個(gè)組合邏輯電路1和2就可以并行執(zhí)行[9]。該圖也說(shuō)明了流水線技術(shù)實(shí)際上是以增加硬件資源的消耗來(lái)?yè)Q取更高處理速度的。

圖4　流水線技術(shù)基本原理圖

在FPGA中使用流水線技術(shù),需要的額外成本不多,因?yàn)槊總€(gè)LE本身就包含一個(gè)寄存器和寄存器鏈邏輯。提升基于FPGA的自適應(yīng)濾波器的運(yùn)行速度關(guān)鍵在于提高乘法器的處理速度。由文獻(xiàn)[6]可知,對(duì)于FPGA中的一個(gè)N位×N位的乘法器,若想達(dá)到最高處理速度,那么需要的流水線級(jí)數(shù)是log2(N)。本文自適應(yīng)濾波器輸入信號(hào)的位寬設(shè)置成16位,故采用4級(jí)流水線時(shí)可以充分發(fā)揮流水線技術(shù)的速度優(yōu)勢(shì)。

3　FPGA實(shí)現(xiàn)

FPGA是通過(guò)采用可編程的查找表(LUT)結(jié)構(gòu)來(lái)實(shí)現(xiàn)可編程邏輯的。LE是Cyclone系列FPGA芯片中最基本的可編程單元,主要由一個(gè)4輸入的LUT、一個(gè)可編程的寄存器、進(jìn)位鏈邏輯和寄存器鏈邏輯構(gòu)成[10]。因此,我們通常使用 在同一時(shí)鐘的驅(qū)動(dòng)下 某信號(hào)通過(guò)源寄存器至目的寄存器的最短路徑所消耗的最少時(shí)間(Tmin或者Fmax)來(lái)表示對(duì)信號(hào)的處理速度,使用設(shè)計(jì)所需LE的總數(shù)量來(lái)表示FPGA硬件資源的消耗情況[11-12]。

為了跟本文1.2節(jié)最后的MATLAB仿真實(shí)驗(yàn)保持一致,基于Altera公司CycloneⅢEP3C10U256C8FPGA芯片的自適應(yīng)濾波器仍然設(shè)為8階,收斂因子仍取2-7,系統(tǒng)時(shí)鐘clk的頻率設(shè)成數(shù)據(jù)輸入頻率的6倍,自適應(yīng)算法分別采用LMS算法和符號(hào)LMS算法。使用超高速集成電路硬件描述語(yǔ)言(VHDL)進(jìn)行對(duì)分別基于2種算法的自適應(yīng)濾波器進(jìn)行編程,主要包括初始化模塊,信號(hào)輸入模塊,時(shí)鐘分頻模塊,權(quán)值更新模塊,誤差計(jì)算模塊,濾波輸出模塊。接著利用QuartusⅡ和ModelSim軟件對(duì)它們分別進(jìn)行編譯、綜合、適配、時(shí)序分析。設(shè)定x(n)、d(n)、e(n)和y(n)的二進(jìn)制位寬分別是16位,其中x(n)和d(n)的取值是通過(guò)對(duì)本文1.2節(jié)利用MATLAB仿真時(shí)的x(n)和d(n)數(shù)據(jù)進(jìn)行16位量化得到的。

圖5是基于FPGA和LMS算法的自適應(yīng)濾波器的ModelSim時(shí)序驗(yàn)證圖,對(duì)該自適應(yīng)濾波器進(jìn)行VHDL編程時(shí),沒(méi)有使用流水線技術(shù)進(jìn)行優(yōu)化,系統(tǒng)時(shí)鐘的最高頻率是76.75MHz,總共消耗了32個(gè)嵌入式乘法器。詳細(xì)的資源消耗情況如表1所示。圖5中誤差信號(hào)e的波形開(kāi)始時(shí)抖動(dòng)幅度較大,之后慢慢平緩,該設(shè)計(jì)達(dá)到了預(yù)期效果。

圖5　基于LMS算法的自適應(yīng)濾波器的時(shí)序波形圖

圖6是基于FPGA和符號(hào)LMS算法的自適應(yīng)濾波器的ModelSim時(shí)序驗(yàn)證圖,在VHDL編程時(shí)添加了4級(jí)流水線對(duì)該自適應(yīng)濾波器進(jìn)行優(yōu)化,圖6中誤差信號(hào)el的波形開(kāi)始時(shí)抖動(dòng)幅度很大,隨后漸趨平緩。和圖5中的e波形相比,圖6中el波形的抖動(dòng)更小,這跟1.2節(jié)中的MATLAB仿真結(jié)果是完全一致的,因此本設(shè)計(jì)是正確的。表1也給出了該自適應(yīng)濾波器的資源消耗情況和處理速度。

圖6　基于LMS算法的自適應(yīng)濾波器的時(shí)序波形圖

表1基于2種算法的自適應(yīng)濾波器的資源消耗和速度比較

算法LEsRegistersEmbeddedmultiplierFmax/MHzLMS141213213276．75符號(hào)LMS103793916123．93

由表1可知,基于LMS算法的自適應(yīng)濾波器所消耗的LE和寄存器數(shù)量分別比基于符號(hào)LMS算法的多了375個(gè)和382個(gè),并且前者所消耗的嵌入式乘法器數(shù)量是后者的2倍,但是前者的處理速度卻比后者慢很多。足見(jiàn)基于符號(hào)LMS算法的自適應(yīng)濾波器在使用流水線技術(shù)優(yōu)化后的優(yōu)越性,并且這種優(yōu)越性隨著自適應(yīng)濾波器階數(shù)的升高、輸入位寬的增大將更加明顯。

事實(shí)上如果不使用流水線技術(shù)對(duì)基于符號(hào)LMS算法的自適應(yīng)濾波器進(jìn)行優(yōu)化,那么它所消耗的LE和寄存器數(shù)量分別只有576個(gè)和412個(gè),嵌入式乘法器的數(shù)量依然是16個(gè),但此時(shí)自適應(yīng)濾波器的處理速度明顯降低。這恰恰印證了本文第2節(jié)中流水線技術(shù)是以面積換取速度的論斷。

4　結(jié)束語(yǔ)

本文首先闡述了自適應(yīng)濾波器常用的LMS算法和改進(jìn)后的符號(hào)LMS算法,并且使用MATLAB作了前期對(duì)比分析,然后簡(jiǎn)述流水線技術(shù),最后將基于LMS算法和符號(hào)LMS算法的自適應(yīng)濾波器在FPGA硬件上實(shí)現(xiàn),并且使用流水線技術(shù)對(duì)基于符號(hào)LMS算法的自適應(yīng)濾波器進(jìn)行了優(yōu)化。QuartusⅡ驗(yàn)證得到了各種資源消耗情況和最高時(shí)鐘頻率,ModelSim仿真得到了基于2種算法的自適應(yīng)濾波器的時(shí)序波形圖。將實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比分析,本文采用符號(hào)LMS算法和流水線技術(shù)的自適應(yīng)濾波器在資源消耗和運(yùn)行速度方面的確更具優(yōu)勢(shì)。

參考文獻(xiàn):

[1]Simon Haykin.自適應(yīng)濾波器原理[M].鄭寶玉,譯.北京:電子工業(yè)出版社,2010:159-238.

[2]高亞軍.基于FPGA的數(shù)字信號(hào)處理[M].北京:電子工業(yè)出版社,2012:79-104.

[3]Bernard Widrow,Samuel D Stearns.自適應(yīng)信號(hào)處理[M].王永德,龍憲惠,譯.北京:機(jī)械工業(yè)出版社,2008:68-76.

[4]吳高奎.數(shù)字信號(hào)處理算法的FPGA高速實(shí)現(xiàn)研究[D].成都:電子科技大學(xué),2011:7-21.

[5]祝燕華,劉建業(yè),賴際舟,等.FOG信號(hào)的變步長(zhǎng)符號(hào)LMS自適應(yīng)消噪方法[J].成都:光電工程.2008,35(11):122-127.

[6]Uwe Meyer-Baese.數(shù)字信號(hào)處理的FPGA實(shí)現(xiàn)[M].劉凌,譯.北京:清華大學(xué)出版社,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]潘松,黃繼業(yè),潘明.EDA技術(shù)實(shí)用教程-Verilog HDL[M].北京:科學(xué)出版社,2010:232-236.

[10]楊海鋼,孫嘉斌,王慰.FPGA器件設(shè)計(jì)技術(shù)發(fā)展綜述[J].北京:電子與信息學(xué)報(bào),2010(3):714-723.

[11]張春生,蘇開(kāi)友.FPGA數(shù)字信號(hào)處理與工程應(yīng)用實(shí)踐[M].北京:中國(guó)鐵道出版社,2013:149-156.

[12]Stephen Brown,Zvonko Vranesic.數(shù)字邏輯基礎(chǔ)與VHDL設(shè)計(jì)[M].伍微,譯.北京:清華大學(xué)出版社,2011:230-248.

邱陳輝(1988-)男,漢族,江蘇南通人,博士研究生,研究方向?yàn)榛贔PGA的數(shù)字信號(hào)處理生物醫(yī)學(xué)信號(hào)處理,qch19881114@126.com;

李鋒(1970-)男,漢族,陜西商洛人,博士,副教授,碩士生導(dǎo)師,研究方向?yàn)楣怆娦畔⑻幚?lifengsl@126.com;

徐祖強(qiáng)(1988-)男,漢族,江西贛州人,碩士研究生,研究方向?yàn)閿?shù)字信號(hào)處理及其FPGA實(shí)現(xiàn),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

中圖分類(lèi)號(hào):TN911.72

文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1005-9490(2014)05-0904-04

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

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(11204109);國(guó)家自然科學(xué)基金項(xiàng)目(51307074)