1、第第3 3章章 快速付里葉變換快速付里葉變換(FFT)(FFT) Fast FourierFast Fourier TransformingTransformingu離散傅里葉變換在實際應用中是非常重要的，利用它可以計算信號的頻譜、功率譜和線性卷積等.u但是，如果使用定義式來直接計算DFT，當N很大時，DFT的計算量太大，即使使用高速計算機，所花的時間也太多，很難對問題進行實時處理。所以在相當長的時間里，并沒有得到真正的運用。因此，如何提高計算DFT的速度，便成了重要的研究課題。快速付里葉變換快速付里葉變換(FFT)(FFT) 1965年庫利（J.W.Cooley）和圖基（J.W.Tukey）

2、首次提出了DFT運算的一種快速算法，后來又有桑德（G.Sande）和圖基（J.W.Tukey）的快速算法相繼出現以后，情況才發生了根本的變化。人們開始認識到DFT運算的一些內在規律，從而很快地發展和完善了一套高速有效的運算方法，這就是現在人們普遍稱之為快速傅里葉變換（FFT）的算法。 快速付里葉變換快速付里葉變換(FFT)(FFT)FFT的出現，使計算DFT的計算量可縮短一、二個數量級，還有效地減少了計算所需的存儲容量，從而成為數字信號處理強有力的工具。FFT技術的應用極大地推動了DSP的理論和技術的發展，使DFT的運算在實際中真正得到了廣泛的應用。uFFTFFT:各種各樣快速計算DFT的方法

3、，統稱為快速傅里葉變換(Fast Fourier Transform)，簡稱為FFT?？焖俑独锶~變換快速付里葉變換(FFT)(FFT) FFTFFT:快速傅里葉變換（Fast Fourier Transform，簡稱為FFT）并不是一種新的變換， 而是離散傅里葉變換（DFT）的一種快速算法。由于有限長序列在其頻域也可離散化為有限長序列（DFT），因此離散傅里葉變換（DFT）在數字信號處理中是非常有用的?？焖俑独锶~變換快速付里葉變換(FFT)(FFT) 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 10NknNnX kx n W 101NknNk

4、x nXk WNDFTDFT及及IDFTIDFT的定義的定義0,1,1kN0,1,1nN將將DFTDFT定義式展開成方程組定義式展開成方程組：將方程組寫成矩陣形式將方程組寫成矩陣形式用向量表示用向量表示： 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 FFTFFT算法是基于可以將一個長度為算法是基于可以將一個長度為N N的序的序列的離散傅里葉變換逐次分解為

5、較短的列的離散傅里葉變換逐次分解為較短的離散傅里葉變換來計算這一基本原理的。離散傅里葉變換來計算這一基本原理的。這一原理產生了許多不同的算法，但它這一原理產生了許多不同的算法，但它們在計算速度上均取得了大致相當的改們在計算速度上均取得了大致相當的改善。善。3.1 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 nkNnkNWW*)(（2 2） W WN Nnknk的周期性的周期性 )()(NknNkNnNnkNWWW（3 3） W WN Nnknk的可

6、約性的可約性 mnkmNnkNnmkmNnkNWWWW/,kNNkNWW)2/(（1 1） W WN Nnknk的對稱性的對稱性 的特性的特性:nkNWnkNknNNkNnNWWW)()(10NW12/NNWjWNN4/ 3.1 直接計算直接計算DFTDFT的特點及減少運的特點及減少運 算量的基本途徑算量的基本途徑 的特性的特性:nkNWFFT DIT:按時間抽取法 （Decimation-in-Time） DIF:按頻率抽取法 （Decimation-in-Frequency）。 按時間抽?。―IT）的基-2 FFT算法的基本出發點是，利用旋轉因子WN nk的對稱性和周期性，將一個長序列的D

7、FT分解為一些逐次變小的DFT來計算。分解過程遵循兩條規則： 對時間進行奇偶分解； 對頻率進行前后分解。3 3.2.2 按時間抽?。ò磿r間抽取（DITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原理（庫利-圖基算法）3 3.2.2 按時間抽?。ò磿r間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原理（庫利-圖基算法） 設序列x(n)的長度為N，且M為自然數N-point DFTMN22logMN 10,0,1,.,1NknNnX kx n WkN將其一分為二，分成偶數和奇數序列項（the even-indexed and odd-indexed terms）則

8、N/2點的序列為： even: x1(r)=x(2r), r=0, 1, , N/2-1 odd: x2(r)=x(2r+1) , r=0, 1, , N/2-13 3.2.2 按時間抽取（按時間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原理（庫利-圖基算法）偶數序列偶數序列 the range: 02rN-2 (N is even) 0r(N/2)-1奇數序列奇數序列 the range: 12r+1N-1 (N is even) 02rN-2 0r(N/2)-13 3.2.2 按時間抽?。ò磿r間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原

9、理（庫利-圖基算法）3 3.2.2 按時間抽?。ò磿r間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原理（庫利-圖基算法） 則則x(n)的的DFT：rkNNrkNrkNNrkrNNrrkNNrNnnnkNNnNnnnkNnkNWrxWWrxWrxWrxWnxWnxWnxnxDFTkX)()( )() 12()2()()()()()(2120221201) 12(1202120101010為奇數為偶數故故: :2/2/2222NNjNjNWeeWx(n)的的DFT：由于由于:)()()()()()( )()(212/21202/11202120221201kXWkXWrxW

10、WrxWrxWWrxkXkNrkNNrkNrkNNrrkNNrkNrkNNrN/2-point DFTrkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201) 12()()()2()()()()()(21kXWkXkXkNx x( (n n) )的前的前N N/2-point DFT/2-point DFT：k=0, 1, , N/2-1222221NkXWNkXNkXNkNx x( (n n) )的后的后N N/2-point DFT/2-point DFT：rkNNkrNWW2/22/)()()(212/120122/120

11、11kXWrxWrxkNXrkNNrkNrNNr W WN Nnknk的周期性的周期性 )()(NknNkNnNnkNWWWx(n)的的DFT：)(222kXkNX0,1,12Nk kNkNNNkNNWWWW2/2)()(221kXWkXNkXkN222221NkXWNkXNkXNkNx x( (n n) )的后的后N N/2-point DFT/2-point DFT：0,1,12Nk )()(221kXWkXNkXkN)()()(21kXWkXkXkNx x( (n n) )的的N N-point DFT-point DFT：表示上述算法可用蝶形結（表示上述算法可用蝶形結（ butterf

12、ly butterfly） 蝶形運算符號作圖要素：作圖要素：(1)左邊兩路為輸入(2)右邊兩路為輸出(3)中間以一個小圓表示加、減運算（右上路為相加輸出、右下路為相減輸出)(4)如果在某一支路上信號需要進行相乘運算，則在該支路上標以箭頭，將相乘的系數標在箭頭旁。(5)當支路上沒有箭頭及系數時，則該支路的傳輸比為1。0,1,12Nk )()(221kXWkXNkXkN)()()(21kXWkXkXkNx x( (n n) )的的N N-point DFT-point DFT：運算量？運算量？22N24N24N24N22N2N運算量？運算量？)()(221kXWkXNkXkN)()()(21kXW

13、kXkXkN運算量？運算量？x(n)x(n)y(n)y(n)數字信數字信號處理號處理？ 例：直接計算直接計算DFT【例例：】 計算有限長序列, N=4的DFT X(k)。【解】 由于x(n)是4點序列，因此X(k)也是4點序列。 ( )2, 4, 3, 4x n 340,03nknX kx n Wk 2j44ejW 所以，若將所以，若將k k的具體值代入，可得的具體值代入，可得 x(n)x(n)y(n)y(n)數字信數字信號處理號處理？ 例：離散傅里葉變換（離散傅里葉變換（DFT）300(0)( )( j)(0)(1)(2)(3)24349nnXx nxxxx 3100123(1)( ) (

14、j)(0) ( j)(1) ( j)(2) ( j)(3) ( j)2 14 ( j)3 ( 1)4j5nnXx nxxxx 3200246(2)( ) ( j)(0) ( j)(1) ( j)(2) ( j)(3) ( j)2 14 ( 1)3 ( 1)4 ( 1)7nnXx nxxxx x(n)x(n)y(n)y(n)數字信數字信號處理號處理？例：例： 離散傅里葉變換（離散傅里葉變換（DFT）因此，得到x(n)的DFT為 3300369(3)( ) ( j)(0) ( j)(1) ( j)(2) ( j)(3) ( j)2 14 (j)3 ( 1)4 ( j)5nnXx nxxxx ( )

15、9,5,7,5X k （1 1）先按）先按N N=8-N/2=4=8-N/2=4，做，做4 4點的點的DFTDFT： 1212/2kNkNX kX kW XkX kNX kW Xk12/, 0Nk 例：求例：求 N N=2=23 3=8=8點點FFTFFT變換變換rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201) 12()()()2()()( 例：求例：求 N N=2=23 3=8=8點點FFTFFT變換變換 將N=8點DFT分解成2個4點DFT： 時域上時域上：x(0),x(2),x(4),x(6)為偶子序列 x(1),

16、x(3),x(5),x(7)為奇子序列 頻域上頻域上：X(0)X(3)，由X(k)給出 X(4)X(7),由X(k+N/2)給出將將N=8N=8點分解成點分解成2 2個個4 4點的點的DFTDFT的信號流圖的信號流圖 4點DFTx1(0)=x(0)x1(1)=x(2)x1(2)=x(4)x1(3)=x(6)4點DFTx2(0)=x(1)x2(1)=x(3)x2(2)=x(5)x2(3)=x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1) 0112812823128128000111 222 333XXXWXXXWXXXWXXXW

17、如：X(4)X(7)=?X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)(2) N/2(4(2) N/2(4點點)-N/4(2)-N/4(2點點)FFT)FFT 若將N/2(4點)子序列按奇/偶分解成兩個N/4點(2點)子序列。即對將x1(r)和x2(r)分解成奇、偶兩個N/4點(2點)點的子序列。(a)將4點分解成2點的DFT：(2) N/2(4(2) N/2(4點點)-N/4(2)-N/4(2點點)FFT)FFT 104:26xxx rxx、偶序列、 奇序列 13142 0101214xLxLNLLxLXL偶序列若設：，在此，奇序列x1(0)=x(0)；x1(1)=x(2)x1

18、(2)=x(4)；x1(3)=x(6)(2) N/2(4(2) N/2(4點點)-N/4(2)-N/4(2點點)FFT)FFT 215:37xxx rxx、偶序列同理：、奇序列 25252 0101214xLxLNLLxLXL偶序列同理：，在此，奇序列x2(0)=x(1)；x2(1)=x(3)x2(2)=x(5)；x2(3)=x(7)(b) 求求2點的點的DFT (c) 一個2點的DFT蝶形流圖2點DFT2點DFTx3(0)=x1(0)=x(0)x3(1)=x1(2)=x(4)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W 011344134401

19、13441344000111200 311XXW XXXW XXXW XXXW X其中2點DFT2點DFTX4(0)X4(1)04W14Wx4(0)=x1(1)=x(2)x4(1)=x1(3)=x(6) (d) 另一個2點的DFT蝶形流圖2點DFT2點DFTX5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W01254625460125462546(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXXW X同理：同理：其中：x5(0)=x2(0)=x(1)x5(1)=x2(2)=x(5)x6(0)=x2

20、(1)=x(3)x6(1)=x2(3)=x(7)(3) (3) 將將N/4(2N/4(2點點)DFT)DFT再分解成再分解成2 2個個1 1點的點的DFTDFT(a) 求2個一點的DFT 21200000322220100322221220 102200404(1)04040,1;0,1NnknnknknknkNNX kx n WXxWxWxWxWXxWxWxWxWWWWWnkWW 代入上面流圖可知：這是一蝶形結這里用到對稱性，則，其中 最后剩下兩點DFT，它可分解成兩個一點DFT，但一點DFT就等于輸入信號本身，所以兩點DFT可用一個蝶形結表示。取x(0)、x(4)為例。(b) 2個1點的D

21、FT蝶形流圖 1點DFTx(0)1點DFTx(4)X3(0)X3(1)02W進一步簡化為蝶形流圖：02WX3(0)X3(1)x(0)x(4) 032032004 04104 04XxW xxxXxW xxx其中：(4)一個完整一個完整N=8的按時間抽取的按時間抽取FFT的運算流圖的運算流圖 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W04W02W02W02W02W04W14W14WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2 N點點DIT-FFT運算流程圖運算流程圖(N=8)X1(0)X1(1)X1(2)X1(3

22、)X2(0)X2(1)X2(2)X2(3)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1) DIT-FFTDIT-FFT算法與直接計算算法與直接計算DFTDFT運算量的比較運算量的比較: : 由前面介紹的DIT-FFT運算流圖可見： 每級都由N/2個蝶形單元構成，因此每一級運算都需要N/2次復乘和N次復加（每個結加減各一次）。這樣（N=2M)M級運算共需要： 復乘次數： 復加次數： 可以得出如下結論：按時間抽取法所需的復乘數和復加數都是與成正比。而直接計算DFT時所需的復乘數與復加數則都是與N2成正比.(復乘數N2,復加數N(N-1)N2)NNMNCM2log2

23、22 NNMNCA2log2NN2log DIT-FFTDIT-FFT算法與直接計算算法與直接計算DFTDFT運算量的比較運算量的比較: :復數乘法復數乘法：3.3 DIT-FFT DIT-FFT的運算規律及編程思想的運算規律及編程思想1、原位運算：、原位運算：利用同一單元存儲蝶形計算的輸入、輸出數據。每個蝶形的輸入和輸出均為相同位數。原位運算可節省大量內存，因而硬件成本低。一個完整一個完整N=8的按時間抽取的按時間抽取FFT的運算流圖的運算流圖 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W04W02W02W02W02W04W14W14WX(0)X(

24、1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2 N點點DIT-FFT運算流程圖運算流程圖(N=8)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)1、原位運算：、原位運算： 蝶形運算的特點蝶形運算的特點: :首先每一個蝶形運算都需要兩個輸入數據，計算結果也是兩個數據，與其它結點的數據無關，其它蝶形運算也與這兩結點的數據無關、因此，一個蝶形 運算一旦計算完畢，原輸入數據便失效了。這就意味著輸出數據可以立即使用原輸 人數據結點所占用的內存。原來的數據也就消失了。輸

25、出、輸人數據利用同一內存單 元的這種蝶形計算稱為同位(址)計算。 同址運算的優點同址運算的優點：可以節省存儲單元，從而降低對計算機存儲量的要求或降低硬件實現的成本。3 3. .3 3 DIT-FFT DIT-FFT的的算法特點算法特點及編程思想及編程思想2、蝶形運算兩個節點的距離蝶形運算兩個節點的距離：x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W04W02W02W02W02W04W14W14WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2 N點點DIT-FFT運算流程圖運算流程圖(N=8)X1(0)X1(1)X1(

26、2)X1(3)X2(0)X2(1)X2(2)X2(3)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)3 3. .3 3 DIT-FFT DIT-FFT的的算法特點算法特點及編程思想及編程思想2、蝶形運算兩個節點的距離蝶形運算兩個節點的距離：3 3. .3 3 DIT-FFT DIT-FFT的的算法特點算法特點及編程思想及編程思想3、旋轉因子的變化規律：、旋轉因子的變化規律：x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W04W02W02W02W02W04W14W14WX(0)X(1)X(2)X(3)X(4)X(5)X(6

27、)X(7)m=0m=1m=2X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)2 2(m-1)(m-1)2 2(m-1)(m-1)N=2N=2L L2 2(m-1)(m-1)N=2N=2L L4 4、倒位序倒位序規律規律x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W04W02W02W02W02W04W14W14WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2 N點點DIT-FFT運算流程圖運算流程圖(N=8)

28、X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)4 4、倒位序倒位序規律規律倒序是有規律的。由于 ，所以順序數可用M位二進制數（ ）表示。先按n0的0和1進行偶奇分解，再按n1、n2、依次進行分解。 MN20121. nnnnMM4 4、倒位序倒位序規律規律 000 0 100 4 010 2 110 6 001 1 101 5 011 3 111 7 形成倒序的樹狀圖(N=23) 0 00 00 01 11 10 00 00 00 01 11 11 11 11 1(n(n2 2n

29、n1 1n n0 0) )2 2n n0 0為奇數為奇數n n0 0為偶數為偶數二進制數二進制數 十進制數十進制數3 3. .3 3 頻率抽取法頻率抽取法FFT(DIF-FFT)FFT(DIF-FFT)DITDIT算法算法：把x(n)按奇數偶數分解為越來越短的傅里葉變換；DIFDIF算法算法：把X(k)按奇數偶數分解為越來越短的傅里葉變換；頻率抽選基2FFT算法簡稱為頻率抽選，它的推導過程遵循兩個規則規則：對時間前后分；對頻率偶奇分。3 3. .3 3 頻率抽取法頻率抽取法FFT(DIF-FFT)FFT(DIF-FFT)設序列x(n)長度為 ，將其前后對半分開，得：MN2 10/2 110/2

30、 NknNnNNknknNNnn NX kDFT x nx n Wx n Wx n W式中 /2 1/2 1/2002NNk n NknNNnnNx n Wx nW/21,11kkNNkWk 偶數，奇數 /2 1/202NkNknNNnNx nWx nW再將X(k)分解成偶數組和奇數組k為偶數時： /2 120/2 1/2022 2NrnNnNrnNnNXrx nx nWNx nx nWk為奇數時： /2 1210/2 1/202122NrnNnNnrnNNnNXrx nx nWNx nx nWW令 122,0,1,.,122nNNx nx nx nNnNxnx nx nW得 /2 11/20

31、/2 12/20221NrnNnNrnNnXrx n WXrxn W12,.,1 , 0Nr DIF-FFT蝶形運算流圖nNWx(n)x(n+N/2)x1(n)=x(n)+x(n+N/2)x2(n)=x(n)-x(n+N/2)nNWx(n)x(n)y(n)y(n)數字信數字信號處理號處理？ 例：直接計算直接計算DFT【例例：】 計算有限長序列, N=4的DFT X(k)。【解】 由于x(n)是4點序列，因此X(k)也是4點序列。 ( )2, 4, 3, 4x n 340,03nknX kx n Wk 2j44ejW 所以，若將所以，若將k k的具體值代入，可得的具體值代入，可得 x(n)x(n

32、)y(n)y(n)數字信數字信號處理號處理？ 例：離散傅里葉變換（離散傅里葉變換（DFT）300(0)( )( j)(0)(1)(2)(3)24349nnXx nxxxx 3100123(1)( ) ( j)(0) ( j)(1) ( j)(2) ( j)(3) ( j)2 14 ( j)3 ( 1)4j5nnXx nxxxx 3200246(2)( ) ( j)(0) ( j)(1) ( j)(2) ( j)(3) ( j)2 14 ( 1)3 ( 1)4 ( 1)7nnXx nxxxx x(n)x(n)y(n)y(n)數字信數字信號處理號處理？例：例： 離散傅里葉變換（離散傅里葉變換（DF

33、T）因此，得到x(n)的DFT為 3300369(3)( ) ( j)(0) ( j)(1) ( j)(2) ( j)(3) ( j)2 14 (j)3 ( 1)4 ( j)5nnXx nxxxx ( )9,5,7,5X k DIF-FFT運算流圖(N=8)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)0NW1NW2NW2NW2NW3NW0NW0NW0NW0NW0NW0NW38W28W18W08WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)04W04W14W14W02W02W02W02Wx(0

34、)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1) N點點DIF-FFT運算流程圖運算流程圖(N=8)DITDIT與與DIFDIF的異同的異同 運算量相同：L級，每級N/2個蝶形，每個蝶形一次復乘，兩次復加； 與時間抽選算法一樣，頻率抽選FFT算法也具有同址(原位)計算的優點。但是，與時間抽選不同的是，頻率抽選FFT算法的信號輸入為正序排列，輸出為碼位倒置排列，因此輸出要進行變址計算。 利用轉置定理，可以使DIT和DIF的基本蝶

35、形進行相互轉換。3 3. .4 4 快速傅里葉反變換快速傅里葉反變換IFFTIFFT的計算的計算 10NknNnX kx n W 101NknNkx nXk WNDFTDFT及及IDFTIDFT的定義的定義0,1,1kN0,1,1nN 比較上面兩式，可以看出，只要把DFT公式中 的系數 改為 ，并乘以系數1/N，就可用 FFT算法來計算IDFT，就得到了IFFT的算法。 當把時間抽選FFT算法用于IFFT計算時，由于 原來輸入的時間序列x(n)現在變為頻率序列 X(k)，原來是將x(n)偶奇分的，而現在變成 對X(k)進行偶奇分了，因此這種算法改稱為 頻率抽選IFFT算法。類似地，當把頻率抽選 FFT算法用于計算IFFT時，稱為時間抽選IFFT 算法。 3 3. .4