【正文】 目 錄 摘要 ................................................................ Ⅰ 1 理論學(xué)習(xí) ........................................................... 1 圓周卷積原理 ................................................... 1 重疊相加法 ..................................................... 2 重疊相加法圓周卷積 .............................................. 4 線性卷積、圓周卷積、重疊相加法、 DFT、 FFT 之間的聯(lián)系 ................. 5 2 程序設(shè)計(jì) ............................................................ 6 程序設(shè)計(jì)思路 .................................................... 6 程序設(shè)計(jì)流程圖 .................................................. 7 程序代碼 ....................................................... 7 3程序調(diào)試與結(jié)果與分析 ................................................. 9 心得體會(huì) ............................................................. 11 參考文獻(xiàn) ............................................................. 12 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 1 1 理論 學(xué)習(xí) 圓周卷積原理 對(duì)兩個(gè) N 點(diǎn)序列 )(1nx 和 )(2nx ，除了可以 做線性卷積外，還有一種很重 要的卷積運(yùn)算，就是圓周卷積。 令 則圓周卷積結(jié)果長(zhǎng)度不變 , 為 N. 由上式可以得出圓周卷積與周期卷積的關(guān)系，就是有限長(zhǎng)序列圓周卷積結(jié)果的周期延拓，等于它們周期延拓后的周期卷積。也就是說(shuō)，周期卷積的主值序列，是各周期序列主值序列的圓周卷積。 若 )(1nx 、 )(2nx 分別是長(zhǎng)度為 N、 M 的序列則 )(1nx 與 )(2nx 線性卷積至多 M+N1 個(gè)非零值，如果 LM+N1則周期延拓時(shí)必然會(huì)有一部分非零值發(fā)生混疊；只有當(dāng) LM+N1時(shí)，周期延拓才不會(huì)發(fā)生混疊。 之所以討論用圓周卷積來(lái)計(jì)算線性卷積的條件，是因?yàn)閳A周卷積可在頻域下利用 DFT求得，從而可采用 DFT 的快速算法 FFT來(lái)計(jì)算，這樣就可以利用 FFT來(lái)計(jì)算線性卷積，大大提高運(yùn)算效率。 ??????????1010)()(1111 NnN Nnnxnx??????????1010)()(2222 NnN Nnnxnx?? ??????????1012102121))(()())(()()()()(NmNNmN mnxmxmnxmxnxnxny武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 2 圓周卷積的實(shí)現(xiàn)步驟如下 圖 ： 圖 圓周卷積的實(shí)現(xiàn)步驟 重疊相加法 DFT 是連續(xù)傅里葉變換在時(shí) 域和頻域上都離散的形式，將時(shí)域信號(hào)的采樣變換為在離散時(shí)間傅里葉變換頻域的采樣。在形式上，變換兩端（時(shí)域和頻域上）的序列是有限長(zhǎng)的。 DFT 具備明確且合理的物理含義，適合應(yīng)用于數(shù)字系統(tǒng)，同時(shí)可以方便地由計(jì)算機(jī)進(jìn)行運(yùn)算。 對(duì)于線性非移變離散系統(tǒng)，可由線性卷積表示時(shí)域輸入輸出關(guān)系，即 y(n)=x(n)*h(n) 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 3 通常采用循環(huán)卷積降低運(yùn)算量，但實(shí)際中往往無(wú)法滿足對(duì)信號(hào)處理的實(shí)時(shí)性要求。因此，產(chǎn)生了重疊相加法，用以快速計(jì)算線性卷積，成為了 DFT 的一個(gè)重要應(yīng)用。 重疊相加法是將待過(guò)濾的信號(hào)分割成長(zhǎng)為 N 的若干段，如 圖 1 所示，每一段都可以和有限時(shí)寬單位取樣響應(yīng)作卷積，再將過(guò)濾后的各段重疊相加。 具體算法實(shí)現(xiàn)原理如圖 2 所示，建立緩存序列，每次輸入 N 點(diǎn)序列，通過(guò)計(jì)算x(n) 和 h(n) 的循環(huán)卷積實(shí)現(xiàn)線性卷積運(yùn)算，將緩存的 M1 點(diǎn)序列和卷積結(jié)果相加，并輸出前 N 點(diǎn)作為計(jì)算結(jié)果，同時(shí)緩存后 M1 點(diǎn)，如此循環(huán)，直至所有分段計(jì)算完畢，則輸出序列 y(n)為最終計(jì)算結(jié)果。 圖 重疊相加法的分段示意圖 圖 重疊相加法算法示意圖 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 4 重疊相加法圓周卷積 在實(shí)際應(yīng)用中利用 FFT 來(lái)計(jì)算兩個(gè)序列的圓周卷積從而 實(shí)現(xiàn)計(jì)算其線性卷積，但是常遇到的問(wèn)題是參加卷積的兩個(gè)序列 的長(zhǎng)度相差較大，這樣長(zhǎng)度小的序列就需要補(bǔ)很多的零點(diǎn)，這樣就需要較大 的存儲(chǔ)量，運(yùn)算時(shí)間也會(huì)變長(zhǎng)。所以常用到的解決方法有兩種，其中一種就是重疊相加法。 h(n)長(zhǎng)度為 N， x(n)長(zhǎng)度為無(wú)限長(zhǎng)， x(n)取 M點(diǎn)，且與 N盡量接近 圖 重疊相加法的卷積示意圖 重疊相加法的步驟如下 （ 1）將 h(n)補(bǔ)零延長(zhǎng)到 L =M+ N 1，并計(jì)算長(zhǎng)為 L 的 FFT，得到 H(k)。 ?????? k k nxnx )()()()()( kMnRnxnx Mk ??x(n)與 h(n)的卷積為 )(*)()(*)()( nxnhnhnxny kk???????)()](*)([ nynhnx kkkk ?? ???????? ??武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 5 （ 2）分別將 xk(n)補(bǔ)零延 長(zhǎng)到 L =M+ N 1，并計(jì)算長(zhǎng)為 L 的 FFT，得到 Xk(k) （ 3）計(jì)算 )()()( kHkXkY kk ? ，并求長(zhǎng)為 L 的反變換，即 )]([)( kYIFFTny kk ? （ 4）將 yk(n)的重疊部分相加，最后得到結(jié)果為 ?????? k k nyny )()( 線性卷積、圓周卷積、重疊相加法、 DFT、 FFT 之間的聯(lián)系 由時(shí)域與頻域的關(guān)系可知，兩序列 )(1nx 和 )(2nx 在時(shí)域下進(jìn)行線性卷積的結(jié)果等于這兩個(gè)序列在 頻域下相乘后進(jìn)行反變換回時(shí)域的結(jié)果。圓周卷積在一定條件下（ LM+N1）與線性卷積得到的結(jié)果相同，而圓周卷積可在頻域下利用 DFT 求得，從而可采用 DFT的快速算法 FFT 來(lái)計(jì)算，這樣就可以利用 FFT來(lái)計(jì)算線性卷積，大大提高運(yùn)算效率。而在利用 FFT來(lái)計(jì)算圓周卷積的過(guò)程中當(dāng)兩序列的長(zhǎng)度相差較大時(shí)采用重疊相加法來(lái)進(jìn)行計(jì)算可有效提高計(jì)算的效率，減小存儲(chǔ)空間的消耗。 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 6 2 程序 設(shè)計(jì) 程序設(shè)計(jì)思路 函數(shù) conv (x1,x2,L)設(shè)計(jì) （ 1） x1(n)進(jìn)行 N 點(diǎn)快速傅里葉變換得 X1(k) （ 2） x2(n)進(jìn)行 N 點(diǎn)快速傅里葉變換得 X2(k) （ 3） 進(jìn)行頻域相乘 Y(k)=X1(k)*X2k （ 4） 對(duì) Y(k)進(jìn)行反變換得到時(shí)域卷積結(jié)果 y(n) 函數(shù) overlap_add(x,h,N)設(shè)計(jì) 方案 1： （ 1）首先取長(zhǎng)序列 x(n)進(jìn)行分段的長(zhǎng)度 N，以使其分段后的長(zhǎng)度與較短的相近 （ 2）確定圓周卷積的周期 L （ 3）填充序列使得循環(huán)中對(duì)序列的索引不會(huì)超出范圍 （ 4）確定分段數(shù) K （ 5）對(duì)序列進(jìn)行分段調(diào)用 conv ()函數(shù)計(jì)算圓周卷積 （ 6）各段重疊相加 （ 7）取出實(shí)際的輸出序列 方案 2： （ 1）首先取圓周卷積的周期 L（即進(jìn)行 L 點(diǎn)的快速傅里 葉變換） （ 2）計(jì)算每一分段的大小 N （ 3）填充序列使得循環(huán)中對(duì)序列的索引不會(huì)超出范圍 （ 4）計(jì)算分段數(shù) K （ 5）對(duì)序列進(jìn)行分段調(diào)用 conv ()函數(shù)計(jì)算圓周卷積 （ 6）各段重疊相加 （ 7）取出實(shí)際的輸出序列 結(jié)論：方案二比較接近我們平常的思維，使用較為方便，利于程序調(diào)試。 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 7 程序設(shè)計(jì)流程圖 圖 程序設(shè)計(jì)流程圖 程序代碼 function y = circular_conv( x1,x2,L) % 利用循環(huán) 卷積計(jì)算線性卷積 % 循環(huán)卷積采用頻域計(jì)算方法 ,已 FFT 代替 DFT,降低運(yùn)算量 X1k = fft(x1,L)。 %x1 做 L 點(diǎn) FFT X2k = fft(x2,L)。 %x1 做 L 點(diǎn) FFT Yk = X1k.*X2k。 %頻域相乘 y = ifft(Yk)。 %FFT 反變換得循環(huán)卷積結(jié)果 開(kāi)始 輸入序列 x(n),h(n) 計(jì)算各個(gè)序列長(zhǎng)度，分段數(shù)，生成臨時(shí)序列 填入保留值后分段循環(huán)卷積 輸出前 N 個(gè)點(diǎn)并為 t(n)重新賦為保留值 完成所有分段計(jì)算 輸出序列 y（ n） 結(jié)束 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 8 function y = overlap_add(x,h,N) %重疊相加法實(shí)現(xiàn) %核心為將高點(diǎn)數(shù) DFT 轉(zhuǎn)化為低點(diǎn)數(shù) DFT，且用循環(huán)卷積計(jì)算線性卷積 M = length(h)。 %獲得 h(n)的長(zhǎng)度 if N M %為 N 選擇合適的值保證運(yùn)算正確 N = M+1。 end L = M+N1。 %循環(huán)卷積與線性卷積結(jié)果相同時(shí)需要進(jìn)行運(yùn)算的最少點(diǎn)數(shù) Lx = length(x)。 %獲得 x(n)的長(zhǎng)度 T = ceil(Lx/N)。 %確定分段數(shù) T t = zeros(1,M1)。 %初始化序列 t(n) x = [x,zeros(1, (T+1)*NLx)]。 %不足的分段補(bǔ)零 y = zeros(1, (T+1)*N)。 %生成輸出序列 y(n),長(zhǎng)度足夠長(zhǎng) for i=0:1:T xi=i*N+1。 x_seg = x(xi:xi+N1)。 %選擇低點(diǎn)數(shù)計(jì)算時(shí)的分段 x(n) y_seg = circular_conv(x_seg,h,L)。 %調(diào)用循環(huán)卷積計(jì)算線性卷積 y_seg(1:M1) = y_seg(1:M1)+t(1:M1)。%完成重疊相加 t(1:M1) = y_seg(N+1:L)。 %重新對(duì) t(n)賦值為保留的后 M1 點(diǎn) y(xi:xi+N1) = y_seg(1:N)。 %直接輸出前 N 個(gè)點(diǎn) end y=y(1:Lx+M1)。 %取出最終的 輸出序列 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 9 3 程序調(diào)試與結(jié)果與分析 先輸入程序段 conv( x1,x2,L)保存為 再輸入程序段 overlap_add(x,h,N)保存為 如下圖： 圖 程序 調(diào)試 輸入 序列和周期 L x1=[1:2:20]。 x2=[2:1:2]。 L=14。 圖 程序調(diào)試 結(jié)果 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 10 如圖可見(jiàn)，運(yùn)算結(jié)果： 2 7 13 18 20 20 20 20 20 20 22 47 53 38 輸入指令輸出圖表可獲得更直觀的結(jié)論： x=[1:2:20]。h=[2:1:2]。overlap_add(x,h,14)。 subplot(3,1,1)。 c=1:2:20。stem(c,x)。 subplot(3,1,2)。 b=1:5。stem(b,h)。 subplot(3,1,3)。 a=1:14。stem(a,ans)。 圖 卷積結(jié)果 由程序運(yùn)行結(jié)果與線性卷積結(jié)果比較可以知道程序計(jì)算結(jié)果正確的，程序設(shè)計(jì)完成。 武漢理工大學(xué)《 信號(hào)分析與處理 》課程設(shè)計(jì)說(shuō)明書(shū) 11 心得體會(huì) 總是說(shuō)學(xué)習(xí)要 溫故而知新。課程設(shè)計(jì) 進(jìn)行之初 ，思緒全無(wú)，舉步維艱，對(duì)于理論知識(shí)學(xué)習(xí)不夠扎實(shí)的我深感“書(shū)到用時(shí)方 恨少”，于是想起圣人之言“溫故而知新”，便重拾教材與實(shí)驗(yàn)手冊(cè)，對(duì)知識(shí)系統(tǒng)而全面進(jìn)行了梳理，遇到難處先是苦思冥想再向同學(xué)請(qǐng)教，終于熟練掌握了基本理論知識(shí)，學(xué)會(huì)了如何思考的思維方式，找到了 解決的方案 。 雖然第一遍的方案總有那么多的欠缺，但是 過(guò)而能改，善莫大焉。至善至 美，是人類(lèi)永恒的追求。但是，不從忘卻“金無(wú)足赤，人無(wú)完人”， 換種思維方式，去惡亦是至善，改