第4快速傅立葉變換課件

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

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

3、 1X 2X 3X 4X 5X 6X 7-1-1-1-18點(diǎn)基2時(shí)間抽取FFT算法流圖基2時(shí)間抽取FFT算法第一級(jí)第二級(jí)第三級(jí)算法的計(jì)算復(fù)雜度復(fù)乘次數(shù)復(fù)乘次數(shù)NN 2基2時(shí)間抽取FFT算法流圖第一級(jí)第二級(jí)第三級(jí)FFT算法流圖旋轉(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。倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x011x11101010101 基2頻率抽取FFT算

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