FFT與DFT計算時間的比較及圓周卷積代替線性卷積的有效

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

2、卷積代替線性卷積，并比較圓周卷積法和直接計算線性卷積兩者的運(yùn)算速度。三預(yù)做實驗v1.FFT與與DFT計算時間的比較計算時間的比較 （1）FFT提高運(yùn)算速度的原理 （2）實驗數(shù)據(jù)與結(jié)論 v2.圓周卷積代替線性卷積的有效性實驗圓周卷積代替線性卷積的有效性實驗 （1）圓周卷積代替線性卷積的原理 （2）實驗數(shù)據(jù)和結(jié)論 FFT提高運(yùn)算速度的原理v FFT算法將長序列的DFT分解為短序列的DFT。N點(diǎn)的DFT先分解為2個N/2點(diǎn)的DFT，每個N/2點(diǎn)的DFT又分解為N/4點(diǎn)的DFT，等等。最小變換的點(diǎn)數(shù)即所謂的“基數(shù)”。因此，基數(shù)為2的FFT算法的最小變換（或稱蝶型）是2點(diǎn)的DFT。一般地，對N點(diǎn)FFT，

3、對應(yīng)于N個輸入樣值，有N個頻域樣值與之對應(yīng)。v以基2時間按抽選法為例，分解遞推公式為：1212( )( )( )0,12()( )( )2kNkNX kX kW XkNkNX kX kW XkX1(K)和X2（K）分別對應(yīng)時間序列 x(n)的的偶、奇序列 N/2點(diǎn)長的DFT，以此方法分解下去，得到兩點(diǎn)長N/2為組的離散時間分組結(jié)果。在一次由兩點(diǎn)DFT復(fù)合產(chǎn)生4、8、16到N點(diǎn)的最后結(jié)果。運(yùn)算量由N*N次降為 次乘法。 2log2NN實驗數(shù)據(jù)與結(jié)論v令N為不同長度的序列時，DFT和FFT的耗時比較：vN=512點(diǎn)時： dft_cost_time =0.3750s fft_cost_time =0

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

5、激響應(yīng)為,其輸入信號為.其輸出為.并且的長度為L點(diǎn),的長度為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)的長度為L+M-1。 線性卷積的乘法運(yùn)算量為LM次，又由于FIR濾波 器 h(n)的特性是對稱序列即 因而，乘法運(yùn)算次數(shù)減半，即為LM/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)計： 比較兩者乘法運(yùn)算量比較兩者乘法運(yùn)算量2

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

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

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