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蝶形運(yùn)算符號

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

DIF-FFT第一次分解運(yùn)算流圖（N=8）

與時間抽取法的推導(dǎo)過程一樣，由于N=2M，N/2仍然是一個偶數(shù)，因而可以將每個N/2點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)DFT進(jìn)一步分解為兩個N/4點(diǎn)DFT。DIF基2FFT算法原理DIF-FFT第二次分解運(yùn)算流圖（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)運(yùn)算流圖DIF-FFT運(yùn)算流圖（N=8）按頻率抽選的FFT算法的特點(diǎn)1.原位運(yùn)算（同址運(yùn)算）實(shí)現(xiàn)全部運(yùn)算只需要一列存儲N個復(fù)數(shù)的寄存器。按頻率抽取的FFT(N=8)運(yùn)算流圖2.倒位序規(guī)律DIF-FFT的輸入為自然數(shù)順序，輸出為倒位序3.蝶形運(yùn)算按頻率抽選的FFT算法的特點(diǎn)1、M級運(yùn)算2、碟型運(yùn)算3、運(yùn)算量4、原位運(yùn)算頻域抽取與時間抽取法的異同相同點(diǎn)3.5快速傅里葉變換不同點(diǎn)DIT-FFTDIF-FFT輸出順序自然順序倒位序輸入順序倒位序自然順序碟形運(yùn)算頻域序列時間序列3.5快速傅里葉變換頻域抽取與時間抽取法的異同DIT基2FFT算法原理課前回顧課前回顧DIT-基2-FFT算法流圖（8點(diǎn)）DIF―FFT蝶形運(yùn)算符號

3.5快速傅里葉變換DIF基2FFT算法原理課前回顧課前回顧DIF-基2-FFT算法流圖（8點(diǎn)）修改FFT程序?qū)崿F(xiàn)IFFTFFT算法流圖也可以用于離散傅里葉逆變換(InverseDiscreteFourierTransform，IDFT)。比較DFT和IDFT的運(yùn)算公式：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）快速算法輸入序列輸出順序蝶形運(yùn)算運(yùn)算量運(yùn)算特點(diǎn)對象次序乘法次數(shù)加法次數(shù)DIT-FFT時序倒序頻序順序頻域序列先乘后加減原位運(yùn)算DIF-FFT時序順序頻序倒序時域序列先加減后乘原位運(yùn)算DIT-IFFT頻序順序時序倒序頻域序列先加減后乘原位運(yùn)算DIF-IFFT頻序倒序時序順序時域序列先乘后加減原位運(yùn)算

基2FFT算法正變換和反變換特點(diǎn)3.5快速傅里葉變換

DFTDFT

DFT

DFT

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

FFTFFT

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

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

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

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

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

實(shí)序列的F