案例十——線性卷積這樣算會快內(nèi)容概要案例設(shè)置目的相關(guān)基礎(chǔ)理論情境任務及步驟磨刀不誤砍柴工探尋圓周卷積與線性卷積的等價關(guān)系挑戰(zhàn)經(jīng)典思考題總結(jié)報告要求案例設(shè)置目的編制程序驗證圓周卷積和線性卷積的等價條件，理解線性卷積與圓周卷積的關(guān)系，掌握用圓周卷積計算線性卷積的快速實現(xiàn)方法；理解MATLAB函數(shù)conv的算法基礎(chǔ)；了解程序效率測試的基本方法。相關(guān)基礎(chǔ)理論設(shè)輸入序列x(n)僅在0≤n≤N1-1范圍內(nèi)有非零值，系統(tǒng)單位脈沖

響應h(n)僅在0≤n≤N2-1范圍內(nèi)有非零值，二者的線性卷積yl(n)和N點圓周卷積yc(n)可分別表示為(10.1)

(10.2)當圓周卷積計算點數(shù)N≥N1+N2-1時，在0≤n≤N-1范圍內(nèi)yl(n)和yc(n)完全相同，即yl(n)可以用計算yc(n)的方法進行計算。利用DFT的性質(zhì)，圓周卷積可以這樣計算：(10.3)其中Yc(k)=X(k)?H(k)。而根據(jù)序列DFT的定義，有限長序列x(n)的N（N>N1）點DFT可表示為(10.4)相關(guān)基礎(chǔ)理論若將序列x(n)寫成一個列向量x=[x(0),x(1),…,x(N-1)]T，當N≥M時x(M),…,x(N-1)取值為零，將N個X(k)值寫成一個列向量X=[X(0),X(1),…,X(N-1)]T，此時式（10.4）可改寫為：(10.5)h(n)的DFT結(jié)果H(k)也可用式（10.5）計算。綜上，利用圓周卷積計算線性卷積的過程可以概括為如下五步（1）確定循環(huán)卷積長度N，其中N≥N1+N2-1。若采用基2-FFT實現(xiàn)DFT的快速運算，還要求N=2m（m為整數(shù)）。（2）用補零方法使x(n)和h(n)變成列長為N的序列，即

(10.6)相關(guān)基礎(chǔ)理論（3）計算x(n)和h(n)的N點離散傅里葉變換

（H(k)只需計算一次）。（4）計算X(k)和H(k)乘積H(k)X(k)=Y(k)。（5）計算Y(k)的離散傅里葉反變換得

(10.7)從式（10.7）可以看出，序列的IFFT可以通過調(diào)用FFT的算法程序?qū)崿F(xiàn)，因而線性卷積的計算過程僅需編制一個FFT程序，而不用再單獨編寫IFFT程序。利用圓周卷積計算線性卷積的流程如圖10.1所示。圖10.1利用FFT的快速卷積實現(xiàn)框圖情境任務及步驟一、磨刀不誤砍柴工已知序列x1(n)={1,1,1,1}和x2(n)={1,2,3,4}。1.DFT怎么算、有何用（1）根據(jù)離散時間傅里葉變換的定義計算X1(ejω)，其中X1(ejω)=DTFT[x1(n)]，并畫出0~2

范圍內(nèi)|X1(ejω)|~ω的圖。（2）N分別取4、8和32，根據(jù)式（10.5）計算x1(n)的離散傅里葉變換，結(jié)果分別記為X4(k)、X8(k)和X32(k)，并分別畫出|X4(k)|~k、|X8(k)|~k和|X32(k)|~k的圖。需要說明的是這里畫|Xi(k)|~k的圖時補一個點的值，如i=4時，k取0,1,2,3,4，且這樣補充Xi(N)的值，即Xi(N)=Xi(0)。將所有的|Xi(k)|~k的圖與0~2

范圍內(nèi)|X1(ejω)|~ω的圖進行對比，其中i=4,8,32，歸納DFT的物理含義，理解DFT的用途。情境任務及步驟2．探究X(k)的隱含周期性（1）N取8，根據(jù)式（10.5）重新計算x1(n)的離散傅里葉變換，結(jié)果記為X8(k)，并畫出|X8(k)|~k的圖，這里畫圖時不進行補點。（2）將X8(k)中k的取值范圍從0~7擴大到0~48重新計算，結(jié)果記為X8-49(k)，并畫出|X8-49(k)|~k的圖，這里畫圖時不進行補點。需要提醒的是，在完成該項任務暫時先忽略式（10.4）中關(guān)于k取值范圍的限定，或者說將式（10.5）中矩陣的維數(shù)直接擴成49×8進行計算。（3）比較|X8(k)|~k和|X8-49(k)|~k的圖，從找共性的角度看，兩者有何關(guān)聯(lián)？（4）在探究“DFT怎么算、有何用”過程中，那樣補點是否合理？情境任務及步驟3．探究DFT的對稱性（1）N取8，根據(jù)式（10.5）重新計算x1(n)的離散傅里葉變換，結(jié)果記為X1(k)，計算x2(n)的離散傅里葉變換，結(jié)果記為X2(k)。（2）觀察Xi(k)與Xi(N-k)的值，你有何發(fā)現(xiàn)？i=1,2。（3）構(gòu)造復序列f(n)，其中f(n)=x1(n)+jx2(n)，并計算f(n)離散傅里葉變換的結(jié)果F(k)。（4）計算序列F(k)的共軛對稱部分Fe(k)和共軛反對稱部分Fo(k)，并將它們分別與X1(k)、X2(k)進行比較，你有何發(fā)現(xiàn)？

需要說明的是在MATLAB的語法中，標點“'”和“.’”對于復數(shù)矩陣是完全不同的兩種運算。假設(shè)c=[1+2j,3+4j]，你可以分別計算c’和c.’，便能明確二者的區(qū)別。情境任務及步驟二、探尋圓周卷積與線性卷積的等價關(guān)系已知序列x1(n)={1,1,1}和x2(n)={1,1,1,0,1}。1．編制基于DFT性質(zhì)的線性卷積計算程序根據(jù)【相關(guān)基礎(chǔ)理論】編制程序myconv計算兩個序列的線性卷積，要求如下：（1）輸入?yún)?shù)有三個，分別是輸入序列a、b和計算卷積的點數(shù)N；輸出參數(shù)為y，其中y為x(n)和h(n)的圓周卷積的結(jié)果序列。（2）myconv內(nèi)部要求調(diào)用函數(shù)fft計算兩序列的離散傅里葉變換，調(diào)用ifft計算離散傅里葉反變換，正反變換的點數(shù)均由參數(shù)N控制。2．直接計算卷積，確立比較基準（1）在workspace下調(diào)用MATLAB提供的conv函數(shù)計算x1(n)和x2(n)的線性卷積，并將結(jié)果記為y1。（2）在Figure1中顯示序列y1，要求橫軸顯示的范圍為0～9，縱軸顯示范圍為0～5，并用grid指令為子圖添加柵格。情境任務及步驟3．一驗自編函數(shù)在workspace下調(diào)用自己編制的函數(shù)myconv計算N=5的x1(n)和x2(n)線性卷積，將結(jié)果記為y2，并在Figure2中subplot(221)下顯示序列y2。要求橫軸顯示的范圍為0～9，縱軸顯示范圍為0～5，并用grid指令為子圖添加柵格。4．再驗自編函數(shù)在workspace下再次調(diào)用自己編制的函數(shù)myconv繼續(xù)分別計算N=6,7,8的x1(n)

和x2(n)線性卷積，將結(jié)果分別記為y3,y4,y5，并在Figure2中subplot(222)、subplot(223)、subplot(224)下分別顯示序列y3,y4,y5，要求橫軸顯示的范圍為0～9，縱軸顯示范圍為0～5，并用grid指令為每個子圖添加柵格，用title加注圖題。5．圓周卷積、線性卷積等價點數(shù)的關(guān)系逐樣點比較Figure2中各子圖所示序列與Figure1所示序列的異同，并總結(jié)在x1(n)

和x2(n)的長度一定、N(5～8)

取值一定的情況下，對應結(jié)果與Figure1所示序列等價樣點的個數(shù)。若只有部分樣點等價，通過比較判斷這些等價樣點是出現(xiàn)在序列的右側(cè)還是左側(cè)，將數(shù)據(jù)分析結(jié)果記入總結(jié)報告。情境任務及步驟三、挑戰(zhàn)經(jīng)典已知數(shù)字濾波器的單位脈沖響應為

N1=8，序列x(n)=cos(2πn/N2)?RN2(n),N2=8。（1）為N自選3組合適的取值，利用函數(shù)myconv分別計算三種不同點數(shù)的線性卷積，并在一個圖形窗口的三個子圖中顯示結(jié)果。（2）調(diào)用函數(shù)conv計算x(n)和h(n)的線性卷積，在新的圖形窗口中顯示計算結(jié)果。（3）對比兩種方法的計算效果，判斷N的選擇是否恰當，有無多余的零值點，有無樣點值不同的點，有多少個，如何調(diào)整N才能消除差異（4）在conv語句的上一行鍵入tic，下一行鍵入toc，myconv語句也進行同樣處理。重新執(zhí)行程序，將在命令窗口中返回的總結(jié)報告記入總結(jié)報告。思考題（1）當輸入序列為無窮長，而系統(tǒng)單位脈沖響應為M點長，按照