基于重疊相加法圓周卷積的實現(xiàn)

1、目 錄摘要1 理論學習11.1圓周卷積原理11.2重疊相加法21.3重疊相加法圓周卷積41.4線性卷積、圓周卷積、重疊相加法、DFT、FFT之間的聯(lián)系52 程序設計62.1程序設計思路62.2程序設計流程圖72.3 程序代碼73程序調(diào)試與結果與分析9心得體會11參考文獻121 理論學習1.1圓周卷積原理對兩個N點序列和，除了可以做線性卷積外，還有一種很重要的卷積運算，就是圓周卷積。令則圓周卷積結果長度不變, 為N.由上式可以得出圓周卷積與周期卷積的關系，就是有限長序列圓周卷積結果的周期延拓，等于它們周期延拓后的周期卷積。也就是說，周期卷積的主值序列，是各周期序列主值序列的圓周卷積。若、分別是長

2、度為N、M的序列則與線性卷積至多M+N-1個非零值，如果L<M+N-1則周期延拓時必然會有一部分非零值發(fā)生混疊；只有當L>M+N-1時，周期延拓才不會發(fā)生混疊。之所以討論用圓周卷積來計算線性卷積的條件，是因為圓周卷積可在頻域下利用DFT求得，從而可采用DFT的快速算法FFT來計算，這樣就可以利用FFT來計算線性卷積，大大提高運算效率。圓周卷積的實現(xiàn)步驟如下圖：圖1.1 圓周卷積的實現(xiàn)步驟1.2重疊相加法DFT 是連續(xù)傅里葉變換在時域和頻域上都離散的形式，將時域信號的采樣變換為在離散時間傅里葉變換頻域的采樣。在形式上，變換兩端（時域和頻域上）的序列是有限長的。DFT 具備明確且合理的

3、物理含義，適合應用于數(shù)字系統(tǒng)，同時可以方便地由計算機進行運算。對于線性非移變離散系統(tǒng)，可由線性卷積表示時域輸入輸出關系，即y(n)=x(n)*h(n)通常采用循環(huán)卷積降低運算量，但實際中往往無法滿足對信號處理的實時性要求。因此，產(chǎn)生了重疊相加法，用以快速計算線性卷積，成為了DFT 的一個重要應用。重疊相加法是將待過濾的信號分割成長為N 的若干段，如圖1 所示，每一段都可以和有限時寬單位取樣響應作卷積，再將過濾后的各段重疊相加。具體算法實現(xiàn)原理如圖2 所示，建立緩存序列，每次輸入N 點序列，通過計算x(n) 和h(n) 的循環(huán)卷積實現(xiàn)線性卷積運算，將緩存的M-1 點序列和卷積結果相加，并輸出前N

4、 點作為計算結果，同時緩存后M-1 點，如此循環(huán)，直至所有分段計算完畢，則輸出序列y(n)為最終計算結果。圖1.2 重疊相加法的分段示意圖圖1.3 重疊相加法算法示意圖1.3重疊相加法圓周卷積在實際應用中利用FFT來計算兩個序列的圓周卷積從而實現(xiàn)計算其線性卷積，但是常遇到的問題是參加卷積的兩個序列的長度相差較大，這樣長度小的序列就需要補很多的零點，這樣就需要較大的存儲量，運算時間也會變長。所以常用到的解決方法有兩種，其中一種就是重疊相加法。h(n)長度為N，x(n)長度為無限長，x(n)取M點，且與N盡量接近x(n)與h(n)的卷積為圖1.4 重疊相加法的卷積示意圖重疊相加法的步驟如下（1）將

5、h(n)補零延長到L =M+ N -1，并計算長為L的FFT，得到 H(k)。（2）分別將xk(n)補零延長到L =M+ N -1，并計算長為L的FFT，得到 Xk(k)（3）計算，并求長為L的反變換，即（4）將yk(n)的重疊部分相加，最后得到結果為1.4線性卷積、圓周卷積、重疊相加法、DFT、FFT之間的聯(lián)系由時域與頻域的關系可知，兩序列和在時域下進行線性卷積的結果等于這兩個序列在頻域下相乘后進行反變換回時域的結果。圓周卷積在一定條件下（L>M+N-1）與線性卷積得到的結果相同，而圓周卷積可在頻域下利用DFT求得，從而可采用DFT的快速算法FFT來計算，這樣就可以利用FFT來計算線性

6、卷積，大大提高運算效率。而在利用FFT來計算圓周卷積的過程中當兩序列的長度相差較大時采用重疊相加法來進行計算可有效提高計算的效率，減小存儲空間的消耗。2 程序設計2.1程序設計思路函數(shù)conv (x1,x2,L)設計（1） x1(n)進行N點快速傅里葉變換得X1(k)（2） x2(n)進行N點快速傅里葉變換得X2(k)（3） 進行頻域相乘Y(k)=X1(k)*X2k（4） 對Y(k)進行反變換得到時域卷積結果y(n)函數(shù)overlap_add(x,h,N)設計方案1：（1）首先取長序列x(n)進行分段的長度N，以使其分段后的長度與較短的相近（2）確定圓周卷積的周期L（3）填充序列使得循環(huán)中對序

7、列的索引不會超出范圍（4）確定分段數(shù)K（5）對序列進行分段調(diào)用conv ()函數(shù)計算圓周卷積（6）各段重疊相加（7）取出實際的輸出序列方案2：（1）首先取圓周卷積的周期L（即進行L點的快速傅里葉變換）（2）計算每一分段的大小N（3）填充序列使得循環(huán)中對序列的索引不會超出范圍（4）計算分段數(shù)K（5）對序列進行分段調(diào)用conv ()函數(shù)計算圓周卷積（6）各段重疊相加（7）取出實際的輸出序列結論：方案二比較接近我們平常的思維，使用較為方便，利于程序調(diào)試。2.2程序設計流程圖開始輸入序列x(n),h(n)計算各個序列長度，分段數(shù)，生成臨時序列填入保留值后分段循環(huán)卷積輸出前N個點并為t(n)重新賦為保留

8、值完成所有分段計算輸出序列y（n）結束圖2.1 程序設計流程圖2.3 程序代碼function y = circular_conv( x1,x2,L) % 利用循環(huán)卷積計算線性卷積 % 循環(huán)卷積采用頻域計算方法,已FFT代替DFT,降低運算量 X1k = fft(x1,L); %x1做L點FFT X2k = fft(x2,L); %x1做L點FFT Yk = X1k.*X2k; %頻域相乘 y = ifft(Yk); %FFT反變換得循環(huán)卷積結果 function y = overlap_add(x,h,N) %重疊相加法實現(xiàn) %核心為將高點數(shù)DFT轉(zhuǎn)化為低點數(shù)DFT，且用循環(huán)卷積計算線性卷積

9、 M = length(h); %獲得h(n)的長度 if N <M %為N選擇合適的值保證運算正確 N = M+1; end L = M+N-1; %循環(huán)卷積與線性卷積結果相同時需要進行運算的最少點數(shù) Lx = length(x); %獲得x(n)的長度 T = ceil(Lx/N); %確定分段數(shù)T t = zeros(1,M-1); %初始化序列t(n) x = x,zeros(1, (T+1)*N-Lx); %不足的分段補零 y = zeros(1, (T+1)*N); %生成輸出序列y(n),長度足夠長 for i=0:1:T xi=i*N+1; x_seg = x(xi:xi

10、+N-1); %選擇低點數(shù)計算時的分段x(n) y_seg = circular_conv(x_seg,h,L); %調(diào)用循環(huán)卷積計算線性卷積 y_seg(1:M-1) = y_seg(1:M-1)+t(1:M-1);%完成重疊相加 t(1:M-1) = y_seg(N+1:L); %重新對t(n)賦值為保留的后M-1點 y(xi:xi+N-1) = y_seg(1:N); %直接輸出前N個點 end y=y(1:Lx+M-1); %取出最終的輸出序列3程序調(diào)試與結果與分析先輸入程序段conv( x1,x2,L)保存為circular_conv.m再輸入程序段overlap_add(x,h,N

11、)保存為overlap_add.m如下圖：圖3.1 程序調(diào)試輸入序列和周期Lx1=1:2:20;x2=-2:1:2;L=14; 圖3.2 程序調(diào)試結果如圖可見，運算結果：-2 -7 -13 -18 -20 -20 -20 -20 -20 -20 22 47 53 38輸入指令輸出圖表可獲得更直觀的結論：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);圖3.3 卷積結果由程

12、序運行結果與線性卷積結果比較可以知道程序計算結果正確的，程序設計完成。心得體會總是說學習要溫故而知新。課程設計進行之初，思緒全無，舉步維艱，對于理論知識學習不夠扎實的我深感“書到用時方恨少”，于是想起圣人之言“溫故而知新”，便重拾教材與實驗手冊，對知識系統(tǒng)而全面進行了梳理，遇到難處先是苦思冥想再向同學請教，終于熟練掌握了基本理論知識，學會了如何思考的思維方式，找到了解決的方案。 雖然第一遍的方案總有那么多的欠缺，但是過而能改，善莫大焉。至善至美，是人類永恒的追求。但是，不從忘卻“金無足赤，人無完人”，換種思維方式，去惡亦是至善，改錯亦為至美。在課程設計過程中，我不斷發(fā)現(xiàn)錯誤，不斷改正，不斷領悟，不斷獲取。最終的仿真環(huán)節(jié)，本身就是在踐行“過而能改，善莫大焉”的知行觀。我要感謝所有給與我?guī)椭耐瑢W和老師，正是有你們的幫助才使得我理清了思路，少走了許多彎路。同時你們的許多獨到的想法也給與了我一種全新的認識，使那些原本在腦海中的零零散散的知識點最終匯聚一堂，形成了一個完整的體系。并且在實踐中得到了肯好的印證，使原本相對生硬的知識給我留下了相當直觀的不可磨滅