含源代碼北郵dsp MATLAB實驗一重疊相加和重疊保留

1、【含源代碼】北郵ds P-MATLAB實驗一重疊相加和重疊保留Dsp-matlab實驗課題名稱:學生姓名:級:班內(nèi)序號: 學 號:日 期:2015/06/15實驗一:重疊相加法和重疊保留法的實現(xiàn)POSTSPOSTS、實驗原理.二、Matlab源代碼三、Matlab運行結(jié)果四、Matlab結(jié)果分析五、遇到的難題與解決方法參考文獻目錄一、實驗原理1、算法來源DFT是連續(xù)傅里葉變換在時域和頻域上都離散 的形式，將時域信號的采樣變換為在離散時間傅 里葉變換頻域的采樣。 在形式上， 變換兩端(時 域和頻域上)的序列是有限長的。DFT具備明確 且合理的物理含義，適合應(yīng)用于數(shù)字系統(tǒng)，同時 可以方便地由計算機

2、進行運算。對于線性非移變離散系統(tǒng)，可由線性卷積表示時 域輸入輸出關(guān)系，即x(n )*h( n)=y( n)通常采用循環(huán)卷積降低運算量，但實際中往往無 法滿足對信號處理的實時性要求。 因此，產(chǎn)生了 重疊相加法和重疊保留法兩種典型的算法， 用以 快速計算線性卷積，成為了DFT的一個重要應(yīng) 用。2、兩種算法基本思想1)重疊相加法重疊相加法和重疊保留法的實質(zhì)都是以逐段地 方式通過循環(huán)卷積來完成線性卷積的計算。 將輸 入序列x(n)進行分段，每段長為N,且NM( MIA A ,(/f,(/f 為有限長因果序列h(n)的長度)，x(n)逐段 與h(n)進行循環(huán)卷積，在重疊保留法中需在x(n)序列首部加入長

3、度為M-1的0序列。 在算 法中，在獲得N個點的輸入后，進行N+M-1點循 環(huán)卷積計算，之后輸出N個點。通過for循環(huán)逐 段進行循環(huán)卷積，使用fft和ifft計算兩個有 限長序列的N點循環(huán)卷積結(jié)果。重疊相加法是將待過濾的信號分割成長為N的 若干段，如圖1所示，每一段都可以和有限時寬 單位取樣響應(yīng)作卷積，再將過濾后的各段重疊相 加。每次輸入N點序列，通過計算x(n)和h(n)的循 環(huán)卷積實現(xiàn)線性卷積運算，將緩存的M-1點序列 和卷積結(jié)果相加，并輸出前N點作為計算結(jié)果， 同時緩存后M-1點，如此循環(huán)，直至所有分段計 算完畢，則輸出序列y(n)為最終計算結(jié)果。2N-12N-1 2N2N.fl- *

4、% N-1N-1 N NJ cAL點播壞專#處A AL=N+M1L=N+M1hghg圖Z Z *4*4栢加法算法示意圖2)重疊保留法重疊保留法相當于將X*?和h(?作循環(huán)卷積，然后找出循環(huán)卷積中相當于線性卷積的部分。在這種情況下，將序列y(n)分為長為N的若干段(如圖3所示)，每個輸入段和前一段有M-1個重 疊點。此時只需要將發(fā)生重疊的前M-1個點舍 去，保留重疊的部分并輸出，則可獲得序列y(n)， 算法如圖4所示。DMDM點維右I I A A心e e 4141點- -STST N N A Aynyn+-ILIIIIv,v, 1ff1ff) )Matlab源 代碼- 1 1I+N-1I+N-1

5、 盤碼環(huán)%根I I啟 N NI I點 hghgffi 4.晝堆探留衛(wèi)*法示廈圖重疊相加法源代碼fun cti onY=over pl xqy(x,h,N)% %利用循環(huán)卷積計算線性卷積 % %循環(huán)卷積采用頻域計算方法A=x(k*N+1:k*N+N);y1=fft(A,Lx+M-1);%y2=fft(h,Lx+M-1);y3=yl.*y2；% %頻域相乘Y(k*N+1:k*N+M-1)=q(1:M-1)+t(1:M-1);Y(k*N+M:k*N+N)=q(M:N); t(1:M-1)=q(N+1:N+M-1);end1)重疊相加法q=ifft(y3,Lx+M-1);%FF反變換得循環(huán)卷積結(jié)果,

6、,已 FFTFFT 弋替 DFTDFT 降低運算量Lx=le ngth(x); % M=length(h); %hx=x,zeros(1,N-1);t=zeros(1,M-1);Y=zeros(1,Lx+M-1);a=floor(Lx/N);for k=0:a序列長度(n)長度利用FFT進行運算Y(1:Lx+M-1);% %取出最終的輸出序列重疊保留法源代碼fun cti onY=overl psav(x,h,N)Lx=le ngth(x);M=le ngth(h);M1=M -1;L=N-M1;h=h,zeros(1,N-M); x=zeros(1,M1),x,zeros(1,N-1); a

7、=floor (Lx+M1-1)/(L)+1;Y=zeros(1,N);for k=0:a-1xk=x(k*L+1:k*L+N); b=fft(xk,N); C=fft(h,N);Z=b.*C;1)重疊保留法Y(k+1,:)=ifft(Z,N);%FFT反變換得循環(huán)卷積結(jié)endY=Y(:,M:N);陋出最終的輸出序列Y=(Y(:)Matlab運行結(jié)果m m frofro IMATIAB?IMATIAB? & & rttauftftrttauftft forfor血rttdLrttdLSpSp9,5 5 0,5,1,90,5,1,9 lTf=ll,Qj-lTf=ll,Qj- Jf

8、cr5Jfcr5pvTpbtqjpvTpbtqj fiTafiTa 1 1 MiMi3ns =曲t t】*轅電山5*5* InIn和辰*弓h(huán) h IfIf-P-P 4 4fl-fl-上QWOQWO -#-# 44004400-.C-.C 0 0由此可見，兩種算法運行正常，計算正確。更多的測試也正確。算法正確。四、Matlab結(jié)果分析重疊相加算法具有可行性和實用性。再從算法的空間復(fù)雜度來看，由空間復(fù)雜度為 0(1)0(1)。t列畑、A A101010010010001000100001000010100 0 0131510131510.00026b0.00026b0.018930.018930

9、0 0273780273780,074Si40,074Si41001000.0011730.0011730,0000,0000.0003190.0003190,0009170,0009170,0100070,01000710001000O.OOQ936O.OOQ9360,0025240,0025240.0009?0.0009?0,0007460,0007460.010.01 A927A92710000100000.0741810.0741810.0271210.0271210.0066fi20.0066fi20;004060;00406O.O(m23O.O(m23100000100000O.6

10、O693JO.6O693J0.2654760.2654760.05285i0.05285i0.0301060.0301060.0482450.048245lOOOOOOlOOOOOO6.0J35286.0J35282.48352G2.48352G0.3962060.3962060.2460520.2460520,333870,33387100000001000000059.9377659.9377625.1046625.104663,8974443,8974442.3281222.3281223.2314993.231499可以看出，同重疊相加法類似，隨著數(shù)據(jù)規(guī)模的增大，運算耗時呈線性增長，算

11、法的時間復(fù)雜度為 0(n)0(n)，其中 n n 為數(shù)據(jù)規(guī)模。同樣由于分配的緩存空間只由分段長度確定, 空間復(fù)雜度為 0(1)0(1)。綜合考察，重疊保留法也具有較好的時間和空間復(fù)雜度。LflMOLflMOS.S. dOOCdOOC-3-0000-3-0000-9.-9. OOOOOOOO -I.-I. OOQOOOQOkODOOkODOO4.4. 00000000-I.-I. OOGDOOGD -9x0-9x0DOODOO1.1. e e ; ; flfl1 1-J.fliMft-J.fliMft Y,Y, dgcjdgcjI I咖0 014.14. o o d d - - -kooOfl-

12、kooOfl -ifl.oww-ifl.owwHJLflosiflosi臥(HKOH-H- OWdOWd -l-OMO-l-OMO -LS-LS- 0 0 W W -fl-flMJ-fl-flMJ OLflWOOLflWOx(n)長度為N,y(n)長度為M;計算線性卷積y(n),y(n)可視為N個序列的 疊加結(jié)果，序列長度為M，所以每生成一個序 列需完成M次乘法，共需完成MN次乘法運算。這N個序列依次向右移動一位故需(N-1) (M-1) 次加法運算。按照fft和ifft計算線性卷積時，設(shè)L=N=M-1,整個運算過程包含了法運算，所以，按基ifft，共需完成(3Llog2L)次加法運算。7 尊

13、K摩4 4101010010010001000100001000010100,0005120,0005120,0002250,0002250.0012490.001249o.oooesio.oooesi0.0084540.0084541001000.0010140.0010140-0005140-0005140.0002720.000272ooooejbooooejbQ0G&Q2Q0G&Q2100010000,0092970,0092970.0024O20.0024O20.0007370.0007370,0006870,0006870-0111070-0111071000010

14、0000.056740.0567400?319400?31940.00512?0.00512?0.0039410.003941ooiioaaooiioaa1000001000000.5588650.5588650.5168180.5168180.03917S0.03917S0.026(X40.026(X40,0426430,0426435.2210795.2210793.1440393.144039035742803574280.2362770.2362770.3275390.3275392個fft、一個ifft和L次乘2頻域抽選算法實現(xiàn)fft或100000001000000052.246452.246422,0221522,022153.W32823.W