高金定，許慧燕，楊　盼，段　波

(1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083；

2.湖南涉外經(jīng)濟(jì)學(xué)院信息科學(xué)與工程學(xué)院，湖南 長沙 410205)

?

基于割集重定時(shí)規(guī)則的串行最小均方誤差自適應(yīng)濾波器

高金定1，2，許慧燕2，楊盼2，段波2

(1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083；

2.湖南涉外經(jīng)濟(jì)學(xué)院信息科學(xué)與工程學(xué)院，湖南 長沙 410205)

摘要:針對標(biāo)準(zhǔn)串行最小均方誤差(LMS)自適應(yīng)濾波器運(yùn)算速度受到系數(shù)更新模塊運(yùn)算限制的不足，提出了基于割集重定時(shí)規(guī)則的LMS自適應(yīng)濾波器。通過利用割集重定時(shí)技術(shù)，對標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器關(guān)鍵路徑進(jìn)行了優(yōu)化，有效縮短了該濾波器關(guān)鍵路徑，提高了運(yùn)行速度。利用DSP Builder軟件構(gòu)建了改進(jìn)前后自適應(yīng)噪聲對消模型并進(jìn)行了仿真，仿真驗(yàn)證表明：未引入流水線結(jié)構(gòu)的情況下，在EP2C35F484型現(xiàn)場可編程門陣列(FPGA)芯片上，自適應(yīng)濾波器響應(yīng)速度從20.40 MHz提高到了22.89 MHz。利用割集重定時(shí)技術(shù)對自適應(yīng)濾波器結(jié)構(gòu)關(guān)鍵路徑進(jìn)行優(yōu)化設(shè)計(jì)，能有效的提高自適應(yīng)濾波器的響應(yīng)速度。

關(guān)鍵詞:自適應(yīng)濾波；串行LMS；割集重定時(shí)；優(yōu)化設(shè)計(jì)；響應(yīng)速度

0引言

隨著電子技術(shù)的發(fā)展，F(xiàn)PGA技術(shù)開始廣泛應(yīng)用到地球物理儀器研制中，儀器數(shù)據(jù)處理速度越來越快、集成度越來越高、體積也越來越小[1]。LMS最小均方誤差算法自適應(yīng)濾波器具有運(yùn)算量小、結(jié)構(gòu)簡單等優(yōu)勢，在地球物理勘探儀器中有著廣泛的應(yīng)用前景[2]。如何在FPGA芯片上實(shí)現(xiàn)高速LMS自適應(yīng)噪聲對消濾波器以滿足地球物理儀器的需求具有重要的實(shí)際意義，也是目前國內(nèi)外研究的熱點(diǎn)[3]。為了獲得高速LMS自適應(yīng)濾波器，目前國內(nèi)外研究重點(diǎn)集中在LMS自適應(yīng)濾波算法優(yōu)化上，比如引入前瞻技術(shù)和松弛技術(shù)，對串行LMS自適應(yīng)濾波算法更新方程進(jìn)行近似，以提高運(yùn)行速度，然后這些方法僅適用于平穩(wěn)環(huán)境，此外由于采取了近似估計(jì)，對LMS自適應(yīng)算法濾波性能和收斂性能均有一定的影響[4-6]。

本文針對標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器運(yùn)算速度受到系數(shù)更新模塊運(yùn)算限制的不足，引入割集重定時(shí)規(guī)則[7-8]，對LMS自適應(yīng)濾波器關(guān)鍵路徑進(jìn)行了優(yōu)化，有效縮短了關(guān)鍵路徑，提出了基于割集重定時(shí)規(guī)則的串行LMS自適應(yīng)濾波器。

1割集重定時(shí)規(guī)則

定義1：關(guān)鍵路徑：數(shù)據(jù)流圖中，所有零延遲路徑中，具有最長運(yùn)算時(shí)間的路徑稱為關(guān)鍵路徑。

定義2：環(huán)路邊界與迭代邊界：每個環(huán)路執(zhí)行的最低時(shí)間稱為環(huán)路邊界，具有最大環(huán)路邊界值的環(huán)路稱為關(guān)鍵環(huán)路。顯然，關(guān)鍵環(huán)路的環(huán)路邊界表示了用硬件實(shí)現(xiàn)數(shù)據(jù)流圖的數(shù)據(jù)處理速度的極限值，這個極限稱為迭代邊界，一般用T∞來表示。

定義3：割集重定時(shí)規(guī)則：割集是數(shù)據(jù)流圖的一組邊，將這組邊從數(shù)據(jù)流圖上除去后可以將數(shù)據(jù)流圖分成兩個不相連的子圖。

如圖1所示，將數(shù)據(jù)流圖(a)沿虛線斷開，則可以將數(shù)據(jù)流圖(a)分成圖(b)所示的兩個不相連的子圖G1和G2，則圖(a)中虛線所切割的所有邊的集合稱為數(shù)據(jù)流圖(a)的一個割集。

割集重定時(shí)只影響割集中邊的權(quán)重(延遲數(shù))。如圖1(b)中兩個不相連的子圖G1和G2，割集重定時(shí)包含兩個內(nèi)容：若從子圖G1到子圖G2的每條邊都增加k個延遲單元，則從子圖G2到子圖G1的每條邊都減少k個延遲單元，反之亦然。

如圖1(c)所示，若從子圖G1到子圖G2的每條邊都減少1個延遲單元，則從子圖G2到子圖G1的每條邊都增加1個延遲單元。最后得到割集重定時(shí)后的數(shù)據(jù)流圖如圖(d)所示。

圖1　數(shù)據(jù)流圖割集重定時(shí)示例Fig.1　Cutset retiming example of data flow diagrams

2基于割集重定時(shí)技術(shù)的LMS自適應(yīng)濾波器優(yōu)化設(shè)計(jì)方法

2.1串行LMS自適應(yīng)濾波器結(jié)構(gòu)

當(dāng)輸入信號和噪聲統(tǒng)計(jì)特性未知或者發(fā)生變化時(shí)，自適應(yīng)濾波器能夠在滿足某種準(zhǔn)則前提下能自動調(diào)整濾波器系數(shù)，始終實(shí)現(xiàn)最優(yōu)濾波。

圖2是標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器結(jié)構(gòu)圖。主要包括標(biāo)準(zhǔn)FIR濾波器和系數(shù)更新兩個部分。其中x(k)是自適應(yīng)濾波器的輸入信號，y(k)是自適應(yīng)濾波器的輸出信號，d(k)是期望信號，e(k)是誤差信號。通常利用誤差信號e(k)構(gòu)造自適應(yīng)濾波算法所需要的目標(biāo)函數(shù)，并定義好自適應(yīng)濾波器系數(shù)的更新方式，目標(biāo)函數(shù)的最小化意味著在某種意義上，自適應(yīng)濾波器的輸出信號y(k)與期望信號d(k)實(shí)現(xiàn)了匹配，此時(shí)也就實(shí)現(xiàn)了最優(yōu)濾波。

LMS算法自適應(yīng)濾波器核心迭代方程如式(1)、(2)和(3)所示，式(1)是LMS自適應(yīng)濾波器輸出求和表達(dá)式，式(2)是誤差函數(shù)方程，式(3)是系數(shù)更新表達(dá)式。

y(k)=xT(k)w(k-1)

(1)

e(k)=d(k)-xT(k)w(k-1)

(2)

w(k)=w(k-1)+2μe(k)x(k)

(3)

圖2　串行LMS自適應(yīng)濾波器結(jié)構(gòu)Fig.2　Structure of serial LMS adaptive filter

2.2優(yōu)化設(shè)計(jì)方法

根據(jù)關(guān)鍵路徑的定義，影響標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器運(yùn)行速度的關(guān)鍵路徑如圖2紅色虛線所示，此關(guān)鍵路徑執(zhí)行時(shí)間主要由3個乘法器和5個加法器的執(zhí)行時(shí)間決定, 假設(shè)乘法器的執(zhí)行時(shí)間是tm，加法器的執(zhí)行時(shí)間是ta，則此關(guān)鍵路徑執(zhí)行時(shí)間為：

Tcp=3tm+5ta

(4)

要提高LMS自適應(yīng)濾波器的運(yùn)行速度，只能對此關(guān)鍵路徑進(jìn)行優(yōu)化。如圖2所示，對LMS自適應(yīng)系數(shù)更新部分的加法器做割集，即圖中四個橢圓形虛線框所示的割集CutsetA，對移入每個加法器節(jié)點(diǎn)的所有邊增加一個延遲單元Z-1，相應(yīng)地對移出每個加法器節(jié)點(diǎn)的所有邊增加一個超前單元Z+1(等效為減少一個延遲單元Z-1)，按照此規(guī)則，得到了一種新的串行LMS自適應(yīng)濾波器結(jié)構(gòu)，如圖3所示。

圖3　割集重定時(shí)后的串行LMS自適應(yīng)濾波器結(jié)構(gòu)Fig. 3　Structure of serial LMS adaptive filter after cutest retiming

從圖3可以看出，割集重定時(shí)后串行LMS自適應(yīng)濾波器的關(guān)鍵路徑有所縮短，減少了一個加法器的運(yùn)行時(shí)間ta，關(guān)鍵路徑執(zhí)行時(shí)間縮短為：

Tcp=3tm+4ta

(5)

因此，從理論上來看，改進(jìn)后的物理可實(shí)現(xiàn)的LMS自適應(yīng)濾波器結(jié)構(gòu)運(yùn)行速度應(yīng)該更快。同時(shí)，從圖2和圖3還可以看出，割集重定時(shí)并沒有改變串行LMS自適應(yīng)濾波器關(guān)鍵環(huán)路的迭代邊界，關(guān)鍵環(huán)路的寄存器數(shù)量并沒有改變。

3驗(yàn)證

用DSP Builder建模工具，構(gòu)建標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器和割集重定時(shí)后的串行LMS自適應(yīng)濾波器噪聲對消模型，分別如圖4和圖5所示。仿真模型主要由Add加法器模塊、BC總線轉(zhuǎn)換模塊、D延遲單元模塊和P乘法器模塊組成。自適應(yīng)濾波器的輸入信號高斯白噪聲，期望信號為8 Hz的正弦波待檢測信號疊加高斯白噪聲干擾。

圖4　標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器模型Fig.4　Model of serial LMS adaptive filter

圖5　割集重定時(shí)后的串行LMS自適應(yīng)濾波器模型Fig.5　Model of serial LMS adaptive filter after cutest retiming

圖6是期望信號頻譜，從圖可以看出，期望信號除了有待檢測的8 Hz正弦波信號以外，在整個頻域范圍內(nèi)都有著白噪聲。

圖6　期望信號頻譜(待檢測信號+高斯白噪聲)Fig. 6　Frequency spectrum of desired signals

圖7是標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器時(shí)域仿真波形圖，從上到下四個信號依次為輸入的白噪聲信號、自適應(yīng)濾波器輸出信號、自適應(yīng)濾波器誤差信號以及自適應(yīng)濾波器的期望信號。在自適應(yīng)噪聲對消系統(tǒng)中，誤差信號為實(shí)際檢測輸出的有用信號。從圖7可以看出，所設(shè)計(jì)的自適應(yīng)噪聲對消濾波器能較好的從白噪聲環(huán)境中檢測出有用的正弦波信號。

圖7　自適應(yīng)濾波器時(shí)域仿真波形Fig.7　Time domain simulation waveforms of adaptive filter

圖8是自適應(yīng)濾波器穩(wěn)定輸出后誤差信號的頻譜，可以看出，高斯白噪聲已經(jīng)被較好地濾除了。運(yùn)行Signal Compiler工具，將模型轉(zhuǎn)換成VHDL硬件描述語言，用Modelsim軟件進(jìn)行寄存器傳輸級(RTL)仿真，仿真結(jié)果如圖9所示。從圖9可以看出，RTL仿真結(jié)果與Simulink中模型仿真結(jié)果基本一致，這進(jìn)一步驗(yàn)證了設(shè)計(jì)的可靠性。圖10、圖11和圖12分別是割集重定時(shí)后自適應(yīng)濾波器時(shí)域仿真波形、自適應(yīng)濾波器誤差信號頻譜和RTL寄存器傳輸級仿真結(jié)果?？梢钥闯觯罴囟〞r(shí)后的自適應(yīng)濾波器的性能與標(biāo)準(zhǔn)串行LMS自適應(yīng)濾波器基本一致。

將模型轉(zhuǎn)換以后得到的VHDL程序在Quartus II軟件中進(jìn)行編譯與適配，在同一款FPGA (EP2C35F484C8)芯片上得到割集重定時(shí)前后自適應(yīng)濾波器的響應(yīng)速度和資源消耗情況，如表1所示。

圖8　穩(wěn)定后自適應(yīng)濾波誤差信號頻譜Fig.8　Frequency spectrum of adaptive filter’s error signal after stabilization

圖9　自適應(yīng)濾波器RTL仿真結(jié)果波形Fig.9　RTL simulation waveforms of adaptive filter

圖10　自適應(yīng)濾波器時(shí)域仿真波形(割集重定時(shí)后)Fig.10　Time domain simulation waveforms of adaptive filter after cutest retiming

圖11　自適應(yīng)濾波誤差信號頻譜(割集重定時(shí)后)Fig.11　Frequency spectrum of adaptive filter’s error signal after cutest retiming

圖12　自適應(yīng)濾波器RTL仿真波形(割集重定時(shí)后)Fig.12　RTL simulation waveforms of adaptive filter after cutest retiming

從表1可以看出，在沒有用到流水線結(jié)構(gòu)的情況下，割集重定時(shí)后自適應(yīng)濾波器的響應(yīng)速度從原來的20.40 MHz提高到了22.89 MHz，還少用了26個邏輯單元。

表1　適應(yīng)濾波器響應(yīng)速度及資源消耗情況

4結(jié)論

本文提出了基于割集重定時(shí)規(guī)則的串行LMS自適應(yīng)濾波器。通過利用割集重定時(shí)方法，對串行LMS自適應(yīng)濾波器關(guān)鍵路徑進(jìn)行優(yōu)化，該濾波器關(guān)鍵路徑得到了有效的縮短，運(yùn)行速度得到了提高。仿真驗(yàn)證表明，未引入流水線結(jié)構(gòu)的情況下，在EP2C35F484型FPGA芯片上，自適應(yīng)濾波器響應(yīng)速度從20.40 MHz提高到了22.89 MHz。當(dāng)然本文所采用的割集重定時(shí)方法對自適應(yīng)濾波器的迭代邊界沒有影響，關(guān)鍵環(huán)路的迭代周期還是保持不變，如何減小關(guān)鍵環(huán)路的迭代周期進(jìn)一步提高運(yùn)行速度值得進(jìn)一步研究。

參考文獻(xiàn):

[1]Gao Jinding, An Improved Delayed Structure of Least Mean Square Adaptive Filter and Its Field Programmable Gate Array Implementation[J]. ICIC Express Letters, Part B: Applications, 2013, 4(1):69-73.

[2]劉雄飛，高金定.LMS自適應(yīng)濾波器FPGA實(shí)現(xiàn)的新方法[J].壓電與聲光，2007,29(1)：87-89.

[3]湯霞清,劉翔,程旭維,等. 基于FPGA的光纖陀螺自適應(yīng)LMS濾波算法研究[J]. 計(jì)算機(jī)測量與控制,2015,23(3):867-869,872.

[4]李鋒，邱陳輝，徐祖強(qiáng). 基于改進(jìn)DLMS算法的自適應(yīng)FIR濾波器設(shè)計(jì)[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(3):895-899.

[5]白瑞青,宋軍,宋鑫霞,等. 基于現(xiàn)場可編程門陣列的彈載遙測記憶重發(fā)器[J].探測與控制學(xué)報(bào),2015, 37(2):55-58.

[6]高金定. 平穩(wěn)環(huán)境下LMS算法優(yōu)化分析及其FPGA實(shí)現(xiàn)[J].壓電與聲光,2013,35(3):445-451.

[7]Parhi著.VLSI數(shù)字信號處理系統(tǒng)：設(shè)計(jì)與實(shí)現(xiàn)[M].陳弘毅,譯.北京: 機(jī)械工業(yè)出版社, 2004

[8]施國勇.數(shù)字信號處理FPGA電路設(shè)計(jì)[M].北京:高等教育出版社, 2010.

Serial Least Mean Square Error Adaptive Filter Based on Cutk-Set Retiming Rules

GAO Jinding1,2，XU Huiyan2，YAN PAN2，DUAN Bo2

(1.School of Earth Science and Info-Physics, Central South University, Changsha, Hunan, China, 410083；2.School of Information Science and Engineering, Hunan International Economics University, Changsha, Hunan, China, 410205)

Abstract:Aiming at the problem of the standard serial least mean square error algorithm adaptive filter’s calculation speed was limited by its calculation of the coefficient update module, an improved LMS adaptive filter was proposed. Using cut-set retiming technology, the critical path of the standard serial LMS adaptive filter has been optimized, and an improved structure of LMS adaptive filter was obtained. Then using DSP Builder software, the adaptive noise cancellation system models with the standard serial LMS structure and the improved structure were built respectively, and a series of simulation and analysis was completed. Simulation results show that: without introducing pipelining, on EP2C35F484 Field Programmable Gate Array chip, the response speed of the adaptive filter was improved from 20.40MHz to 22.89MHz. Using cut-set retiming technology to optimize the critical path of adaptive filter can effectively improve its response speed.

Key words:adaptive filter; serial LMS; cut-set retiming; optimization design；response speed

中圖分類號:TN713.7

文獻(xiàn)標(biāo)志碼:A

文章編號：1008-1194(2016)01-0071-05

作者簡介:高金定(1981—)，男，湖南桃江人，副教授，博士研究生，研究方向：數(shù)字信號處理及其FPGA實(shí)現(xiàn)技術(shù)。E-mail: jdgao@qq.com。

基金項(xiàng)目:湖南省2013年度科研條件創(chuàng)新專項(xiàng)項(xiàng)目資助(2013TT2037)；湖南省教育廳重點(diǎn)科研項(xiàng)目資助(15A106)；湖南省教育廳一般科研項(xiàng)目資助(15C782)

*收稿日期:2015-11-01