3.5 頻率抽取基2-FFT及IFFT

——頻率抽取基2-FFT及IFFT快速傅里葉變換(FFT)DIF基2FFT算法原理頻域抽取與時間抽取法的異同快速傅里葉反變換主要內(nèi)容快速傅里葉變換（2）N=2M偶數(shù)奇數(shù)DIF基2FFT算法原理3.5快速傅里葉變換3.5快速傅里葉變換DIF基2FFT算法原理DIF―FFT蝶形運算符號

3.5快速傅里葉變換DIF基2FFT算法原理

DIF-FFT第一次分解運算流圖（N=8）

與時間抽取法的推導(dǎo)過程一樣，由于N=2M，N/2仍然是一個偶數(shù)，因而可以將每個N/2點DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點DFT進(jìn)一步分解為兩個N/4點DFT。DIF基2FFT算法原理DIF-FFT第二次分解運算流圖（N=8）9按頻率(

k

的奇偶)抽取的第一次分解(N=8)X

(1)X

(3)X

(5)X

(7)k=0,2,4,6k=1,3,5,7X

(0)X

(2)X

(4)X

(6)DIF基2FFT算法原理10X

(0)X

(4)X

(2)X

(6)X

(1)X

(5)X

(3)X

(7)按頻率(

k

的奇偶)抽取的第二次分解(N=8)11按頻率抽取的FFT(N=8)運算流圖DIF-FFT運算流圖（N=8）按頻率抽選的FFT算法的特點1.原位運算（同址運算）實現(xiàn)全部運算只需要一列存儲N個復(fù)數(shù)的寄存器。按頻率抽取的FFT(N=8)運算流圖2.倒位序規(guī)律DIF-FFT的輸入為自然數(shù)順序，輸出為倒位序3.蝶形運算按頻率抽選的FFT算法的特點1、M級運算2、碟型運算3、運算量4、原位運算頻域抽取與時間抽取法的異同相同點3.5快速傅里葉變換不同點DIT-FFTDIF-FFT輸出順序自然順序倒位序輸入順序倒位序自然順序碟形運算頻域序列時間序列3.5快速傅里葉變換頻域抽取與時間抽取法的異同DIT基2FFT算法原理課前回顧課前回顧DIT-基2-FFT算法流圖（8點）DIF―FFT蝶形運算符號

3.5快速傅里葉變換DIF基2FFT算法原理課前回顧課前回顧DIF-基2-FFT算法流圖（8點）修改FFT程序?qū)崿F(xiàn)IFFTFFT算法流圖也可以用于離散傅里葉逆變換(InverseDiscreteFourierTransform，IDFT)。比較DFT和IDFT的運算公式：3.5快速傅里葉變換快速傅里葉反變換（IFFT）DIT-IFFTDIF-FFT3.5快速傅里葉變換快速傅里葉反變換（IFFT）X(k)共軛FFT程序共軛乘1/N調(diào)用FFT程序?qū)崿F(xiàn)IFFT3.5快速傅里葉變換快速傅里葉反變換（IFFT）調(diào)用FFT程序?qū)崿F(xiàn)IFFT利用IFFT的周期性對計算結(jié)果倒序排列即得到，注意快速傅里葉反變換（IFFT）快速算法輸入序列輸出順序蝶形運算運算量運算特點對象次序乘法次數(shù)加法次數(shù)DIT-FFT時序倒序頻序順序頻域序列先乘后加減原位運算DIF-FFT時序順序頻序倒序時域序列先加減后乘原位運算DIT-IFFT頻序順序時序倒序頻域序列先加減后乘原位運算DIF-IFFT頻序倒序時序順序時域序列先乘后加減原位運算

基2FFT算法正變換和反變換特點3.5快速傅里葉變換

DFTDFT

DFT

DFT

DFT實序列的FFT用一個N點FFT計算兩個實序列的FFT設(shè)x1(n)和x2(n)為兩個N點實序列,

FFTFFT

FFT實序列的FFT用一個N點FFT計算兩個實序列的FFT設(shè)x

(n)為2N點實序列實序列的FFT用N點復(fù)序列的FFT實現(xiàn)2N點實序列的FFT實序列的FFT用N點復(fù)序列的FFT實現(xiàn)2N點實序列的FFT

DFT運算量——復(fù)乘：N2，復(fù)加：N（N﹣1）時間抽取—基2—FFT算法☆☆

頻率域蝶形運算輸入倒位序，輸出自然順序運算量——復(fù)乘：，復(fù)加：DIF基2-FFT算法--小結(jié)頻域抽取—基2—FFT算法☆

時間域蝶形運算輸入自然順序，輸出倒位序運算量——復(fù)乘：，復(fù)加：IFFT方法——修改FFT程序、直接調(diào)用FFT程序

實序列的F