數字信號處理

(DigitalSignalProcessing)

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

本章的重點是基2時間抽取FFT算法的基本原理，FFT蝶形運算流圖本章的難點是由短序列的DFT表達相應長序列的DFT的基本原理及方法時間抽取FFT問題的提出4點序列{2，3，3，2}DFT的計算復雜度復數加法N(N-1)復數乘法N

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

[0]X

[1]X

[2]X

[3]時間抽取FFT4點基2時間抽取FFT算法流圖時間抽取FFT8點基2時間抽取FFT算法流圖4點DFT4點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點DFT4點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點基2時間抽取FFT算法流圖時間抽取FFT第一級第二級第三級8點基2時間抽取FFT算法流圖時間抽取FFT算法的計算復雜度復乘次數復乘次數NN2時間抽取FFT基2時間抽取FFT算法流圖第一級第二級第三級時間抽取FFTFFT算法流圖旋轉因子規(guī)律第二級的蝶形系數為，蝶形節(jié)點的距離為2。第一級的蝶形系數均為，蝶形節(jié)點的距離為1。第三級的蝶形系數為，蝶形節(jié)點的距離為4。第M級的蝶形系數為，蝶形節(jié)點的距離為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例：試利用N=4基2時間抽取的FFT流圖計算8點序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：根據基2時間抽取FFT算法原理，8點序列的DFTX[m]可由兩個4點序列的DFTX1[m]和X2[m]表達。如果按照序列x[k]序號的奇偶分解為x1[k]和x2[k]，則存在其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通過4點的FFT來計算。時間抽取FFT例：試利用N=4基2時間抽取的FFT流圖計算8點序列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