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

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

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

3、物理含義，適合應(yīng)用于數(shù)字系統(tǒng)，同時(shí)可以方便地由計(jì)算機(jī)進(jìn)行運(yùn)算。對(duì)于線性非移變離散系統(tǒng)，可由線性卷積表示時(shí)域輸入輸出關(guān)系，即y(n)=x(n)*h(n)通常采用循環(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)算，將緩存的M-1 點(diǎn)序列和卷積結(jié)果相加，并輸出前N

4、 點(diǎn)作為計(jì)算結(jié)果，同時(shí)緩存后M-1 點(diǎn)，如此循環(huán)，直至所有分段計(jì)算完畢，則輸出序列y(n)為最終計(jì)算結(jié)果。圖1.2 重疊相加法的分段示意圖圖1.3 重疊相加法算法示意圖1.3重疊相加法圓周卷積在實(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盡量接近x(n)與h(n)的卷積為圖1.4 重疊相加法的卷積示意圖重疊相加法的步驟如下（1）將

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

6、卷積，大大提高運(yùn)算效率。而在利用FFT來(lái)計(jì)算圓周卷積的過(guò)程中當(dāng)兩序列的長(zhǎng)度相差較大時(shí)采用重疊相加法來(lái)進(jìn)行計(jì)算可有效提高計(jì)算的效率，減小存儲(chǔ)空間的消耗。2 程序設(shè)計(jì)2.1程序設(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ì)序

7、列的索引不會(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)試。2.2程序設(shè)計(jì)流程圖開(kāi)始輸入序列x(n),h(n)計(jì)算各個(gè)序列長(zhǎng)度，分段數(shù)，生成臨時(shí)序列填入保留值后分段循環(huán)卷積輸出前N個(gè)點(diǎn)并為t(n)重新賦為保留

8、值完成所有分段計(jì)算輸出序列y（n）結(jié)束圖2.1 程序設(shè)計(jì)流程圖2.3 程序代碼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é)果 function y = overlap_add(x,h,N) %重疊相加法實(shí)現(xiàn) %核心為將高點(diǎn)數(shù)DFT轉(zhuǎn)化為低點(diǎn)數(shù)DFT，且用循環(huán)卷積計(jì)算線性卷積

9、 M = length(h); %獲得h(n)的長(zhǎng)度 if N <M %為N選擇合適的值保證運(yùn)算正確 N = M+1; end L = M+N-1; %循環(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,M-1); %初始化序列t(n) x = x,zeros(1, (T+1)*N-Lx); %不足的分段補(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

10、+N-1); %選擇低點(diǎn)數(shù)計(jì)算時(shí)的分段x(n) y_seg = circular_conv(x_seg,h,L); %調(diào)用循環(huán)卷積計(jì)算線性卷積 y_seg(1:M-1) = y_seg(1:M-1)+t(1:M-1);%完成重疊相加 t(1:M-1) = y_seg(N+1:L); %重新對(duì)t(n)賦值為保留的后M-1點(diǎn) y(xi:xi+N-1) = y_seg(1:N); %直接輸出前N個(gè)點(diǎn) end y=y(1:Lx+M-1); %取出最終的輸出序列3程序調(diào)試與結(jié)果與分析先輸入程序段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)試結(jié)果如圖可見(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);圖3.3 卷積結(jié)果由程

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