1、第四章 快速傅里葉變換4.1 直接計(jì)算N點(diǎn)DFT的運(yùn)算量4.2 按時(shí)間抽取的FFT算法4.3 按頻率抽取的FFT算法4.4 IDFT的快速算法4.5 實(shí)序列的DFT計(jì)算1直接計(jì)算N點(diǎn)DFT的運(yùn)算量結(jié)論：運(yùn)算量：4.1 直接計(jì)算N點(diǎn)DFT的運(yùn)算量2減少運(yùn)算量的基本途徑4.2 按時(shí)間抽取（DIT）的基2 FFT算法當(dāng)N =2L時(shí)，將x(n)按奇偶分成的序列：1基2 DIT-FFT算法原理DIT:庫利-圖基算法（1965年庫利提出的）1805年高斯提出，未得到重視。則x(n)的DFT為:4.2 按時(shí)間抽取（DIT）的基2 FFT算法由于所以4.2 按時(shí)間抽取（DIT）的基2 FFT算法代換利用對稱性

2、及同理X(k)的前一半X(k)的后一半?4.2 按時(shí)間抽取（DIT）的基2 FFT算法X(k)的后一半為:4.2 按時(shí)間抽取（DIT）的基2 FFT算法蝶形流圖表示:4.2 按時(shí)間抽取（DIT）的基2 FFT算法4.2 按時(shí)間抽取（DIT）的基2 FFT算法4.2 按時(shí)間抽取（DIT）的基2 FFT算法2點(diǎn)DFT2點(diǎn)DFT4.2 按時(shí)間抽取（DIT）的基2 FFT算法4.2 按時(shí)間抽取（DIT）的基2 FFT算法2DIT-FFT算法的運(yùn)算量特點(diǎn)：運(yùn)算量：DFT與FFT的運(yùn)算量之比：表1 DFT與FFT算法的比較 結(jié)論：N越大，F(xiàn)FT算法的優(yōu)越性越明顯。NN22414.041644.086412

3、5.416256328.03210248012.864409619221.41281638444836.625665536102464.05122621442304113.8102410485765120204.82048419430411264372.44.2 按時(shí)間抽取（DIT）的基2 FFT算法4.2 按時(shí)間抽取（DIT）的基2 FFT算法3DIT-FFT算法的特點(diǎn)(1)原位計(jì)算4.2 按時(shí)間抽取（DIT）的基2 FFT算法(2)輸入序列倒序順序與倒序二進(jìn)制數(shù)對照表 倒序（輸入）順序（輸出）十進(jìn)制數(shù)I二進(jìn)制數(shù)二進(jìn)制數(shù)十進(jìn)制數(shù)J0000000041000011201001026110011

4、310011004510110153011110671111117(3)旋轉(zhuǎn)因子的變化規(guī)律4.2 按時(shí)間抽取（DIT）的基2 FFT算法-1-1-1-1-1-1-1-1-1x(0)x(14)x(6)x(8)x(12)x(2)x(10)x(4)x(1)x(15)x(7)x(9)x(13)x(3)x(11)x(5)-1-1-1-1-1-1-1-1-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1-1-1-1-1-1-1-1X(8)X(9)X(10)X(11)X(12)X(13)X(14)X(15)N=16,按時(shí)間抽取FFT流圖4.2 按時(shí)間抽取（DIT

5、）的基2 FFT算法原位計(jì)算解：N=4，按時(shí)間抽取FFT流圖-1-1x(0)x(2)x(3)x(1)-1X(0)X(1)X(2)X(3)X1(0)X1(1)X2(0)X2(1)-1例1.已知x(n)=1,-1,0,1 0n3，利用基2 DIT計(jì)算x(n)的DFT。4.2 按時(shí)間抽取（DIT）的基2 FFT算法4.2 按時(shí)間抽取（DIT）的基2 FFT算法將x(n)前后對半分開，得到兩個(gè)序列:1基2 DIF-FFT算法原理4.3 按頻率抽取（DIF）的基2 FFT算法DIF:桑德-圖基算法（1966年桑德提出的）4.3 按頻率抽取（DIF）的基2 FFT算法4.3 按頻率抽取（DIF）的基2 F

6、FT算法4.3 按頻率抽取（DIF）的基2 FFT算法4.3 按頻率抽取（DIF）的基2 FFT算法 DIF-FFT蝶形運(yùn)算流圖:4.3 按頻率抽取（DIF）的基2 FFT算法N=8時(shí)一次分解的運(yùn)算流圖如圖所示4.3 按頻率抽取（DIF）的基2 FFT算法4點(diǎn)DFT4點(diǎn)DFT按頻率抽取FFT流圖（N=8）4.3 按頻率抽取（DIF）的基2 FFT算法4.3 按頻率抽取（DIF）的基2 FFT算法2DIF-FFT算法的運(yùn)算量特點(diǎn)：運(yùn)算量：DFT與FFT的運(yùn)算量之比：4.3 按頻率抽取（DIF）的基2 FFT算法3DIF-FFT算法的特點(diǎn)(1)原位計(jì)算4.3 按頻率抽取（DIF）的基2 FFT算法(2)輸出序列倒序順序（輸入）倒序（輸出）十進(jìn)制數(shù)I二進(jìn)制數(shù)二進(jìn)制數(shù)十進(jìn)制數(shù)J000