數(shù)字信號處理ch3-1時間抽取FFT

數(shù)字信號處理

(DigitalSignalProcessing)

離散傅里葉變換快速算法(FFT)問題的提出解決問題的思路與方法基2時間抽取FFT算法基2時間抽取FFT算法的計算復(fù)雜度基2時間抽取FFT算法流圖規(guī)律基2頻率抽取FFT算法FFT算法的實(shí)際應(yīng)用時間抽取FFT學(xué)習(xí)要求掌握基2時間抽取和基2頻率抽取FFT算法原理和方法。了解基4時間抽取FFT算法的基本原理。掌握實(shí)序列FFT計算方法。掌握由N點(diǎn)序列FFT計算2N點(diǎn)序列FFT的方法。掌握利用FFT計算IDFT的原理及過程。時間抽取FFT重點(diǎn)和難點(diǎn)

本章的重點(diǎn)是基2時間抽取FFT算法的基本原理，F(xiàn)FT蝶形運(yùn)算流圖本章的難點(diǎn)是由短序列的DFT表達(dá)相應(yīng)長序列的DFT的基本原理及方法時間抽取FFT問題的提出4點(diǎn)序列{2，3，3，2}DFT的計算復(fù)雜度復(fù)數(shù)加法N(N-1)復(fù)數(shù)乘法N

2如何提高DFT的運(yùn)算效率?時間抽取FFT解決問題的思路1.將長序列DFT分解為短序列的DFT2.利用旋轉(zhuǎn)因子的周期性、對稱性、可約性。時間抽取FFT旋轉(zhuǎn)因子的性質(zhì)(1)周期性(2)對稱性(3)可約性時間抽取FFT解決問題的方法將時域序列逐次分解為一組子序列，利用旋轉(zhuǎn)因子的特性，由子序列的DFT來實(shí)現(xiàn)整個序列的DFT?；?時間抽取(Decimationintime)FFT算法基2頻率抽取(Decimationinfrequency)FFT算法時間抽取FFT基2時間抽取FFT算法推導(dǎo)偶序列奇序列時間抽取FFT基2時間抽取FFT算法推導(dǎo)因此有:時間抽取FFT基2時間抽取FFT算法流圖N=2x[k]={x[0],x[1]}時間抽取FFT4點(diǎn)基2時間抽取FFT算法流圖x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2點(diǎn)DFT2點(diǎn)DFT-1-1-1-1X

[0]X

[1]X

[2]X

[3]時間抽取FFT4點(diǎn)基2時間抽取FFT算法流圖時間抽取FFT8點(diǎn)基2時間抽取FFT算法流圖4點(diǎn)DFT4點(diǎn)DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-1時間抽取FFT4點(diǎn)DFT4點(diǎn)DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X

[0]X

[1]X

[2]X

[3]X

[4]X

[5]X

[6]X

[7]-1-1-1-18點(diǎn)基2時間抽取FFT算法流圖時間抽取FFT第一級第二級第三級8點(diǎn)基2時間抽取FFT算法流圖時間抽取FFT算法的計算復(fù)雜度復(fù)乘次數(shù)復(fù)乘次數(shù)NN2時間抽取FFT基2時間抽取FFT算法流圖第一級第二級第三級時間抽取FFTFFT算法流圖旋轉(zhuǎn)因子規(guī)律第二級的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為2。第一級的蝶形系數(shù)均為，蝶形節(jié)點(diǎn)的距離為1。第三級的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為4。第M級的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為N/2。時間抽取FFT倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]01010101時間抽取FFT例：試?yán)肗=4基2時間抽取的FFT流圖計算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根據(jù)基2時間抽取FFT算法原理，8點(diǎn)序列的DFTX[m]可由兩個4點(diǎn)序列的DFTX1[m]和X2[m]表達(dá)。如果按照序列x[k]序號的奇偶分解為x1[k]和x2[k]，則存在其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通過4點(diǎn)的FFT來計算。時間抽取FFT例：試?yán)肗=4基2時間抽取的FFT流圖計算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：

X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3