1、實(shí)驗(yàn)二 FFT與DFT計(jì)算時(shí)間的比較及圓周卷積代替線性卷積的有效性實(shí)驗(yàn),一 實(shí)驗(yàn)?zāi)康?二 實(shí)驗(yàn)內(nèi)容及要求 三 預(yù)做實(shí)驗(yàn),一 實(shí)驗(yàn)?zāi)康?1：掌握FFT基2時(shí)間（或基2頻率）抽選法，理解其提高減少乘法運(yùn)算次數(shù)提高運(yùn)算速度的原理。 2：掌握FFT圓周卷積實(shí)現(xiàn)線性卷積的原理,二 實(shí)驗(yàn)內(nèi)容及要求,1.對(duì)N=2048或4096點(diǎn)的離散時(shí)間信號(hào)x(n)，試用Matlab語言編程分別以DFT和FFT計(jì)算N個(gè)頻率樣值X(k), 比較兩者所用時(shí)間的大小。 2.對(duì)N/2點(diǎn)長(zhǎng)的x(n)和N/2點(diǎn)長(zhǎng)的h(n)，試用Matlab語言編程實(shí)現(xiàn)以圓周卷積代替線性卷積，并比較圓周卷積法和直接計(jì)算線性卷積兩者的運(yùn)算速度。,三預(yù)做

2、實(shí)驗(yàn),1.FFT與DFT計(jì)算時(shí)間的比較 （1）FFT提高運(yùn)算速度的原理 （2）實(shí)驗(yàn)數(shù)據(jù)與結(jié)論 2.圓周卷積代替線性卷積的有效性實(shí)驗(yàn) （1）圓周卷積代替線性卷積的原理 （2）實(shí)驗(yàn)數(shù)據(jù)和結(jié)論,FFT提高運(yùn)算速度的原理,FFT算法將長(zhǎng)序列的DFT分解為短序列的DFT。N點(diǎn)的DFT先分解為2個(gè)N/2點(diǎn)的DFT，每個(gè)N/2點(diǎn)的DFT又分解為N/4點(diǎn)的DFT，等等。最小變換的點(diǎn)數(shù)即所謂的“基數(shù)”。因此，基數(shù)為2的FFT算法的最小變換（或稱蝶型）是2點(diǎn)的DFT。一般地，對(duì)N點(diǎn)FFT，對(duì)應(yīng)于N個(gè)輸入樣值，有N個(gè)頻域樣值與之對(duì)應(yīng)。,以基2時(shí)間按抽選法為例，分解遞推公式為：,X1(K)和X2（K）分別對(duì)應(yīng)時(shí)間序列

3、 x(n)的的偶、奇序列 N/2點(diǎn)長(zhǎng)的DFT，以此方法分解下去，得到兩點(diǎn)長(zhǎng)N/2為組的離散時(shí)間分組結(jié)果。在一次由兩點(diǎn)DFT復(fù)合產(chǎn)生4、8、16到N點(diǎn)的最后結(jié)果。運(yùn)算量由N*N次降為 次乘法。,實(shí)驗(yàn)數(shù)據(jù)與結(jié)論,令N為不同長(zhǎng)度的序列時(shí)，DFT和FFT的耗時(shí)比較： N=512點(diǎn)時(shí)： dft_cost_time =0.3750s fft_cost_time =0.0150s N=1024點(diǎn)時(shí)： dft_cost_time =2.9220s fft_cost_time =0.1250s N=2048點(diǎn)時(shí)： dft_cost_time =23.5000s； fft_cost_time =0.4690s N

4、=4096點(diǎn)時(shí)： dft_cost_time =305.9530s fft_cost_time =103.9220s 有上面數(shù)據(jù)表明，同樣長(zhǎng)度的信號(hào)，DFT耗時(shí)要比FFT耗時(shí)要少，表明FFT算法的有效性。,圓周卷積代替線性卷積的原理,線性卷積的長(zhǎng)度及運(yùn)算量 ； 用FFT算的步驟； 比較兩者乘法運(yùn)算量 ；,線性卷積的長(zhǎng)度及運(yùn)算量,設(shè)一離散線性移不變系統(tǒng)的沖激響應(yīng)為,其輸入信號(hào)為.其輸出為.并且的長(zhǎng)度為L(zhǎng)點(diǎn),的長(zhǎng)度為M點(diǎn),則：,則y(n)的長(zhǎng)度為L(zhǎng)+M-1。,線性卷積的乘法運(yùn)算量為L(zhǎng)M次，又由于FIR濾波 器 h(n)的特性是對(duì)稱序列即,因而，乘法運(yùn)算次數(shù)減半，即為L(zhǎng)M/2。,用FFT算的步驟,流

5、程圖,以上各步運(yùn)算量統(tǒng)計(jì)：,比較兩者乘法運(yùn)算量,當(dāng)h(n)和x(n)長(zhǎng)度相當(dāng)時(shí)，若M較短時(shí)，e.g.為8，16，32時(shí),圓周卷積的時(shí)間大于直接線性卷積的結(jié)果；當(dāng)M=64時(shí)，兩者的運(yùn)算速度相當(dāng)，當(dāng)M超過64以后，M越長(zhǎng)圓周卷積的速度越快。當(dāng)輸入序列x(n)也表現(xiàn)不出來，此時(shí)可用重疊相加法和重疊保留法，進(jìn)行分段卷積，保障圓周卷積的優(yōu)勢(shì)。,實(shí)驗(yàn)數(shù)據(jù)和結(jié)論,（1）兩個(gè)長(zhǎng)度為N/2=4096/2=2048點(diǎn)的序列直接線性卷積與N點(diǎn)的圓周卷積，兩過程的計(jì)算時(shí)間與計(jì)算結(jié)果比較 計(jì)算時(shí)間比較：direct_convolution_time =0.0460s fft_convolution_time =0s 計(jì)

6、算結(jié)果如下所示,N=4096點(diǎn)時(shí)圓周卷積的結(jié)果,兩個(gè)長(zhǎng)度為N/2=4096/2=2048點(diǎn)的序列直接線性卷積,（2）兩個(gè)長(zhǎng)度為N/2=8000/2=4000點(diǎn)的序列直接線性卷積與N點(diǎn)的圓周卷積，兩過程的計(jì)算時(shí)間與計(jì)算結(jié)果比較 計(jì)算時(shí)間比較：direct_convolution_time =0.1560 fft_convolution_time =0.0160 計(jì)算結(jié)果如下所示：,兩個(gè)長(zhǎng)度為N/2=8000/2=4000點(diǎn)的序列直接線性卷積,N=8000點(diǎn)時(shí)圓周卷積的結(jié)果,（3）兩個(gè)長(zhǎng)度為N/2=10000/2=5000點(diǎn)的序列直接線性卷積與N點(diǎn)的圓周卷積，兩過程的計(jì)算時(shí)間與計(jì)算結(jié)果比較 計(jì)算時(shí)間比較： direct_convolution_time =0.2500s fft_convolution_time =0.0470s,兩個(gè)長(zhǎng)度為N/2=10000/2=5000點(diǎn)的序列直接線性卷積,計(jì)算結(jié)果比較N=10000點(diǎn)時(shí)：,N=10000點(diǎn)時(shí)圓周卷積的結(jié)果,數(shù)據(jù)分析與結(jié)論,通過以上三組數(shù)據(jù)比較，證實(shí)了圓周卷積代替