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

數(shù)字信號(hào)處理

(DigitalSignalProcessing)

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

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

2如何提高DFT的運(yùn)算效率?時(shí)間抽取FFT解決問(wèn)題的思路1.將長(zhǎng)序列DFT分解為短序列的DFT2.利用旋轉(zhuǎn)因子的周期性、對(duì)稱性、可約性。時(shí)間抽取FFT旋轉(zhuǎn)因子的性質(zhì)(1)周期性(2)對(duì)稱性(3)可約性時(shí)間抽取FFT解決問(wèn)題的方法將時(shí)域序列逐次分解為一組子序列，利用旋轉(zhuǎn)因子的特性，由子序列的DFT來(lái)實(shí)現(xiàn)整個(gè)序列的DFT?；?時(shí)間抽取(Decimationintime)FFT算法基2頻率抽取(Decimationinfrequency)FFT算法時(shí)間抽取FFT基2時(shí)間抽取FFT算法推導(dǎo)偶序列奇序列時(shí)間抽取FFT基2時(shí)間抽取FFT算法推導(dǎo)因此有:時(shí)間抽取FFT基2時(shí)間抽取FFT算法流圖N=2x[k]={x[0],x[1]}時(shí)間抽取FFT4點(diǎn)基2時(shí)間抽取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]時(shí)間抽取FFT4點(diǎn)基2時(shí)間抽取FFT算法流圖時(shí)間抽取FFT8點(diǎn)基2時(shí)間抽取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時(shí)間抽取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時(shí)間抽取FFT算法流圖時(shí)間抽取FFT第一級(jí)第二級(jí)第三級(jí)8點(diǎn)基2時(shí)間抽取FFT算法流圖時(shí)間抽取FFT算法的計(jì)算復(fù)雜度復(fù)乘次數(shù)復(fù)乘次數(shù)NN2時(shí)間抽取FFT基2時(shí)間抽取FFT算法流圖第一級(jí)第二級(jí)第三級(jí)時(shí)間抽取FFTFFT算法流圖旋轉(zhuǎn)因子規(guī)律第二級(jí)的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為2。第一級(jí)的蝶形系數(shù)均為，蝶形節(jié)點(diǎn)的距離為1。第三級(jí)的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為4。第M級(jí)的蝶形系數(shù)為，蝶形節(jié)點(diǎn)的距離為N/2。時(shí)間抽取FFT倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]01010101時(shí)間抽取FFT例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根據(jù)基2時(shí)間抽取FFT算法原理，8點(diǎn)序列的DFTX[m]可由兩個(gè)4點(diǎn)序列的DFTX1[m]和X2[m]表達(dá)。如果按照序列x[k]序號(hào)的奇偶分解為x1[k]和x2[k]，則存在其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通過(guò)4點(diǎn)的FFT來(lái)計(jì)算。時(shí)間抽取FFT例：試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算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