用MATLAB實(shí)現(xiàn)線性卷積運(yùn)算北郵

1、信息與通信工程學(xué)院數(shù)字信號(hào)處理實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：用MATLAB實(shí)現(xiàn)線性卷積運(yùn)算班級(jí)：2008211113姓名：學(xué)號(hào)：日期：2010年5月索 引一、實(shí)驗(yàn)原理11、算法產(chǎn)生背景12、算法基本思想11）重疊相加法12）重疊保留法2二、流程圖設(shè)計(jì)31、重疊相加法32、重疊保留法4三、MATLAB源代碼51、重疊相加源碼52、重疊保留源碼6四、實(shí)驗(yàn)結(jié)果與分析7調(diào)用conv()計(jì)算7測(cè)試重疊相加算法7測(cè)試重疊保留算法7五、討論與總結(jié)81、算法效率分析：8A.重疊相加法8B.重疊保留法10C.調(diào)用conv()11D.綜合對(duì)比分析122、故障和問題分析13分段問題13運(yùn)算完整性問題13算法硬件實(shí)現(xiàn)13一、實(shí)驗(yàn)

2、原理1、算法產(chǎ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)系，即通常采用循環(huán)卷積降低運(yùn)算量，但實(shí)際中往往無(wú)法滿足對(duì)信號(hào)處理的實(shí)時(shí)性要求。因此，產(chǎn)生了重疊相加法和重疊保留法兩種典型的算法，用以快速計(jì)算線性卷積，成為了DFT的一個(gè)重要應(yīng)用。2、算法基本思想1）重疊相加法重疊相加法是將待過(guò)濾的信號(hào)分割成長(zhǎng)為N的若干段，如圖1所示，每一段都可以和有

3、限時(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點(diǎn)作為計(jì)算結(jié)果，同時(shí)緩存后M-1點(diǎn)，如此循環(huán)，直至所有分段計(jì)算完畢，則輸出序列y(n)為最終計(jì)算結(jié)果。 0 N-1 N 2N-1 2N 圖1. 重疊相加法的分段示意圖L點(diǎn)循環(huán)卷積M-1點(diǎn)緩存1L=N+M-1h(n)前N點(diǎn)后M-1點(diǎn)y(n)圖2. 重疊相加法算法示意圖2）重疊保留法重疊保留法相當(dāng)于將xl(n)和h(n)作循環(huán)卷積，然后找出循環(huán)卷積中相當(dāng)于線性卷積的部分。在這種情況下，將

4、序列y(n)分為長(zhǎng)為N的若干段(如圖3所示)，每個(gè)輸入段和前一段有M-1個(gè)重疊點(diǎn) 。此時(shí)只需要將發(fā)生重疊的前M-1個(gè)點(diǎn)舍去，保留重疊的部分并輸出，則可獲得序列y(n)，算法如圖4所示。 0 N-1 N 2N-1 2N 圖3. 重疊保留法的分段示意圖序列銜接M-1點(diǎn)緩存每N點(diǎn)輸入h(n)y(n)圖4. 重疊保留法算法示意圖后M-1點(diǎn)M+N-1點(diǎn)循環(huán)卷積后N點(diǎn)二、流程圖設(shè)計(jì)1、重疊相加法2、重疊保留法三、MATLAB源代碼1、重疊相加源碼function y = overlap_add(x,h,N)%重疊相加法實(shí)現(xiàn)%核心為將高點(diǎn)數(shù)DFT轉(zhuǎn)化為低點(diǎn)數(shù)DFT，且用循環(huán)卷積計(jì)算線性卷積M = lengt

5、h(h); %獲得h(n)的長(zhǎng)度if N <M %為N選擇合適的值保證運(yùn)算正確 N = M+1;endL = 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ù)Tt = 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+N-1); %選擇低點(diǎn)數(shù)計(jì)算時(shí)的分段

6、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)endy=y(1:Lx+M-1); %取出最終的輸出序列function y = circular_conv( x1,x2,L)% 利用循環(huán)卷積計(jì)算線性卷積% 循環(huán)卷積采用頻域計(jì)算方法,已FFT代替DFT,降低運(yùn)算量 X1k = fft(x1

7、,L); %x1做L點(diǎn)FFTX2k = fft(x2,L); %x1做L點(diǎn)FFTYk = X1k.*X2k; %頻域相乘 y = ifft(Yk); %FFT反變換得循環(huán)卷積結(jié)果2、重疊保留源碼function y = overlap_save(x,h,N)%重疊保留法實(shí)現(xiàn)%核心為將高點(diǎn)數(shù)DFT轉(zhuǎn)化為低點(diǎn)數(shù)DFT，且用循環(huán)卷積計(jì)算線性卷積Lx = length(x); %獲得x(n)的長(zhǎng)度M = length(h); %獲得h(n)的長(zhǎng)度if N <M %為N選擇合適的值保證運(yùn)算正確 N = M+1;endL = N+M-1; %為降低點(diǎn)數(shù),取M+N-1點(diǎn)循環(huán)卷積即可t = zeros(

8、1,M-1); %初始化序列t(n)T = ceil(Lx/N); %確定分段數(shù)x = x,zeros(1, (T+1)*N-Lx); %為不足的分段補(bǔ)零y = zeros(1, (T+1)*N); for i=0:1:T xi = i*N+1; x_seg = t,x(xi:xi+N-1); %確定每個(gè)低點(diǎn)數(shù)卷積的分段x(n) t = x_seg(N+1:N+M-1); %為t(n)重新賦值為后M-1個(gè)點(diǎn)的值 y_seg = circular_conv(x_seg,h,L); %循環(huán)卷積計(jì)算線性卷積 y(xi:xi+N-1)=y_seg(M:N+M-1);%直接取出后N個(gè)點(diǎn)作為一次計(jì)算的輸出

9、endy=y(1:Lx+M-1); %取出實(shí)際的輸出序四、實(shí)驗(yàn)結(jié)果與分析對(duì)兩種算法采用同一序列進(jìn)行測(cè)試分析。設(shè)xn=n+1,0n9;hn=-2,0,+2 。計(jì)算yn=xn*h(n) 。調(diào)用conv()計(jì)算首先利用Matlab對(duì)兩序列直接運(yùn)算，得出正確結(jié)果。代碼為：x=1:1:10,h=-2,0,+2,conv(x,h)結(jié)果為: -2 -4 -4 -4 -4 -4 -4 -4 -4 -4 18 20 測(cè)試重疊相加算法代碼為：overlap_add(x,h,6)結(jié)果為： -2.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000

10、-4.0000 -4.0000 18.0000 20.0000 測(cè)試重疊保留算法代碼為：overlap_save(x,h,4)結(jié)果為： -2.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 18.0000 20.0000 由此可見，兩種算法運(yùn)行正常，計(jì)算正確。更多的測(cè)試也正確。算法正確。五、討論與總結(jié)1、算法效率分析：A.重疊相加法 分段長(zhǎng)度序列長(zhǎng)度410100100010000100.0131510.0002660.0189630.0273780.0748341000.0011730.0

11、006050.0003190.0009170.01000710000.0099360.0028240.000920.0007460.013927100000.0741810.0271210.0066820.004060.0099221000000.6069330.2654760.0528520.0301060.04824510000006.0335282.4835260.3962060.2460520.333871000000059.9377625.104663.8974442.3281223.231499由上表和圖1可以看出，隨著數(shù)據(jù)規(guī)模增大，運(yùn)算耗時(shí)呈線性增長(zhǎng)，因而算法的時(shí)間復(fù)雜度為O(n

12、)，其中n為數(shù)據(jù)規(guī)模。因而重疊相加算法具有可行性和實(shí)用性。再?gòu)乃惴ǖ目臻g復(fù)雜度來(lái)看，由于分配的緩存空間只由分段長(zhǎng)度確定，不隨數(shù)據(jù)規(guī)模的變化而變化，因而空間復(fù)雜度為O(1)。綜合考察，重疊相加法具有較好的時(shí)間和空間復(fù)雜度。當(dāng)數(shù)據(jù)量達(dá)到千萬(wàn)量級(jí)時(shí)，運(yùn)算延時(shí)最少大約為2.328s，可運(yùn)用于對(duì)信號(hào)的實(shí)時(shí)處理。B.重疊保留法 分段長(zhǎng)度序列長(zhǎng)度410100100010000100.0005120.0002250.0012490.0008810.0084541000.0010140.0005140.0002720.0008360.00880210000.0092970.0024020.0007870.000

13、6870.011107100000.056740.0231940.0061220.0039410.0110831000000.5588650.2168180.0391750.0260440.04264310000005.2218792.1440890.3574280.2362770.3275391000000052.246422.022153.5932822.3357253.251762由上表和圖2可以看出，同重疊相加法類似，隨著數(shù)據(jù)規(guī)模的增大，運(yùn)算耗時(shí)呈線性增長(zhǎng)，算法的時(shí)間復(fù)雜度為O(n)，其中n為數(shù)據(jù)規(guī)模。同樣由于分配的緩存空間只由分段長(zhǎng)度確定，空間復(fù)雜度為O(1)。綜合考察，重疊保留法也

14、具有較好的時(shí)間和空間復(fù)雜度。當(dāng)數(shù)據(jù)量達(dá)到千萬(wàn)量級(jí)時(shí)，運(yùn)算延時(shí)最少大約為2.335s，可運(yùn)用于對(duì)信號(hào)的實(shí)時(shí)處理。C.調(diào)用conv()序列長(zhǎng)度1010010001000010000010000001000000運(yùn)算耗時(shí)(s)0.0001130.0000810.0001170.0002750.0024920.0321550.32588由上表和圖3可以看出，調(diào)用系統(tǒng)自帶的線性卷積運(yùn)算函數(shù)conv()計(jì)算線性卷積，運(yùn)算時(shí)間和序列長(zhǎng)度也有線性關(guān)系。時(shí)間復(fù)雜度為O(n)。但此時(shí)的信號(hào)處理延時(shí)很小，當(dāng)數(shù)據(jù)達(dá)到千萬(wàn)量級(jí)時(shí)，延時(shí)僅為0.325s，實(shí)時(shí)性非常好！D.綜合對(duì)比分析 分段長(zhǎng)度平均耗時(shí)(s)4101001

15、00010000重疊相加9.525273.9834970.6247690.3767690.531758重疊保留 8.2992433.4870560.5711880.3720560.523056調(diào)用conv() 0.051630.051630.051630.051630.05163重疊保留法和重疊相加法運(yùn)行效率與分段長(zhǎng)度相關(guān)性較強(qiáng)。分段數(shù)和卷積運(yùn)算的序列長(zhǎng)度為非線性關(guān)系，且當(dāng)分段長(zhǎng)度維持在大約1000點(diǎn)左右時(shí)，獲得最高的平均運(yùn)行效率。內(nèi)置函數(shù)conv()運(yùn)行效率與分段數(shù)無(wú)關(guān)。重疊相加和重疊保留兩者效率幾乎一致。在實(shí)際應(yīng)用中，重疊保留和重疊相加主要用于實(shí)施信號(hào)處理，因而輸入序列是連續(xù)輸入，在保證實(shí)

16、時(shí)性的要求下，輸入序列的分段不能太長(zhǎng)。設(shè)想實(shí)際情況如下：設(shè)語(yǔ)音信號(hào)采樣率為8KHz，相當(dāng)于每秒輸入8000點(diǎn)序列，由重疊相加法處理(重疊保留法類似)。如若分段為1000點(diǎn)，考慮實(shí)際系統(tǒng)中為實(shí)時(shí)輸出（Matlab算法模擬里面是將所有序列保存之后再輸出），因而每分段處理延時(shí)0.00406/8s，又接收1000點(diǎn)延時(shí)為1/8s，故處理總延時(shí)為0.1255075s。此時(shí)接收延時(shí)起主要作用，影響實(shí)時(shí)性。減小接收延時(shí)則需要減小分段點(diǎn)數(shù)，同時(shí)使得處理延時(shí)增加。接收延時(shí)和處理延時(shí)兩者是不可調(diào)和的矛盾。實(shí)際處理時(shí)，可根據(jù)實(shí)時(shí)性要求，折中選擇分段點(diǎn)數(shù)，既滿足實(shí)時(shí)性要求，又降低系統(tǒng)開銷。2、故障和問題分析分段問題初

17、始時(shí)沒有考慮到分段長(zhǎng)度的限制，導(dǎo)致用戶輸入分段小于系統(tǒng)沖擊響應(yīng)h(n)的長(zhǎng)度時(shí)運(yùn)算出錯(cuò)。后增加一個(gè)判斷語(yǔ)句，當(dāng)出現(xiàn)前述情況時(shí)，自動(dòng)提升分段點(diǎn)數(shù)，問題解決。運(yùn)算完整性問題在寫好代碼之后的測(cè)試中，出現(xiàn)了一個(gè)十分奇怪的現(xiàn)象，即：當(dāng)輸入點(diǎn)數(shù)為1000、10000或者更大時(shí)卷積運(yùn)算最后M-1個(gè)結(jié)果為0。反復(fù)測(cè)試發(fā)現(xiàn)，不僅1000和10000，只要是分段數(shù)N的倍數(shù)的輸入點(diǎn)數(shù)都存在同樣問題，而其他非倍數(shù)的輸入，運(yùn)算與conv() 函數(shù)運(yùn)算結(jié)果完全一致。通過(guò)設(shè)置斷點(diǎn)，逐句調(diào)試，最終發(fā)現(xiàn)問題的癥結(jié)，當(dāng)輸入序列為N的倍數(shù)時(shí)，最后的一段卷積實(shí)際上沒有做。因而將循環(huán)次數(shù)增加1，將最后一次保留的M-1個(gè)點(diǎn)補(bǔ)全N個(gè)0，做最后一次分段卷積。修改后，測(cè)試結(jié)果正確。算法硬件實(shí)現(xiàn)第一，重疊保留和重疊相加算法在硬件實(shí)現(xiàn)時(shí)將算法中的臨時(shí)變量都化為緩存，所以考慮緩存的大小限制，不能將輸入序列分段過(guò)長(zhǎng)，否則所需的緩存將加大，成本加大。第二，接收延時(shí)和處理延時(shí)兩者存在