第4快速傅立葉變換課件

1、第4章 快速傅立葉變換問題的提出解決問題的思路與方法 基2時間抽取FFT算法基2時間抽取FFT算法的計算復雜度基2時間抽取FFT算法流圖規(guī)律基2頻率抽取FFT算法FFT算法的實際應用問題的提出4點序列2，3，3，2 DFT的計算復雜度復數(shù)加法N(N-1)復數(shù)乘法N 2如何提高DFT的運算效率?解決問題的思路1. 將長序列DFT分解為短序列的DFT2. 利用旋轉(zhuǎn)因子 的周期性、對稱性、可約性。旋轉(zhuǎn)因子 的性質(zhì)1)周期性2) 對稱性3)可約性解決問題的方法將時域序列逐次分解為一組子序列，利用旋轉(zhuǎn)因子的特性，由子序列的DFT來實現(xiàn)整個序列的DFT?；?時間抽取(Decimation in time)

2、FFT算法基2頻率抽取(Decimation in frequency)FFT算法基2時間抽取FFT算法流圖N=2xk=x0, x14點基2時間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點DFT2點DFT-1-1-1-1X 0X 1X 2X 34點基2時間抽取FFT算法流圖8點基2時間抽取FFT算法流圖4點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-14點DFT4點DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X

3、 1X 2X 3X 4X 5X 6X 7-1-1-1-18點基2時間抽取FFT算法流圖基2時間抽取FFT算法第一級第二級第三級算法的計算復雜度復乘次數(shù)復乘次數(shù)NN 2基2時間抽取FFT算法流圖第一級第二級第三級FFT算法流圖旋轉(zhuǎn)因子 規(guī)律第二級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為2。第一級的蝶形系數(shù)均為 ，蝶形節(jié)點的距離為1。第三級的蝶形系數(shù)為 ，蝶形節(jié)點的距離為4。第M級 的蝶形系數(shù)為 ，蝶形節(jié)點的距離為N /2。倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x011x11101010101 基2頻率抽取FFT算

4、法3NW-12NW-11NW-10NW-1x0 x4x1x5x2x6x3x74點DFTX0X6X2X44點DFTX1X3X5X7X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2點DFT-1-12NW0NW-1-12點DFT2點DFT2點DFT0NW1NW2NW3NW-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1FFT算法應用利用N點復序列的FFT計算兩個N點實序列FFT利用N點復序列的FFT，計算2N點序列的FFT利用FFT計算IFFT利用N點復序列的FFT算法計算兩個N點實序列FFTx1k, x2k是實序列，將其構(gòu)成復序列yk=x1k+j x2kDFTx1k+j x2k=YR m+jYI m利用N點復序列的FFT，計算2N點序列的FFTyk是一個長度為2