第四章

快速傅里葉變換(FFT)

主要內(nèi)容引言

直接計算DFT的特點時間抽取基2FFT算法頻率抽取基2FFT算法4.1引言DFT是信號分析與處理中的一種重要變換.直接計算DFT的計算量與變換區(qū)間長度N2成正比，當N較大時，計算量太大.在快速傅里葉變換(FFT)出現(xiàn)以前，直接用DFT算法進行譜分析和信號的實時處理是不切實際的.1965年發(fā)現(xiàn)了DFT的一種快速算法以后，情況發(fā)生了根本的變化.4.2直接計算DFT的特點長度為N的有限長序列x(n)的DFT為：其周期性表現(xiàn)為：其對稱性表現(xiàn)為：N點DFT的復乘次數(shù)等于N2.顯然，把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少.另外，旋轉(zhuǎn)因子具有明顯的周期性和對稱性.FFT算法就是不斷把長序列的DFT分解成幾個短序列的DFT，利用上述周期性和對稱性來減少DFT的運算次數(shù).FFT算法基本上分為兩大類：

(1)時域抽取法FFT(DecimationInTimeFFT,簡稱DIT—FFT).(2)頻域抽取法FFT(DecimationInFrequencyFFT,簡稱DIF—FFT).1、算法原理設(shè)輸入序列長為N=2M(M為正整數(shù))，將該序列按時間順序的奇偶分解為越來越短的子序列，稱為基2按時間抽取的FFT算法.若序列長度不滿足條件N=2M，可以加零補長使其達到N=2M.4.3時域抽取基2FFT算法要點：2、算法步驟要點：結(jié)論：只要求出(0~N/2-1)區(qū)間內(nèi)的各個整數(shù)k值所對應的X1(k)和X2(k)值，即可求出(0~N-1)整個區(qū)間內(nèi)全部X(k)值，這就是FFT節(jié)省計算量的關(guān)鍵.N=2M→N/2仍為偶數(shù)→可以進一步把每個N/2點子序列再按輸入n的奇偶分解為兩個N/4點的子序列→按這種方法不斷劃分，直到最后剩下2點DFT，兩點DFT實際上只是加減運算.3、蝶形運算符號求N=23=8點FFT.(1)將N=8的DFT分解成2個4點DFT【例題】N點DFT的一次時域抽取分解圖(N=8)⑵將4點DFT分解成2點的DFT將N/2(4點)子序列按奇/偶分解成兩個N/4點(2點)子序列。即將x1(r)和x2(r)分解成奇/偶兩個N/4點(2點)點的子序列。N點DFT的第二次時域抽取分解圖(N=8)⑶將2點DFT分解成2個1點DFT兩點DFT可分解成兩個1點DFT，而1點DFT就等于輸入信號本身，所以兩點DFT可用一個蝶形結(jié)表示.N點DIT-FFT運算流圖(N=8)每一級運算都需要N/2次復數(shù)乘和N次復數(shù)加(每個蝶形需要兩次復數(shù)加法).M級運算總共需要的復數(shù)乘次數(shù)為：4、DIT―FFT與直接DFT運算量的比較M級運算總共需要的復數(shù)加次數(shù)為：直接計算DFT的復數(shù)乘為N2次，復數(shù)加為N(N-1)次數(shù)。當N>>1時，N2>>(N/2)log2N。所以DIT-FFT算法比直接計算DFT的運算次數(shù)大大減少。例如：N=210=1024時：FFT算法與直接計算DFT所需乘法次數(shù)的比較曲線1、算法原理設(shè)輸入序列長度為N=2M(M為正整數(shù))，將該序列的頻域輸出序列X(k)按其頻域順序的奇偶分解為越來越短的子序列，稱基2按頻率抽取FFT算法.若序列長度不滿足條件N=2M，可以加零補長使其達到N=2M.4.4頻域抽取基2FFT算法2、算法步驟結(jié)論：3、蝶形運算符號求N=23=8點FFT.⑴先將N=8的DIF分解成2個4點DIF時域上：x(0)，x(1)，x(2)，x(3)為偶子序列；

x(4)，x(5)，x(6)，x(7)為奇子序列。頻域上：X(0)，X(2)，X(4)，X(6)由x1(n)給出.

X(1)，X(3)，X(5)，X(7)由x2(n)給出.【例題】其中:DIF-FFT一次分解運算流圖(N=8)⑵再將N=4的DIF分解成2個2點DIFDIF-FFT二次分解運算流圖(N=8)⑶再將N=2的DIF分解成2個1點DIF最后剩下兩點DFT，它可分解成兩個1點DFT，但1點DFT就等于輸入信號本身，所以兩點DFT可用一個蝶形結(jié)表示.DIF-FFT運算流圖(N=8)4.5IDFT的高效算法比較DFT和IDFT的運算公式：將DFT中的系數(shù)改為，最后乘