序列的卷積和快速卷積運算的編程實現(xiàn)

1、 TOC o 1-5 h z HYPERLINK l bookmark3 o Current Document 1 Mat lab軟件介紹1 HYPERLINK l bookmark18 o Current Document 2項目設計目的及技術要求 3 HYPERLINK l bookmark24 o Current Document 3原理簡介4 HYPERLINK l bookmark27 o Current Document 3.1基本概念4 HYPERLINK l bookmark30 o Current Document 3.2原理分析4 HYPERLINK l bookmark3

2、3 o Current Document 3.2.1離散傅里葉變換（DFT）和快速傅里葉變換（FFT） 4 HYPERLINK l bookmark36 o Current Document 3.2.2序列的卷積和快速卷積運算5 HYPERLINK l bookmark39 o Current Document 3.2.3快速傅里葉變換和快速卷積5 HYPERLINK l bookmark42 o Current Document 4程序設計及仿真結果分析6 HYPERLINK l bookmark45 o Current Document 4.1題目一6 HYPERLINK l bookma

3、rk48 o Current Document 題目二7 HYPERLINK l bookmark61 o Current Document 題目二9 HYPERLINK l bookmark64 o Current Document 5 心得體會13 HYPERLINK l bookmark67 o Current Document 6參考文獻141 Matlab軟件介紹MMATLAB是矩陣實驗室(Matrix Laboratory)的簡稱，是美國MathWorks公司出品 的商業(yè)數(shù)學軟件，用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計算的高級技術計算 語言和交互式環(huán)境，主要包括MATLAB和

4、Simulink兩大部分。MATLAB是由美國mathworks公司發(fā)布的主要面對科學計算、可視化以及交互式程序設 計的高科技計算環(huán)境。它將數(shù)值分析、矩陣計算、科學數(shù)據(jù)可視化以及非線性動態(tài)系統(tǒng) 的建模和仿真等諸多強大功能集成在一個易于使用的視窗環(huán)境中，為科學研究、工程設 計以及必須進行有效數(shù)值計算的眾多科學領域提供了一種全面的解決方案，并在很大程 度上擺脫了傳統(tǒng)非交互式程序設計語言(如。、Fortran)的編輯模式，代表了當今國際科 學計算軟件的先進水平。MATLAB和Mathematica、Maple并稱為三大數(shù)學軟件。它在數(shù)學類科技應用軟件中在數(shù)值計算方面首屈一指。MATLAB可以進行矩陣

5、運算、繪 制函數(shù)和數(shù)據(jù)、實現(xiàn)算法、創(chuàng)建用戶界面、連接其他編程語言的程序等，主要應用于工 程計算、控制設計、信號處理與通訊、圖像處理、信號檢測、金融建模設計與分析等領 域。MATLAB的基本數(shù)據(jù)單位是矩陣，它的指令表達式與數(shù)學、工程中常用的形式十分相似，故用MATLAB來解算問題要比用C，F(xiàn)ORTRAN等語言完成相同的事情簡捷得多， 并且MATLAB也吸收了像Maple等軟件的優(yōu)點，使MATLAB成為一個強大的數(shù)學軟件。在 新的版本中也加入了對。，F(xiàn)ORTRAN，C+，JAVA的支持?？梢灾苯诱{用，用戶也可以 將自己編寫的實用程序導入到MATLAB函數(shù)庫中方便自己以后調用，此外許多的MATLAB

6、 愛好者都編寫了一些經(jīng)典的程序，用戶可以直接進行下載就可以用。MATLAB產(chǎn)品族可以用來進行以下各種工作：數(shù)值分析數(shù)值和符號計算工程與科學繪圖控制系統(tǒng)的設計與仿真數(shù)字圖像處理技術數(shù)字信號處理技術通訊系統(tǒng)設計與仿真（8）財務與金融工程MATLAB的應用范圍非常廣，包括信號和圖像處理、通訊、控制系統(tǒng)設計、 測試和測量、財務建模和分析以及計算生物學等眾多應用領域。附加的工具箱（單獨提 供的專用MATLAB函數(shù)集）擴展了MATLAB環(huán)境，以解決這些應用領域內特定類型的 問題。它的主要特點是：（1）Matlab可以用來解線性方程組、進行矩陣變換與運算、數(shù)據(jù)插值運算等，能使用 戶從繁雜的數(shù)學運算分析中解脫

7、出來。（2）Matlab中有許多高級的繪圖函數(shù)，包括二維、三維、專用圖形函數(shù)、圖形句柄、 用戶圖形界面工具等，利用這些函數(shù)可以輕松地完成各種圖形的繪制和編輯工作，實現(xiàn) 計算結果和編程的可視化。（3）友好的用戶界面及接近數(shù)學表達式的自然化語言，使學習者易于學習和掌握。（4）功能豐富的應用工具箱（如信號處理工具箱，通信工具箱，控制系統(tǒng)工具箱等） 為用戶提供了大量方便實用的處理工具。Matlab的上述特點，使它深受工程技術人員及科技專家的歡迎，并很快成為應用學 科計算機輔助分析、設計、仿真、教學等領域不可缺少的基礎軟件。目前，國內很多理工 院校已經(jīng)或者正在把該軟件作為學生必須掌握的一種軟件。2項目設

8、計目的及技術要求序列的卷積和快速卷積運算的編程實現(xiàn)，具體包括：直接卷積及運用、快速卷積方法 及實現(xiàn)、二者的比較分析等。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.用函數(shù)conv和FFT計算長為1000序列的卷積片(比較其計算時)間。3.用快速卷積法計算x(n)?；騌 (n)和n兩個序列的卷積；并 測試直接卷積和快速卷積的時間。3原理簡介3.1基本概念在數(shù)字信號處理(DSP)系統(tǒng)中，無論在時域或頻域都離不開卷積運算和快速傅里葉 (FFT)運算。Matlab具有強大的矩陣運算

9、能力，方便實用的繪圖功能和語言的高度集成性， 在DSP開發(fā)中，使用Matlab可以快速對系統(tǒng)進行仿真運算。設輸入信號為x(t)，其頻譜函數(shù)為X(jQ )，該信號通過濾波器h(t)后，其輸出信號y(t)的 頻譜函數(shù)Y(jQ )是頻譜函數(shù)x(jQ )與濾波器的頻譜函數(shù)H(jQ )的乘積，即：K (jQ) = X (jQ) H (jQ)而在時域，輸出信號y(t)實際是輸入信號x(t) 與濾波器h(t)的卷積。就是說頻譜函數(shù) 的乘積相當于時間函數(shù)的卷積，反之亦然。即：y(t) = x(t) * h(t) = j x(t )h(t -T )dT8由于DSP主要依靠計算機完成，而計算機無論在時域或頻域只能

10、處理有限長的離散信 號，因此上述關系可表示為：Y (o) = X (o) H (o)y (n)= 丈5 x(m)h(n - m) = x(n) * h(n)m=8式中：n表示離散時間；數(shù)字頻率3 = QT； f為輸入信號頻率；f,T為抽樣頻率和周期。3.2原理分析可以使用線性卷積、圓周卷積實現(xiàn)離散卷積，也可以根據(jù)時域信號函數(shù)與頻譜函數(shù)的 關系，使用快速傅里葉變換(FFT，IFFT)實現(xiàn)離散卷積。3.2.1離散傅里葉變換(DFT)和快速傅里葉變換(FFT)離散傅里葉變換，是連續(xù)傅里葉變換在時域和頻域上都離散的形式，將時域信號的 采樣變換為在離散時間傅里葉變換頻域的采樣。在形式上，變換兩端(時域和

11、頻域上) 的序列是有限長的，而實際上這兩組序列都應當被認為是離散周期信號的主值序列。即 使對有限長的離散信號作DFT，也應當將其看作經(jīng)過周期延拓成為周期信號在做變換。在 實際應用中通常采用快速傅里葉變換（FFT）高效計算DFT。采用這種算法能使計算機計 算離散傅里葉變換所需要的乘法次數(shù)大為減少，特別是被變換的抽樣點數(shù)N越多，F(xiàn)FT算 法計算量的節(jié)省就越顯著。3.2.2序列的卷積和快速卷積運算卷積是數(shù)字信號處理中最常見的，也是最重要的運算之一。利用卷積可以實現(xiàn)相關計 算和FIR濾波等等，正因為卷積如此重要，所以半個世紀以來，學者們提出了多種不同卷 積實現(xiàn)結構，這些結構各有優(yōu)點，針對不同應用可以靈

12、活選擇，而其中快速卷積無疑是 重要的卷積方法之一。顧名思義，快速卷積重點在一個“快”，如果對卷積速度要求較 高，快速卷積無疑是理想的工具。當然，為了提高速度，就要犧牲面積和功耗。3.2.3快速傅里葉變換和快速卷積在此，我們是利用快速傅里葉變換實現(xiàn)快速卷積運算。同時在進行Matlab編程時也是 利用快速傅里葉變換來得到快速卷積的結果。4程序設計及仿真結果分析4.1題目一長度為m的向量序列h和長度為n的向量序列x,卷積w的向量序列長度為(m+n-1), 當m#n時,應以0補齊階次低的向量的高位后進行計算y(1) = h1)*x(1)y(2) = h(1)*x(2)+h(2)*x(1)y(3) =h

13、(1)*x(3)+h(2)*x(2)+h(3)*x(1)= 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)那么所得的結果就是y (n) =6,14,25,36,63,50,55,52,28,10用matlab仿真編程程序如下：h=6,2,3,6,4,2;x=1,2,3,4,5;y=conv(h,x);stem(y)圖4.1.1編程得到的系統(tǒng)輸出函數(shù)y(n)由圖4.1.1可和自己求出的y(n)函數(shù)相比較可以得到，用matl

14、ab編寫程序得出的系統(tǒng) 輸出函數(shù)與自己人工計算的結果相同。4.2 題目二在matlab實現(xiàn)卷積的.函數(shù)為CONV，對于N值較小的向量，這是十分有效的。對于N值 較大的向量卷積可用FFT加快計算速度。若DFT和IDFT均采用FFT和IDFT算法，可提高卷積速度。計算x1(n)和x2(n)的線性卷積的FFT算法可由下面步驟實現(xiàn)：1、計算X1(k)=FFTx1(n);2、計算X2(k)=FFTx2(n);3、Y(k)=X1(k) X2(k);4、計算 x1(n)Xx2(n)=IFFTY(k)在本題目中計算的兩個函數(shù)分別是x1(n)=2*10An,x2(n)=cos(nA3) o用matlab編寫的完

15、整程序如下所示L=1000;N=L*2-1;n=1:L;x1=2*(n.A10)；x2=cos(n.A3);t0=clock;yc=conv(x1,x2);conv_time=etime(clock,t0)t0=clock;yf=ifft(fft(x1,N).*fft(x2,N);fft_time=etime(clock,t0)subplot(221),stem(xn,.);ylabel(x(n);subplot(222),stem(hn,.);ylabel(h(n);subplot(212),stem(real(yc),.);ylabel(y(n);在matlab中編程以及得出的完成程序所需

16、要的時間如下所示：菸 L=1000;N=L+2-l;n=lL;Kl=+(n. 10;K2=cos,(n. 3);tO=clock;yc=convCKlj x2);conv_t ime=et imeclockj 10)t0=clock:yf=ifft (fft fxUNh 蛙ft 俄幻 10。;fft_time=etime(clocks 10)subplot (221)j.st em (xl,. ,：4ylabel x：(n)f subplot (222)j st em (x2j . ) ;ylabelC h (n) 0 : subplot (212)j.st em(real (yc)j.) ；

17、ylabel (? y (n)conv_time 二0.0150fft_time 二1 matlab中完整的編程程序以及輸出的結果0.50-0.5-15001-1圖4.2.2|coqv函數(shù)結果yc和FFT結果yfA該題要求的是對用函數(shù)conV和FFT計算1堿點的序列卷積所需的時間進亍對比，通過121000圖4.2. 1可知，用函數(shù)conv計算該卷積需要0.0150s，而用FFT計算該卷積需要0s,由此可以 得出：FFT算法所消耗的時間遠小于函數(shù)conv要消耗的時間。4.3 題目三利用快速卷積原理求兩個函數(shù)的卷積可以用題目二中所用的方法(先分別對兩個函數(shù) 求傅里葉變換得到X(k)與須口，再兩個函

18、數(shù)傅里葉變換的點乘的結果y(k)，最后直接對y(k)兩個函數(shù)中M與N沒有給求傅里葉反變換得到y(tǒng)(n)快速卷積，得到所要求的#結果。/、 因為在這次題目中、()=.9氣與仞)=七()出，所以本人就分別取M=40，N=30以及M=1500，N=1200兩組數(shù)分別求該題目說得到結果。兩組數(shù)所用的程序以及各自的輸出結果如下所示簫 kr=O. 9. (1:40);hn=l. (1:30):tic;yrKsn*-(立烏 比0 ;toe;L=pow2(nestpow2(40+30-1);ticKk=fft(zn, L);hk=fft (hn,L)yk=Kk. ：hk;yn=ifft L);toe;ubp 1

19、 ot.(2 1em (xn . )-：labelf z (n) )*subplot(222) , st cm (hrij ,? j jylabel h(n);ubp 1 ot.t212), ny= 1:L ; stem(real (yn)s . ) j-label (? y(n)-Elapsed time ig 0. 001237 seconds.Elapsed time is 0. 00S753-.seconds.圖4.3.1取第一組數(shù)時所用的程序以及得出的結果繁 kr=0. 9. (1: 1500.-.;hn=l. (1:1200);tic;yn=conv hn);toe.;L=pow2(n&Ktpow2(1500+1200-1);ticsk=fft (zn, L);hk=fft (hn, L);yk=Kk. ,*hk;yn=ifft &虬 L);toe;subplot (221) 5 st em ?) ;jflabel C k ?n),7 ；subplot C222j/st emfhrLj . J； ; ylabel f h(n)?);subplot(21