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

.../課程設(shè)計任務(wù)書學(xué)生姓名：韓新穎專業(yè)班級：電信1203班指導(dǎo)教師：闕大順王虹工作單位：信息工程學(xué)院題目:序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn)初始條件：Matlab6.5以上版本軟件；課程設(shè)計輔導(dǎo)資料："Matlab語言基礎(chǔ)及使用入門"、"數(shù)字信號處理原理與實(shí)現(xiàn)"、"Matlab及在電子信息課程中的應(yīng)用"等；先修課程：信號與系統(tǒng)、數(shù)字信號處理、Matlab應(yīng)用實(shí)踐及信號處理類課程等。要求完成的主要任務(wù)：〔包括課程設(shè)計工作量及其技術(shù)要求,以及說明書撰寫等具體要求課程設(shè)計時間：1周〔課內(nèi)實(shí)踐；課程設(shè)計內(nèi)容：序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn),具體包括：直接卷積及應(yīng)用、快速卷積方法及實(shí)現(xiàn)、兩者的比較分析等；本課程設(shè)計統(tǒng)一技術(shù)要求：研讀輔導(dǎo)資料對應(yīng)章節(jié),對選定的設(shè)計題目進(jìn)行理論分析,針對具體設(shè)計部分的原理分析、建模、必要的推導(dǎo)和可行性分析,畫出程序設(shè)計框圖,編寫程序代碼〔含注釋,上機(jī)調(diào)試運(yùn)行程序,記錄實(shí)驗結(jié)果〔含計算結(jié)果和圖表,并對實(shí)驗結(jié)果進(jìn)行分析和總結(jié)；課程設(shè)計說明書按學(xué)校"課程設(shè)計工作規(guī)范"中的"統(tǒng)一書寫格式"撰寫,具體包括：目錄；與設(shè)計題目相關(guān)的理論分析、歸納和總結(jié)；與設(shè)計內(nèi)容相關(guān)的原理分析、建模、推導(dǎo)、可行性分析；程序設(shè)計框圖、程序代碼〔含注釋、程序運(yùn)行結(jié)果和圖表、實(shí)驗結(jié)果分析和總結(jié)；課程設(shè)計的心得體會〔至少500字；參考文獻(xiàn)；其它必要內(nèi)容等。指導(dǎo)教師簽名：年月日系主任〔或責(zé)任教師簽名：年月日摘要卷積在數(shù)字信號處理中有著重要的作用。然而直接計算卷積的運(yùn)算量非常大,它與序列長度的平方成反比,因此制約了卷積的應(yīng)用?？焖倬矸e是實(shí)現(xiàn)卷積的一種快速算法,減少了運(yùn)算量,節(jié)約了時間。通過分析我們可在MATLAB里編程實(shí)現(xiàn)。關(guān)鍵詞：卷積；快速卷積；MATLAB。目錄1、直接卷積及應(yīng)用11.1卷積的定義11.2、卷積的運(yùn)用12、快速卷積方法及實(shí)現(xiàn)22.1快速卷積運(yùn)算原理22.2實(shí)現(xiàn)方法3重疊相加法3重疊保留法33、直接卷積和快速卷積的分析比較44、程序設(shè)計及仿真結(jié)果分析45、心得體會116、參考文獻(xiàn)121、直接卷積及應(yīng)用1.1卷積的定義設(shè):f<x>,g<x>是R1上的兩個可積函數(shù),作積分：可以證明,關(guān)于幾乎所有的實(shí)數(shù)x,上述積分是存在的。這樣,隨著x的不同取值,這個積分就定義了一個新函數(shù)h<x>,稱為函數(shù)f與g的卷積,記為h<x>=<f*g><x>。1.2、卷積的運(yùn)用卷積是數(shù)字信號處理中最常見,也是最重要的運(yùn)算之一,利用卷積可以實(shí)現(xiàn)相關(guān)計算和FIR濾波等等,正因為卷積如此重要,所以半個世紀(jì)以來,學(xué)者們提出了多種不同卷積實(shí)現(xiàn)結(jié)構(gòu)。設(shè)輸入信號為x〔t,其頻譜函數(shù)為X〔jΩ該信號通過濾波器h〔t后,其輸出信號y〔t的頻譜函數(shù)Y〔jΩ是頻譜函數(shù)x〔jΩ與濾波器的頻譜函數(shù)H〔jΩ的乘積,即：Y〔jΩ=X〔jΩH〔jΩ而在時域,輸出信號y<t>實(shí)際是輸入信號x<t>與濾波器h<t>的卷積,就是說頻譜函數(shù)的乘積相當(dāng)于時間函數(shù)的卷積,反之亦然,即：y<t>=x<t>*h<t>在數(shù)字信號處理系統(tǒng)中,無論在時域還是頻域都離不開卷積運(yùn)算和快速傅里葉運(yùn)算,Matlab具有強(qiáng)大的矩陣運(yùn)算能力。方便實(shí)用的繪圖功能和語言的高度集成性。在DSP開發(fā)中,使用Matlab可以快速對系統(tǒng)進(jìn)行仿真運(yùn)算。2、快速卷積方法及實(shí)現(xiàn)2.1快速卷積運(yùn)算原理在信號處理中,許多具體的應(yīng)用是以線性卷積為基礎(chǔ)的。當(dāng)滿足一定條件時,可以用圓周卷積來計算線性卷積。由圓周卷積定理知道,圓周卷積可以借助DFT來運(yùn)算,因此DFT的快速算法FFT就可以用來計算線性卷積。設(shè)x1〔n與x2〔n分別是長度為N與M的有限長序列,它們的線性卷積為yl〔n,L點(diǎn)的圓周卷積為yc〔n,它們的關(guān)系為yc〔n=∑yl<n+rL>Rl<n>由上式可知圓周卷積是線性卷積以L為周期進(jìn)行延拓后,再取主值序列的結(jié)果。當(dāng)滿足L>M+N-1時,周期延拓不發(fā)生混疊,就可以用圓周卷積來計算線性卷積。由圓周卷積定義可知,可以用FFT分別求出x1〔n與x2〔n的L點(diǎn)DFTX1〔k與X2〔k,即X1〔k=DFT[x1<n],X2〔k=DFT[x2<n>],再用IFFT計算X1<kX2<k>的L點(diǎn)IDFT得yc〔n,也就是x1〔n與x2〔n的線性卷積為yl<n>,即yl<n>=yc<n>=IDFT[X1<k>·X2〔k]下圖為上述過程的示意圖L點(diǎn)的FFTx1<n>L點(diǎn)的FFTL點(diǎn)的IFFTyc<n=yl<n>L點(diǎn)的IFFTL點(diǎn)的FFTx2<n>L點(diǎn)的FFT2.2實(shí)現(xiàn)方法在實(shí)際應(yīng)用中,常遇到的問題是參加卷積的兩個序列的長度相差較大,這樣長度小的序列就需補(bǔ)很多的零點(diǎn),這樣就需要大的存儲量,運(yùn)算時間也會變長。常用的解決方法有兩種,一是重疊相加法,另一種是重疊保留法。重疊相加法設(shè)序列x1〔n為無限長序列,序列x2〔n是長度為M的序列,由x1<n>構(gòu)成長度為N的有限長序列x1k<n>=x1<n>,kN<n<<k+1>N-1=0其他〔式2.1因此x1k<n>=∑x1k<n>〔式2.2將式子代入卷積公式有Y<n>=x1<n>*x2<n>=x2<n>*∑x1k<n>=∑x1k<n>*x2<n>=∑yk<n>〔式2.3式中,yk<n>=x2<n>*xk<n>=∑x2<m>xk<n-m>〔式2.4式〔2.3表示,計算x1<n>與x2〔n的線性卷積y<n>時,可以先分段計算yk<n>,然后再疊加起來即可。因為yk<n>的長度為M+N-1,因此yk〔n的后N-1個值與yk+1<n>的前N-1個值重疊,因此必須把yk<n>的后N-1個值與yk+1〔n前的N-1個值相加,因為稱為重疊相加法。重疊保留法為了克服重疊相加法中分段卷積后任然需要相加的缺點(diǎn),人們提出了重疊保留法。與重疊相加法不同的是,在對無限長序列x1<n>的后M-1個抽樣值與后一段xk+1<n>的前M-1個抽樣值相同,且分段的長度選圓周卷積的長度L,這樣形成的分段序列為然后計算x2〔n與各分段x1k<n>之間的卷積：Yk’=x2<n>*x1k<n>顯然,yk’<n>的前M-1個值發(fā)生了混疊,不等于x2<n>與x1k<n>的線性卷積。把yk’<n>的前M-1個值舍去,保留yk’<n>沒有發(fā)生混疊的后N個值,形成序列X1k=x<n+kN-M+1>,0<n<L-1=0其他最后輸出序列y<n>=∑yk<n-kN+M-1>3、直接卷積和快速卷積的分析比較卷積是數(shù)字信號處理中最常見的,也是最重要的運(yùn)算之一。利用卷積可以實(shí)現(xiàn)相關(guān)計算和FIR濾波等等,正因為卷積如此重要,所以半個世紀(jì)以來,學(xué)者們提出了多種不同卷積實(shí)現(xiàn)結(jié)構(gòu),這些結(jié)構(gòu)各有優(yōu)點(diǎn),針對不同應(yīng)用可以靈活選擇,而其中快速卷積無疑是重要的卷積方法之一。顧名思義,快速卷積重點(diǎn)在一個"快",如果對卷積速度要求較高,快速卷積無疑是理想的工具。當(dāng)然,為了提高速度,就要犧牲面積和功耗4、程序設(shè)計及仿真結(jié)果分析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>,并作圖。人工計算：長度為m的向量序列h和長度為n的向量序列x,卷積w的向量序列長度為〔m+n-1,當(dāng)不等于n時,應(yīng)以0補(bǔ)齊階次低的向量的高位后進(jìn)行計算y<1>=h<1>*x<1>y<2>=h<1>*x<2>+h<2>*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-2>+...+h<m+n-1>*x<1>那么根據(jù)這個規(guī)律人工計算的結(jié)果為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>結(jié)果如圖4.1所示：圖4.1由圖4.1和自己求出的y<n>函數(shù)相比較可以得到,用matlab編寫程序得出的系統(tǒng)輸出函數(shù)與自己人工計算的結(jié)果相同。2、用函數(shù)conv和FFT計算長為1000序列的卷積,比較其計算時間。在matlab實(shí)現(xiàn)卷積的.函數(shù)為CONV,對于N值較小的向量,這是十分有效的對于N大的向量卷積可用FFT加快計算速度。若DFT和IDFT均采用FFT和IDFT法,可提高卷積速度。計算x1<n>和x2<n>的線性卷積的FFT算法可由下面步驟實(shí)現(xiàn)：1、計算X1<k>=FFT[x1<n>];2、計算X2<k>=FFT[x2<n>];3、Y<k>=X1<k>·X2<k>;4、計算x1<n>×x2<n>=IFFT[Y<k>]在本題目中計算的兩個函數(shù)分別是x1<n>=2*10^n,x2<n>=cos<n^3>。用Matlab編寫的程序如下：L=1000;N=L*2-1;n=1:L;x1=2*<n.^10>;x2=cos<n.^3>;t0=clock;yc=conv<x1,x2>;conv_time=etime<clock,t0>N=pow2<nextpow2<L*2-1>>;t0=clock;yf=ifft<fft<x1,N>.*fft<x2,N>>;fft_time=etime<clock,t0>subplot<221>,stem<x1,'.'>;ylabel<'x<n>'>;subplot<222>,stem<x2,'.'>;ylabel<'h<n>'>;subplot<212>,stem<real<yc>,'.'>;ylabel<'y<n>'>;在Matlab中編程以及得出的完成程序所需的時間如圖4.2：圖4.2輸出結(jié)果如圖4.3：圖4.3該題要求的是對用函數(shù)conv和FFT計算1000點(diǎn)的序列卷積所需的時間進(jìn)行對比,通過圖4.2可知,用函數(shù)conv計算該卷積需要0.0100s,而用FFT計算該卷積需要0s,由此可以得出：FFT算法所消耗的時間遠(yuǎn)小于函數(shù)conv要消耗的時間。3、用快速卷積法計算和兩個序列的卷積；并測試直接卷積和快速卷積的時間。利用快速卷積原理求兩個函數(shù)的卷積可以用題目二中所用的方法〔先分別對兩個函數(shù)求傅里葉變換得到X<k>與H<k>,再兩個函數(shù)傅里葉變換的點(diǎn)乘的結(jié)果y<k>,最后直接對y<k>求傅里葉反變換得到y(tǒng)<n>快速卷積,得到所要求的結(jié)果。因為在這次題目中與兩個函數(shù)中M與N沒有給出,所以就分別取M=50,N=30和M=1500,N=1100分別求該題目所說并得到結(jié)果:所用的程序以及輸出結(jié)果分別如下圖所示：〔1M=50,N=30的情況：圖4.4圖4.5〔2M=1500,N=1100的情況：圖4.6圖4.7題目3要求計算兩序列的卷積,比較直接卷積和快速卷積的時間對比由上圖的結(jié)果可知,當(dāng)說算積分的點(diǎn)數(shù)比較少時,快速卷積并不占有優(yōu)勢,反而快速卷積所用時間多于正常的卷積conv函數(shù)。只有當(dāng)積分的點(diǎn)數(shù)比較多時才會有快速卷積所用時間少于普通卷積的conv函數(shù)。5、心得體會在得到這次課設(shè)題目以后,我就開始準(zhǔn)備資料了,先是上網(wǎng)查閱基本資料,做一個大概的了解,然后發(fā)現(xiàn)此次題目卷積和快速卷積在課本上能找到相關(guān)的內(nèi)容,就再在書上進(jìn)行尋找,發(fā)現(xiàn)了書上有介紹快速卷積的方法就進(jìn)行閱讀并學(xué)習(xí),在做好準(zhǔn)備后就開始進(jìn)行課設(shè)的三個題目了,第一題很好解答很快也完成了,感覺信心倍增,但是在做第二題時,‘’符號打入Matlab中老是不符合規(guī)范,進(jìn)行了多次改進(jìn)也沒辦