快速卷積的MATLAB實現(xiàn)

1、摘 要 在信號處理中，許多具體的應用是以線性卷積為基礎的。當序列點數(shù)較少時可以直接計算線性卷積，然而當序列長度很長時，直接計算卷積的運算量非常龐大?？焖倬矸e是實現(xiàn)卷積的一種快速算法，減少了運算量，節(jié)約了時間，給我們計算卷積提供了很大的便利。本課程設計是以Matlab為基礎，完成序列的卷積和快速卷積運算的編程實現(xiàn)，以及相應的分析和比較。關鍵字：Matlab 卷積 快速卷積目 錄1.基于設計題目的原理簡介11.1 序列卷積的定義11.2 快速傅里葉變換FFT概念11.3 快速卷積方法及實現(xiàn)12.程序設計及運行結果分析32.1 題目一32.2 題目二42.3 題目三73.心得體會10參考文獻11專業(yè)

2、綜合課程設計成績評定表121. 基于設計題目的原理簡介 卷積是數(shù)字信號處理（DSP）系統(tǒng)中最常見的，也是最重要的運算之一，無論在時域或頻域都離不開卷積運算，F(xiàn)FT是DFT的快速算法，當滿足一定條件時可用來計算線性卷積，稱為快速卷積。Matlab具有強大的矩陣運算能力，方便實用的繪圖功能和語言的高度集成性，在DSP開發(fā)中，使用Matlab可以快速對系統(tǒng)進行仿真運算。1.1 序列卷積的定義設x(n)和h(n)是兩個離散序列，進行下列求和運算： 這樣，隨著n的不同取值，這個求和公式就定義了一個新序列y(n)，稱為序列x(n)與h(n)的卷積，記為y(n)=x(n)*h(n) 。 由于DSP主要依靠計

3、算機完成，而計算機無論在時域或頻域只能處理有限長的離散信號。此時只需令上述公式中的n在一個范圍內取值即可。1.2 快速傅里葉變換FFT概念DFT就是對序列頻譜的離散化，在數(shù)字信號處理中有著重要的作用，但直接計算DFT的運算量非常大，它與序列長度的平方成正比，因此制約了DFT的應用。快速傅里葉變換FFT是實現(xiàn)DFT的一種快速算法，能使計算機計算離散傅里葉變換所需要的乘法次數(shù)大為減少，特別是被變換的抽樣點數(shù)N越多，F(xiàn)FT算法計算量的節(jié)省就越顯著。因而FFT也有重要的作用，下面一節(jié)要介紹的快速卷積就是其應用之一。1.3 快速卷積方法及實現(xiàn)在信號處理中，許多具體的應用是以線性卷積為基礎的。我們知道，當

4、滿足一定條件(LM+N-1)時，可以用圓周卷積來計算線性卷積。由圓周卷積定理知道，圓周卷積可以借助DFT來運算，因此DFT的快速算法FFT就可以用來計算線性卷積。設x1(n)與x2(n)分別是長度為N與M的有限長序列，它們的線性卷積為yl(n)，L點的圓周卷積為yc(n)，它們的關系為: yc(n)=yl(n+rL)RL(n)快速卷積算法過程的示意圖如圖1.1所示。在實際應用中，常遇到的問題是參加卷積的兩個序列的長度相差較大，這樣長度小的序列就需補很多的零點，這樣就需要大的存儲量，運算時間也會變長。常用的解決方法有兩種，一是重疊想加法，另一種是重疊保留法。這里不作介紹。 圖1.1 快速卷積示意

5、圖1.4 直接卷積和快速卷積分析比較快速卷積，顧名思義，其重點在一個“快”，如果對卷積速度要求較高，快速卷積無疑是理想的工具。當然，為了提高速度，就要犧牲面積和功耗。而且由上一節(jié)的介紹可知，快速卷積運算的步驟較多，因而當序列較短時快速卷積運算并沒有優(yōu)勢，直接進行卷積運算反而更簡便。卷積計算的方法選擇要視實際情況而定。2.程序設計及運行結果分析2.1 題目一 已知線性非移變系統(tǒng)的h(n)=6,2,3,6,4,2，輸入為x(n)=1,2,3,4,5；（1）用人工計算系統(tǒng)輸出y(n)；（2）編寫程序輸出y(n)，并作圖。2.1.1 人工計算長度為N=6的序列h(n)和長度為M=5的序列x(n)，卷積

6、y(n)的序列長度為(M+N-1)=10， 計算過程如下：    y(1) = h(1)x(1) =6      y(2) = h(1)x(2)+h(2)x(1) =14       y(3) =h(1)x(3)+h(2)x(2)+h(3)x(1) = 25       

7、;        y(n) = h(1)x(n)+h(2)x(n-1)+  +h(n)x(1)                y(M+N-1) = h(1)x(M+N-1)+h(2)x(M+N)+h(3)x(M+N+1)+h(M+N-1)x(1) =10所得的結果為y(n)= 6，14，25，36，

8、63，50，55，52，28，10。2.1.2 程序設計在Matlab中實現(xiàn)卷積的函數(shù)conv，可以直接調用。設計程序如下：h=6,2,3,6,4,2; x=1,2,3,4,5; y=conv(h,x); %調用conv函數(shù)直接計算線性卷積stem(y); %畫出卷積結果h(n)的序列圖title('y(n)') 2.1.3 運行結果及分析 程序運行后，得到的卷積結果y(n)如圖2.1所示。圖2.1 編程得到的卷積結果y(n) 由圖2.1可看出，編程得到的卷積結果序列y(n)與自己先前計算的結果相同，說明所設計的程序是正確的，得到了正確的結果。圖2.1 編程得到的卷積結果y(n

9、)2.2 題目二用函數(shù)conv和FFT計算長為1000序列的卷積，比較其計算時間。2.2.1 設計內容及原理分析 本題目的在于比較直接卷積和快速卷積的計算時間，分析其優(yōu)劣性。由1.3節(jié)可知快速卷積算法如下：（1）序列補零：將兩序列都補零到L點； （2）計算X1(k)=FFTx1(n)；（3）計算X2(k)=FFTx2(n)；（4）計算Y(k)=X1(k)X2(k)；（5）計算y(n)=x1(n)*x2(n)=IFFTY(k)。本題中已經給定兩原序列的長度M=N=1000，則LM+N-1，而因為快速卷積的基礎是FFT，所以要求L滿足L=2n，為減少運算量選取L=2048。設兩原序列分別

10、為： x1=0.5sin(2*n) ； x2=n3 計算時間的獲取方法為：計算前先調用clock函數(shù)讀取瞬時時鐘，待計算結束后，調用etime(t1，t2)函數(shù)計算時刻t1，t2間所經歷的時間。2.2.2 程序設計框圖圖2.2 程序設計框圖2.2.3 程序代碼N=1000;L=pow2(nextpow2(1000+1000-1); %計算L的值n=1:N;x1=0.5*sin(2*n); x2=n.3;t0=clock; %調用clock函數(shù)讀取瞬時時鐘yc=conv(x1,x2); %用函數(shù)conv計算卷積conv_time=etime(clock,t0) %調用etime函數(shù)計算時間t0=

11、clock;yf=ifft(fft(x1,L).*fft(x2,L); %用函數(shù)FFT計算卷積fft_time=etime(clock,t0)subplot(321),stem(x1,'.');ylabel('x1(n)');subplot(322),stem(x2,'.');ylabel('x2(n)');subplot(312);stem(real(yc),'.');ylabel('直接卷積y(n)');subplot(313);stem(real(yf),'.');ylabel

12、('快速卷積y(n)');2.2.4 運行結果及分析用函數(shù)conv和FFT計算長為1000序列的卷積的結果如圖2.3，計算時間如圖2.4?？梢钥闯觯瑑煞N方法所計算出的卷積結果是一樣的。再來看時間，用函數(shù)conv計算該卷積需要0.0070s，而用FFT計算該卷積需要0s。由此可以得出，當序列長度為1000時，F(xiàn)FT算法所消耗的時間遠小于函數(shù)conv要消耗的時間。圖2.3 函數(shù)conv和FFT計算長為1000序列的卷積的結果圖2.4 函數(shù)conv和FFT的計算時間2.3 題目三用快速卷積法計算和兩個序列的卷積；并測試直接卷積和快速卷積的時間。2.3.1 設計內容及原理分析 用快速卷

13、積計算兩個序列卷積的方法與題目二中的一樣，區(qū)別僅在于序列的長度沒有給出，這里不再重復計算過程。為了做對比分析，兩個原序列的長度M和N取兩組值進行仿真，分別取M=50，N=46和M=800，N=1000。2.3.2 程序設計框圖程序設計框圖與題目二一樣，如圖2.2所示。2.3.3 程序代碼xn=0.9.(1:800);hn=1.(1:1000);L=pow2(nextpow2(800+1000-1); %計算L值 tic;yc=conv(xn,hn); %直接計算卷積toc; %計算時間tic;Xk=fft(xn,L); %求x(n)的快速傅里葉變換X(k)Hk=fft(hn,L); %求h(n

14、)的快速傅里葉變換H(k)Yk=Xk.*Hk; %求Y(k) yf=ifft(Yk,L); %用IFFT求快速卷積yftoc; %計算時間subplot(221),stem(xn,'.');title('x(n)');subplot(222),stem(hn,'.');title('h(n)');subplot(212),ny=1:L;stem(real(yf),'.');title('快速卷積y(n)');2.3.4 運行結果及分析（1） M=50，N=46 卷積結果及計算時間分別如圖2.5和圖2

15、.6所示（直接卷積的計算時間在上，快速卷積的計算時間在下）。圖2.5 M=50，N=46時的快速卷積圖2.6 M=50，N=46時的計算時間（2） M=800，N=1000 卷積結果及計算時間分別如圖2.7和圖2.8所示（直接卷積的計算時間在上，快速卷積的計算時間在下）。圖2.7 M=800，N=1000時的快速卷積圖2.8 M=800，N=1000時的計算時間 可以看出，當M=50，N=46時，快速卷積的計算時間比直接卷積的要長；而當M=800，N=1000時，快速卷積的時間更短。這說明：當序列的點數(shù)比較少時，快速卷積并不占有優(yōu)勢，所用時間反而比直接卷積長，只有在序列較長時，快速卷積才體現(xiàn)出

16、“快”的優(yōu)勢。3.心得體會本次課程設計我的題目是序列的卷積和快速卷積運算的編程實現(xiàn)，因為我們已經學習過信號與系統(tǒng)和Matlab應用實踐課程，對序列的卷積和Matlab仿真并不陌生；而且此次題目卷積和快速卷積在課本上能找到相關的內容，老師在授課時已經講得很詳細，我對這部分的內容也比較熟悉。所以這次課程設計做的比較順利，沒有遇到什么大的難題，只是有一些小的細節(jié)影響了設計的進程，比如函數(shù)名的拼寫等。這讓我體會到，即使是比較容易的事情時，在對待它時也要很認真仔細，就像我們常說的：細節(jié)決定成敗。數(shù)字信號處理是本專業(yè)的一門重要課程，與它相關性最強的軟件就是Matlab，這次課程設計給我提供了一個用Matlab實現(xiàn)序列卷積和快速卷積的機會，通過編程得到了和理論一致的結果。不僅加深了我對序列卷積和快速卷積這部分內容的理解，而且提高了我的程序編寫和糾錯能力，也進一步熟悉了Matlab的操作。但這是遠遠不夠的，卷積只是數(shù)字信號處理中比較簡單的一部分，這門課程還有許多值得我們去實踐和探究的地方，我現(xiàn)在的目標就是在假期將本課程其它幾個課設題目都操作一遍，以進一步提升自己各方面的能力。作為一名電子信息工程專業(yè)的學生，熟練掌握相關軟件的操作是一門必修課，否則就算理論知識學得再好，不會應用，也只是紙上談兵，不會真正取得什么成果，畢業(yè)之后在工作上也會很吃力。而我們并沒有專門的課程來學