FFT與DFT計(jì)算時(shí)間的比較及圓周卷積代替線性卷積的有效

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

2、卷積代替線性卷積，并比較圓周卷積法和直接計(jì)算線性卷積兩者的運(yùn)算速度。三預(yù)做實(shí)驗(yàn)v1.FFT與與DFT計(jì)算時(shí)間的比較計(jì)算時(shí)間的比較 （1）FFT提高運(yùn)算速度的原理 （2）實(shí)驗(yàn)數(shù)據(jù)與結(jié)論 v2.圓周卷積代替線性卷積的有效性實(shí)驗(yàn)圓周卷積代替線性卷積的有效性實(shí)驗(yàn) （1）圓周卷積代替線性卷積的原理 （2）實(shí)驗(yàn)數(shù)據(jù)和結(jié)論 FFT提高運(yùn)算速度的原理v 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，

3、對(duì)應(yīng)于N個(gè)輸入樣值，有N個(gè)頻域樣值與之對(duì)應(yīng)。v以基2時(shí)間按抽選法為例，分解遞推公式為：1212( )( )( )0,12()( )( )2kNkNX kX kW XkNkNX kX kW XkX1(K)和X2（K）分別對(duì)應(yīng)時(shí)間序列 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次降為 次乘法。 2log2NN實(shí)驗(yàn)數(shù)據(jù)與結(jié)論v令N為不同長(zhǎng)度的序列時(shí)，DFT和FFT的耗時(shí)比較：vN=512點(diǎn)時(shí)： dft_cost_time =0.3750s fft_cost_time =0

4、.0150svN=1024點(diǎn)時(shí)： dft_cost_time =2.9220s fft_cost_time =0.1250svN=2048點(diǎn)時(shí)： dft_cost_time =23.5000s； fft_cost_time =0.4690svN=4096點(diǎn)時(shí)： dft_cost_time =305.9530s fft_cost_time =103.9220sv有上面數(shù)據(jù)表明，同樣長(zhǎng)度的信號(hào)，DFT耗時(shí)要比FFT耗時(shí)要少，表明FFT算法的有效性。圓周卷積代替線性卷積的原理v線性卷積的長(zhǎng)度及運(yùn)算量 ；v用FFT算的步驟；v比較兩者乘法運(yùn)算量 ； 線性卷積的長(zhǎng)度及運(yùn)算量v 設(shè)一離散線性移不變系統(tǒng)的沖

5、激響應(yīng)為,其輸入信號(hào)為.其輸出為.并且的長(zhǎng)度為L(zhǎng)點(diǎn),的長(zhǎng)度為M點(diǎn),則： 10( )( )( )( ) ()Lmy nx nh nx m h nm10( )( )( )( ) ()Lmy nx nh nx m h nm10( )( )( )( ) ()Lmy nx nh nx m h nm1hnhMn 則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算的步驟 1.( ), ( )1 ;x n h nNML將補(bǔ)零點(diǎn)，至少為點(diǎn)2 .()()HkF F Thn求；3.( )( )X kFFT

6、x n求；1.( ), ( )1 ;x n h nNML將補(bǔ)零點(diǎn)，至少為點(diǎn)4.()()()YkXk Hk求；5.( )( )y nIFFT Y k求。流程圖( )x n( )h n( )X kIFFTFFTFFT( )Xk( )H k( )( )( )y nx n hn( )x n( )X k1.( )( )H kFFT h n求；2.( )( )X kFFT x n求；3.( )( )( )Y kX k H k求；4.( )( )y nIFFT Y k求。2log2NNN2log2NN2log2NN23log2NNN總運(yùn)算量：次乘法以上各步運(yùn)算量統(tǒng)計(jì)： 比較兩者乘法運(yùn)算量比較兩者乘法運(yùn)算量2

7、32(1log )2dmNFmLMKmN當(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超過(guò)64以后，M越長(zhǎng)圓周卷積的速度越快。當(dāng)輸入序列x(n)也表現(xiàn)不出來(lái)，此時(shí)可用重疊相加法和重疊保留法，進(jìn)行分段卷積，保障圓周卷積的優(yōu)勢(shì)。實(shí)驗(yàn)數(shù)據(jù)和結(jié)論v（1）兩個(gè)長(zhǎng)度為N/2=4096/2=2048點(diǎn)的序列直接線性卷積與N點(diǎn)的圓周卷積，兩過(guò)程的計(jì)算時(shí)間與計(jì)算結(jié)果比較v 計(jì)算時(shí)間比較：direct_convolution_time =0.0460s fft_convolution_time =0sv計(jì)算結(jié)果如

8、下所示40914092409340944095409640974098-0.2-0.100.10.20.30.40.50.60.7fft method circle convolutionN=4096點(diǎn)時(shí)圓周卷積的結(jié)果4092409340944095409640970.40.50.60.70.80.9direct convolution result兩個(gè)長(zhǎng)度為N/2=4096/2=2048點(diǎn)的序列直接線性卷積v（2）兩個(gè)長(zhǎng)度為N/2=8000/2=4000點(diǎn)的序列直接線性卷積與N點(diǎn)的圓周卷積，兩過(guò)程的計(jì)算時(shí)間與計(jì)算結(jié)果比較v計(jì)算時(shí)間比較：direct_convolution_time =0.1

9、560 fft_convolution_time =0.0160v計(jì)算結(jié)果如下所示：7993799479957996799779987999800000.20.40.60.811.2direct convolution result兩個(gè)長(zhǎng)度為N/2=8000/2=4000點(diǎn)的序列直接線性卷積7994799579967997799879998000800100.20.40.60.811.21.4fft method circle convolutionN=8000點(diǎn)時(shí)圓周卷積的結(jié)果v（3）兩個(gè)長(zhǎng)度為N/2=10000/2=5000點(diǎn)的序列直接線性卷積與N點(diǎn)的圓周卷積，兩過(guò)程的計(jì)算時(shí)間與計(jì)算結(jié)果比較v計(jì)算時(shí)間比較： direct_convolution_time =0.2500s fft_convolution_time =0.0470s99909991999299939994999599969997999899991000000.511.52direct convolution result兩個(gè)長(zhǎng)度為N/2=10000/2=5000點(diǎn)的序列直接線性卷積計(jì)算結(jié)果比較N=10000點(diǎn)時(shí)：99919992999399949995999699979998999910000-0.500.511.522.5fft method circle c