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

..1.MATLAB簡(jiǎn)介MATLAB軟件由美國(guó)MathWorks公司于1984年推出,經(jīng)過(guò)不斷的發(fā)展和完善,如今己成為覆蓋多個(gè)學(xué)科的國(guó)際公認(rèn)的最優(yōu)秀的數(shù)值計(jì)算仿真軟件。MATLAB具備強(qiáng)大的數(shù)值計(jì)算能力,許多復(fù)雜的計(jì)算問(wèn)題只需短短幾行代碼就可在MATLAB中實(shí)現(xiàn)。作為一個(gè)跨平臺(tái)的軟件,MATLAB已推出Unix、Windows、Linux和Mac等十多種操作系統(tǒng)下的版本,大大方便了在不同操作系統(tǒng)平臺(tái)下的研究工作。MATLAB軟件具有很強(qiáng)的開(kāi)放性和適應(yīng)性。在保持內(nèi)核不變的情況下,MATLAB可以針對(duì)不同的應(yīng)用學(xué)科推出相應(yīng)的工具箱<toolbox>,目前己經(jīng)推出了圖象處理工具箱、信號(hào)處理工具箱、小波工具箱、神經(jīng)網(wǎng)絡(luò)工具箱以及通信工具箱等多個(gè)學(xué)科的專用工具箱,極大地方便了不同學(xué)科的研究工作。國(guó)內(nèi)已有越來(lái)越多的科研和技術(shù)人員認(rèn)識(shí)到MATLAB的強(qiáng)大作用,并在不同的領(lǐng)域內(nèi)使用MATLAB來(lái)快速實(shí)現(xiàn)科研構(gòu)想和提高工作效率。MATLAB提供了20類圖像處理函數(shù),涵蓋了圖像處理的包括近期研究成果在內(nèi)的幾乎所有的技術(shù)方法,是學(xué)習(xí)和研究圖像處理的人員難得的寶貴資料和加工工具箱。這些函數(shù)按其功能可分為:圖像顯示;圖像文件I/O;圖像算術(shù)運(yùn)算;幾何變換;圖像登記;像素值與統(tǒng)計(jì);圖像分析;圖像增強(qiáng);線性濾波;線性二元濾波設(shè)計(jì);圖像去模糊;圖像變換;鄰域與塊處理;灰度與二值圖像的形態(tài)學(xué)運(yùn)算;結(jié)構(gòu)元素創(chuàng)建與處理;基于邊緣的處理;色彩映射表操作;色彩空間變換;圖像類型與類型轉(zhuǎn)換。MATLAB的應(yīng)用領(lǐng)域十分廣闊,典型的應(yīng)用舉例如下：<1>數(shù)據(jù)分析<2>數(shù)值與符號(hào)計(jì)算；<3>工程與科學(xué)繪圖；4>控制系統(tǒng)設(shè)計(jì)；<5>航天工業(yè)；<6>汽車工業(yè)；<7>生物醫(yī)學(xué)工程；8>語(yǔ)音處理；<9>圖像與數(shù)字信號(hào)處理；<10>財(cái)務(wù)、金融分析；<11>建模、仿真及樣機(jī)開(kāi)發(fā)；<12>新算法研究開(kāi)發(fā)；13>圖形用戶界面設(shè)計(jì)MATLAB的應(yīng)用范圍非常廣,包括信號(hào)和圖像處理、通訊、控制系統(tǒng)設(shè)計(jì)、測(cè)試和測(cè)量、財(cái)務(wù)建模和分析以及計(jì)算生物學(xué)等眾多應(yīng)用領(lǐng)域。附加的工具箱〔單獨(dú)提供的專用MATLAB函數(shù)集擴(kuò)展了MATLAB環(huán)境,以解決這些應(yīng)用領(lǐng)域內(nèi)特定類型的問(wèn)題。它的主要特點(diǎn)是：〔1Matlab可以用來(lái)解線性方程組、進(jìn)行矩陣變換與運(yùn)算、數(shù)據(jù)插值運(yùn)算等,能使用戶從繁雜的數(shù)學(xué)運(yùn)算分析中解脫出來(lái)?！?Matlab中有許多高級(jí)的繪圖函數(shù),包括二維、三維、專用圖形函數(shù)、圖形句柄、用戶圖形界面工具等,利用這些函數(shù)可以輕松地完成各種圖形的繪制和編輯工作,實(shí)現(xiàn)計(jì)算結(jié)果和編程的可視化?！?友好的用戶界面及接近數(shù)學(xué)表達(dá)式的自然化語(yǔ)言,使學(xué)習(xí)者易于學(xué)習(xí)和掌握?！?功能豐富的應(yīng)用工具箱<如信號(hào)處理工具箱,通信工具箱,控制系統(tǒng)工具箱等>為用戶提供了大量方便實(shí)用的處理工具。Matlab的上述特點(diǎn),使它深受工程技術(shù)人員及科技專家的歡迎,并很快成為應(yīng)用學(xué)科計(jì)算機(jī)輔助分析、設(shè)計(jì)、仿真、教學(xué)等領(lǐng)域不可缺少的基礎(chǔ)軟件。目前,國(guó)內(nèi)很多理工院校已經(jīng)或者正在把該軟件作為學(xué)生必須掌握的一種軟件。2.項(xiàng)目設(shè)計(jì)目的及技術(shù)要求序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn),具體包括：直接卷積及運(yùn)用、快速卷積方法及實(shí)現(xiàn)、二者的比較分析等。1． 已知線性非移變系統(tǒng)的h<n>=[6,2,3,6,4,2],輸入為x<n>=[1,2,3,4,5]；〔1 用人工計(jì)算系統(tǒng)輸出y<n>；〔2 編寫程序輸出y<n>,并作圖。2. 用函數(shù)conv和FFT計(jì)算長(zhǎng)為1000序列的卷積,比較其計(jì)算時(shí)間。3. 用快速卷積法計(jì)算和兩個(gè)序列的卷積；并測(cè)試直接卷積和快速卷積的時(shí)間。3.基本原理3.1基本概念在數(shù)字信號(hào)處理<DSP>系統(tǒng)中,無(wú)論在時(shí)域或頻域都離不開(kāi)卷積運(yùn)算和快速傅里葉<FFT>運(yùn)算。Matlab具有強(qiáng)大的矩陣運(yùn)算能力,方便實(shí)用的繪圖功能和語(yǔ)言的高度集成性,在DSP開(kāi)發(fā)中,使用Matlab可以快速對(duì)系統(tǒng)進(jìn)行仿真運(yùn)算。設(shè)輸入信號(hào)為x<t>,其頻譜函數(shù)為X<jΩ>,該信號(hào)通過(guò)濾波器h<t>后,其輸出信號(hào)y<t>的頻譜函數(shù)Y<jΩ>是頻譜函數(shù)x<jΩ>與濾波器的頻譜函數(shù)H<jΩ>的乘積,即：而在時(shí)域,輸出信號(hào)y<t>實(shí)際是輸入信號(hào)x<t>與濾波器h<t>的卷積。就是說(shuō)頻譜函數(shù)的乘積相當(dāng)于時(shí)間函數(shù)的卷積,反之亦然。即：由于DSP主要依靠計(jì)算機(jī)完成,而計(jì)算機(jī)無(wú)論在時(shí)域或頻域只能處理有限長(zhǎng)的離散信號(hào),因此上述關(guān)系可表示為：式中：n表示離散時(shí)間；數(shù)字頻率ω=ΩT；f為輸入信號(hào)頻率；f,T為抽樣頻率和周期。3.2原理分析可以使用線性卷積、圓周卷積實(shí)現(xiàn)離散卷積,也可以根據(jù)時(shí)域信號(hào)函數(shù)與頻譜函數(shù)的關(guān)系,使用快速傅里葉變換<FFT,IFFT>實(shí)現(xiàn)離散卷積。3.2.1離散傅里葉變換〔DFT和快速傅里葉變換〔FFT離散傅里葉變換,是連續(xù)傅里葉變換在時(shí)域和頻域上都離散的形式,將時(shí)域信號(hào)的采樣變換為在離散時(shí)間傅里葉變換頻域的采樣。在形式上,變換兩端〔時(shí)域和頻域上的序列是有限長(zhǎng)的,而實(shí)際上這兩組序列都應(yīng)當(dāng)被認(rèn)為是離散周期信號(hào)的主值序列。即使對(duì)有限長(zhǎng)的離散信號(hào)作DFT,也應(yīng)當(dāng)將其看作經(jīng)過(guò)周期延拓成為周期信號(hào)在做變換。在實(shí)際應(yīng)用中通常采用快速傅里葉變換〔FFT高效計(jì)算DFT。采用這種算法能使計(jì)算機(jī)計(jì)算離散傅里葉變換所需要的乘法次數(shù)大為減少,特別是被變換的抽樣點(diǎn)數(shù)N越多,FFT算法計(jì)算量的節(jié)省就越顯著。3.2.2序列的卷積和快速卷積運(yùn)算卷積是數(shù)字信號(hào)處理中最常見(jiàn)的,也是最重要的運(yùn)算之一。利用卷積可以實(shí)現(xiàn)相關(guān)計(jì)算和FIR濾波等等,正因?yàn)榫矸e如此重要,所以半個(gè)世紀(jì)以來(lái),學(xué)者們提出了多種不同卷積實(shí)現(xiàn)結(jié)構(gòu),這些結(jié)構(gòu)各有優(yōu)點(diǎn),針對(duì)不同應(yīng)用可以靈活選擇,而其中快速卷積無(wú)疑是重要的卷積方法之一。顧名思義,快速卷積重點(diǎn)在一個(gè)"快",如果對(duì)卷積速度要求較高,快速卷積無(wú)疑是理想的工具。當(dāng)然,為了提高速度,就要犧牲面積和功耗。3.2.3快速傅里葉變換和快速卷積在此,我們是利用快速傅里葉變換實(shí)現(xiàn)快速卷積運(yùn)算。同時(shí)在進(jìn)行Matlab編程時(shí)也是利用快速傅里葉變換來(lái)得到快速卷積的結(jié)果。4.程序設(shè)計(jì)及仿真結(jié)果分析4.1題目一長(zhǎng)度為m的向量序列h和長(zhǎng)度為n的向量序列x,卷積w的向量序列長(zhǎng)度為<m+n-1>,當(dāng)m≠n時(shí),應(yīng)以0補(bǔ)齊階次低的向量的高位后進(jìn)行計(jì)算y<1>=h1>*x<1>y<2>=h<1>*x<2>+h<2>*x<1>y<3>=h<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>那么所得的結(jié)果就是y〔n=[6,14,25,42,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系統(tǒng)輸出函數(shù)y<n>由圖4.1可和自己求出的y<n>函數(shù)相比較可以得到,用matlab編寫程序得出的系統(tǒng)輸出函數(shù)與自己人工計(jì)算的結(jié)果相同。4.2題目二在matlab實(shí)現(xiàn)卷積的.函數(shù)為CONV,對(duì)于N值較小的向量,這是十分有效的。對(duì)于N值較大的向量卷積可用FFT加快計(jì)算速度。若DFT和IDFT均采用FFT和IDFT算法,可提高卷積速度。計(jì)算x1<n>和x2<n>的線性卷積的FFT算法可由下面步驟實(shí)現(xiàn)：1、 計(jì)算X1<k>=FFT[x1<n>];2、 計(jì)算X2<k>=FFT[x2<n>];3、 Y<k>=X1<k>·X2<k>;4、 計(jì)算x1<n>*x2<n>=IFFT[Y<k>]在本題目中計(jì)算的兩個(gè)函數(shù)分別是x1<n>=2*n,x2<n>=3.^n。用matlab編寫的完整程序如下所示L=1000;N=L*2-1;n=1:L;x1=2*n;x2=3.^n;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>反正結(jié)果如下：圖4.2由結(jié)果可知,長(zhǎng)度為1000時(shí),快速卷積所用時(shí)間較少。4.3題目三利用快速卷積原理求兩個(gè)函數(shù)的卷積可以用題目二中所用的方法〔先分別對(duì)兩個(gè)函數(shù)求傅里葉變換得到X<k>與H<k>,再兩個(gè)函數(shù)傅里葉變換的點(diǎn)乘的結(jié)果y<k>,最后直接對(duì)y<k>求傅里葉反變換得到y(tǒng)<n>快速卷積,得到所要求的結(jié)果。因?yàn)樵谶@次題目中與兩個(gè)函數(shù)中M與N沒(méi)有給出,取M=2000,N=1800時(shí)。所用的程序以及各自的輸出結(jié)果如下所示：xn=0.9.^<1:20>;hn=1.^<1:16>;tic;yn=conv<xn,hn>;toc;L=pow2<nextpow2<20+16-1>>;ticxk=fft<xn,L>;hk=fft<hn,L>;yk=xk.*hk;yn=ifft<yk,L>;toc;subplot<221>,stem<xn,'.'>;ylabel<'x<n>'>;subplot<222>,stem<hn,'.'>;ylabel<'h<n>'>;subplot<212>,ny=1:L;stem<real<yn>,'.'>;ylabel<'y<n>'>;仿真結(jié)果如圖4.3：圖4.3由仿真結(jié)果可知,當(dāng)點(diǎn)數(shù)較大時(shí),快速卷積所用時(shí)間明顯少于普通卷積。5.心得體會(huì)這次課程設(shè)計(jì)我做的是序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn),是利用MATLAB這個(gè)軟件完成的,因?yàn)橹拔覀冊(cè)鯩ATLAB課設(shè),平時(shí)使用MATLAB也比較多,所以這次課設(shè)做起來(lái)也相對(duì)比較簡(jiǎn)單。但是,即使這個(gè)比較簡(jiǎn)單,也要認(rèn)真對(duì)待。MATLAB功能強(qiáng)大,尤其對(duì)于我們電子信息類的學(xué)生尤其重要,平時(shí)用到的機(jī)會(huì)比較多,認(rèn)真學(xué)好很有必要。完成這次課程設(shè)計(jì)我認(rèn)為收獲還是很多的,不但進(jìn)一步掌握了數(shù)字信號(hào)處理的基礎(chǔ)知識(shí)及一門專業(yè)仿真軟件的基本操作,還提高了自己的設(shè)計(jì)能力及動(dòng)手能力,同時(shí)對(duì)于模擬濾波器來(lái)了個(gè)系統(tǒng)的總結(jié)。更多的是讓我看清了自己,明白了凡事需要耐心,實(shí)踐是檢驗(yàn)學(xué)習(xí)的唯一標(biāo)準(zhǔn)。理論知識(shí)的不足在這次課設(shè)中表現(xiàn)的很明顯。這將有助于我今后的學(xué)習(xí),端正自己的學(xué)習(xí)態(tài)度,從而更加努力的學(xué)習(xí)。只有這樣我們才能真正的去掌握它,而不是只懂得一點(diǎn)皮毛。在做的課程中,也曾遇到一些小問(wèn)題,如在程序中兩個(gè)數(shù)之間點(diǎn)成和叉乘的使用沒(méi)區(qū)別好,所以我們應(yīng)該認(rèn)真對(duì)待每一個(gè)小細(xì)節(jié),才能做好每件事,端正自己的態(tài)度,不要因?yàn)楹?jiǎn)單而不上心。這次課設(shè)還加深自己對(duì)知識(shí)的理解,對(duì)序列的卷積和快速卷積理解更加透徹,從理論到實(shí)踐。只有都經(jīng)過(guò),知識(shí)才能更加牢固。紙上得來(lái)終覺(jué)淺,絕知此事要躬行。前人已經(jīng)總結(jié)的很好,我們只有在實(shí)踐中發(fā)現(xiàn)自己的問(wèn)題,然后不斷的克服,才能把知識(shí)變成自己的,更加好的鍛煉