自適應Voltera濾波的一種快速算法

1、1996年8月InformationandControlAug.,1996自適應Volterra濾波的一種快速算法0羅忠謝凱年劉文江(西安交通大學自動控制系710049)摘要Volterra濾波是非線性自適應信號處理中一種有效的方法.但是其很高的計算復雜度使之在實際應用中有較大的局限性.針對這一問題,本文提出了一種Volterra,可有效地降低計算的復雜度.Volterra自適應模型建模的仿真實例.關鍵詞非線性自適應信號處理,Volterra,1前言,.但實際工程應用中大量,正因為這樣,近年來人們已建立了許多非線性濾波的方法.,非線性自適應濾波已成功地應用于以下一些問題.在數字通信中當波特率高

2、于4800bits s時,誤碼主要是由信道的非線性畸變引起的,因此要用非線性均衡器來均衡信道1.在電話信號傳輸中,信號的壓擴會引起非線性失真,也要采用非線性均衡予以補償2.其他應用有噪聲對消3、高斯過程的非線性函數的檢測4、生物現象的建模5等.長期以來人們一直懼怕非線性問題主要是因為不論從理論分析還是實際應用角度看,這類問題都十分困難.即便是十分有效的Volterra濾波也因其過高的計算量而在實際應用中有較大局限性6.2自適應Volterra濾波及其算法當滿足一定條件時,非線性系統的輸入與輸出關系可用Volterra泛函級數來描述7.設離散時間非線性系統的輸入為x(n),輸出為y(n),則由V

3、olterra級數表示的輸出方程為ky(n)=h0+hk=11=02=0k=0(1,2,k)x(n-1)x(n-k)(1)為了使這一類關系具有實用意義,求和過程顯然不能是無限的.對(1)中求和取有限項得到DN-1N-1N-1kyT(n)=h0+hk=11=02=0k=0(1,2,k)x(n-1)x(n-k)(2)稱為最高階為D,記憶長度為N的截斷Volterra級數模型.文獻8指出當D,N充分大時,對任意時刻n, y(n)-yT(n) 可充分小.由(2)可構造Volterra濾波器及其自適應算法.濾波器輸入信號為x(n),輸出信號為ya(n).濾波器的各抽頭系數分別為1D各階不同的Volter

4、ra核即h1(0),h1(1),h1(N-1),h2(0,0),h2(N-1,N-1),hD(0,0,0),hD(N-1,N-1,N-1),各抽頭輸入為x(n),x(n-N+1),x2(n),x2(n-N+1),xD(n),xD(n-N+1).定義輸入向1995-08-08收稿0國家自然科學基金資助項目4期羅忠等:自適應Volterra濾波的一種快速算法207量為2X(n)=x(n),x(n-N+1),x(n),x(n)x(n-1),xD(n-N+1)T(3)(4)(5)定義系數向量為TH(n)=h1(0),h1(N-1),h2(0,0),h2(0,1),hD(N-1,N-1)則有ya(n)=

5、HT(n)X(n)T誤差信號為e(n)=d(n)-ya(n)=d(n)-H(n)X(n)(6)(7)基于最小均方誤差(MSE)準則的梯度下降算法為H(n+1)=H(n)+2e(n)(n).為下降步長,d(n)為期望輸出信號由于算法每次迭代計算程序完全相同,加法和乘法次數來表征算法復雜度.命題1DDda2Nd=1,Nm=2(d+d=1m2)Nd通過分析(7)可得以上結論,此處不擬證明.可見Na,N際中用的Volterra濾波器的D,N兩參數均不能很大6.均為O(ND).例如當D=3,N=4時有Na=168,Nm=396.如此龐大的計算量在實時性要求較高的應用中是不可想象的.故實3快速算法原理先來

6、看一個很有啟發(fā)性的例子.D=2,N=4的Volterra濾波器有14個抽頭系數,對應的抽頭信號是x(n),x(n-1),x(n-2),x(n-3),x2(n),x2(n-1),x2(n-2),x2(n-3),x(n)x(n-1),x(n-1)x(n-2),x(n-2)x(n-3),x(n)x(n-2),x(n-1)x(n-3),x(n)x(n-3).令z1(n)=x(n),z2(n)=x2(n),z3(n)=x(n)x(n-1),z4(n)=x(n)x(n-2),z5(n)=x(n)x(n-3),則可將以上14個抽頭信號分成5組G1=z1(n),z1(n-1),z1(n-2),z1(n-3)G

7、2=z2(n),z2(n-1),z2(n-2),z2(n-3)G3=z3(n),z3(n-1),z3(n-2)G4=z4(n),z4(n-G5=z5(n)1)可以看出分組的標準是同一組中的抽頭信號均為同一信號(此處為z1(n),z2(n),z5(n)中的某個)對應不同延遲量的延遲信號.分組的好處是十分明顯的,原來計算全部14個抽頭信號要10次乘法,而通過分組只需要4次乘法.因為現在只需要計算z2(n)=x2(n),z3(n)=x(n)x(n-1),z4(n)=x(n)x(n-2),z5(n)=x(n)x(n-3)4個抽頭信號,其他抽頭信號只是它們的延遲而已.可見分組有利于降低算法的復雜度.快速

8、算法的原理是:將Volterra濾波器的全部抽頭按上述方法分為若干組,每一組抽頭屬于一個橫向子濾波器,濾波器的輸出為各子濾波器輸出之和.因此分組對應Volterra濾波器的分解,這種分解的示意圖見圖1.要實現快速算法,就必須先進行分組.當Volterra濾波器的D,N都較小時,分組還能靠觀察完成.當D,N都較大時,必須有一種一般方法才行.208信息與控制25卷圖1快速算法原理示意4分組的一般方法及有關命題可以看出分組有以下特點:分成的組數一定不小于D;只有同一階次Volterra核對應的抽頭信號才有可能分在一組中.按以上特點,可采用“分而治之”的策略,對1D階核對應的抽頭信號分別進行分組,最后

9、綜合各階分組結果,即得總的分組.因一階分組的解是顯然的,所需考慮的僅是2D階的分組問題.令C=(k1,k2,kd) kiZ,0kiN-1,1id,C上的一個關系R定義如下:x,xxxyyyxyxyxyyC,x=(k1,k2,kd),y=(k1,k2,kd),xRyk1-k1=k2-k2=kd-kd.易知R是C上的等價關系,由R可導出C的一個等價類劃分P:C=U1U2UM,U1,UM為R的等價類.顯然i,j,1i,jij.M,UiUj=0x0x0定義1U是R的等價類,x0U,x0=(kx1,k2,kd)若滿足k1k1,kdkdxUx0xx0x則稱x0為U的最小元,記為xU.同樣可以定義最大元xU

10、.minmax對于R的等價類的最小元,其至少有一個坐標分量(ki)為0;對于最大元,其至少有一個坐標分量為N-1.UUUUxxx命題2關系R的一個等價類U中元素的個數為 U =kx1max-k1min+1=kdmax-kdmin+1結論為顯然.命題3集合C,關系R意義如前,則C中R的不同等價類個數為4期羅忠等:自適應Volterra濾波的一種快速算法d209M=i其中組合數Cd=(-i=1iN1)i+1Cdd-i=Nd-(N-1)ddi.證明我們給出一種幾何證明.C是d維向量空間Rd中的一個由整數點(即所有坐標分量均為整數的點)構成的邊長為N的超立方體.Rd中一條平行于該超立方體頂點(0,0,

11、0)和頂點(N-1,N-1,N-1)間對角線的直線若與超立方體相交,其交集(線段)即為關系R的一個等價類.考察圖2所示的d=2的情況可知,這樣的線段的一個端點必在超立方體的d個交于頂點(0,0,0)的面上.且所有線段上均平行.由此可知線段與這d之間存在一一對應關系.在圖2中,邊AB,ADAB與正方形中整數點個數之差為42-(4-1)2=7.N的d維ABCDd超立方體與邊長為N-1的d,即為Nd-(N-1)d=1)i+1(-i=1CNidd-i.性.(n-k1)x(n-kd)和x(n-l1)xn-ld)若(k1,kd)和(l1,ld)是同一組d個數的兩個不同排列,對于濾波問題它們是無法區(qū)分的.因

12、此還要將初步分成的組(即等價類)U1,U2,UM再進行合并和刪除重復元素后才能得到真正的分組.兩個關系R的等價類,若它們的最小元在輪換對稱意義上相同,則應合并到一個集合中,合并完所有等價類我們得到集合V1,V2,VL(L<M).對于各Vi還要將其內部所有在輪換對稱意義上相同的點保留一個而將其他刪除.經這一步,最后得到V1,V2,VL.從而可將d階抽頭信號按d圖2分組問題的幾何意義(d=2)如下方法分為L組Gi=x(n-kj) (k1,k2,kj)Ui,1iL.j=1命題4d(d2)階分組的組數為min(d-1,N)L=k=1CNCd-kk-12ii證明各Ui與其最小元xU.而xUmin之

13、間有一一對應關系min至少有一個坐標分量為0,因輪換對稱性,不妨認為其第一個坐標分量為0.求所有這樣最小元的個數等價于這樣一個組合數學問題:有d-1個相同的盒子,N種不同顏色的球且各色球都有至少d-1個.要求每盒僅放min(d-1,N)一球,求不同放法的總數.由組合數學知識可知,不同放法總數為k=1CNCd-2.證畢.kk-1快速算法執(zhí)行的程序如下(1)構造集合C并對其進行關于關系R的等價類劃分.等價類的確定方法已在命題3的證明中給出了.得到各等價類U1,U2,Um.210信息與控制25卷(2)將U1,U2,UM合并并作刪除重復元素的處理得到集合V1,V2,VL.(3)根據V1,V2,VL進行

14、抽頭信號分組.(4)d=d+1,若d>D,結束,否則重復(1)(3).5快速算法和原算法復雜度對比原算法的復雜度已由命題1給出.下面一個命題是關于快速算法的復雜度的.命題5快速算法完成一次迭代所需的加法和乘法次數分別為Dmin(j,N)kNNDa=2Cj=1k=1DkNCj-k-11min(j,N)min(d-N)Nm=3Cj=1k=1TCk-1j-1+d=k=Nk-1CN-k12證明由命題4可知分組數,由命題2,將各組中的抽頭信Din(,N)號個數相加,=k=1j-1.計算誤差e(n)時加法為NT次,更共需NT次,從而Na=2NT.計算e(n)時,乘法需NT次,所以更新全部系數需乘法2

15、NT次.計算一個d(d2)抽頭信號需乘法一次,d階抽頭信號的表達式x(n-k1)x(n-kd-1)x(n-kd)中,方括號中即為一個d-1階抽頭信號,所以這部分乘法不用做.所需一次乘法用于計算方括號D內結果與x(n-kd)相乘.從而計算各階抽頭信號所需的乘法次數為各階分組數之和為d=2表1快速算法和原算法一次迭代的乘法次數min(d-1,N)Dk=1CCkkNk-1d-2.綜上所述Nm=3NT+d=234547651156162min(d-1,N)2345k=1CNCd-2.證畢.k-1表1列出了不同D和N對應的兩種算法的乘法次數.欄中左邊數字對應快速算法,右邊數字對應原算法.由分析對比可見快

16、速算法的計算復雜度明顯低于原算法,因此快速算法是很成功的.因為分組工作是一次性的,其開銷可忽略不計.6Volterra濾波仿真實例考慮以下自適應建模問題.被建模系統為具有維納模型的非線性系統,其線性部分為G(z)=1 (1-0.8z-1)(1-0.7z-1),非線性特性為N(x)=1 (1+e-0.5x).我們采用D=2,N=4的Volterra濾波器作為自適應性模型.建模仿真結果如圖3所示.其中(a)是輸入為正弦信號時的系統與模型的輸出;(b)是兩個自適應系數h1(0),h2(0,0)的學習過程曲線.7結論我們針對Volterra濾波現有算法計算量大的問題,利用對抽頭信號進行分組,建立了一種

17、快速算法.分析表明快速算法的計算復雜度顯著低于現有算法.下一個研究的問題是建立4期羅忠等:自適應Volterra濾波的一種快速算法211(a)系統與模型的輸出(b)自適應參數學習過程圖3Volterra濾波用于建模的仿真結果Volterra格型濾波器的快速算法,1BellafeminaM,etal.NonlinearChannelsforDigitalTransmission.ProcIEEEInt1480SympC,to,1985:14772Lucky.DetectionforDataTransmissionontheTelephoneChannel.InNewDirectionsinSig

18、nalProcessingunicationandControl,JKSkwirzynskied,LeidenHolland,Noordhoff,19753CokerMJ,etal.ANonlinearAdaptiveNoiseCanceller.Proceedingsofthe1980IEEEInternationalConferenceonA2473coustics,SpeechandSignalProcessing,1980:4704KenefieRJ,etal.ApplicationoftheVolterraFunctionalExpansionintheDetectionofNonl

19、inearFunctionsofGaussian279Processes.IEEETransonCommunications,1985,COM-33(3):2765KorenbergMJ,etal.TheIdentificationofNonlinearBiologicalSystems:LNLCascadeModels.BiologicalCybernetics,1986,55:125134626MathewsVJ.AdaptivePolynomialFilters.IEEESignalProcessingMagazine,1991:107焦李成.非線性傳遞函數理論與應用.西安:電子科技大學出版社,1992:147AFASTALGORITHMOFADAPTIVEVOLTERRAFILTERINGLUOZhongXIEKainianLIUWenjiang(DepartmentofAutomaticControl,XianJiaotongUniversity)AbstractTheVolterrafilteringisaneffectivemet