線性卷積和線性相關(guān)的FFT算法

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