第3章快速付里葉變換FFT

1、第第3 3章章 快速付里葉變換快速付里葉變換(FFT)(FFT) Fast FourierFast Fourier TransformingTransformingu離散傅里葉變換在實(shí)際應(yīng)用中是非常重要的，利用它可以計(jì)算信號(hào)的頻譜、功率譜和線性卷積等.u但是，如果使用定義式來(lái)直接計(jì)算DFT，當(dāng)N很大時(shí)，DFT的計(jì)算量太大，即使使用高速計(jì)算機(jī)，所花的時(shí)間也太多，很難對(duì)問(wèn)題進(jìn)行實(shí)時(shí)處理。所以在相當(dāng)長(zhǎng)的時(shí)間里，并沒(méi)有得到真正的運(yùn)用。因此，如何提高計(jì)算DFT的速度，便成了重要的研究課題?？焖俑独锶~變換快速付里葉變換(FFT)(FFT) 1965年庫(kù)利（J.W.Cooley）和圖基（J.W.Tukey）

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

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

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

5、較短的列的離散傅里葉變換逐次分解為較短的離散傅里葉變換來(lái)計(jì)算這一基本原理的。離散傅里葉變換來(lái)計(jì)算這一基本原理的。這一原理產(chǎn)生了許多不同的算法，但它這一原理產(chǎn)生了許多不同的算法，但它們?cè)谟?jì)算速度上均取得了大致相當(dāng)?shù)母膫冊(cè)谟?jì)算速度上均取得了大致相當(dāng)?shù)母纳?。善?.1 3.1 直接計(jì)算直接計(jì)算DFTDFT的特點(diǎn)及減少運(yùn)的特點(diǎn)及減少運(yùn) 算量的基本途徑算量的基本途徑 3.1 直接計(jì)算直接計(jì)算DFTDFT的特點(diǎn)及減少運(yùn)的特點(diǎn)及減少運(yùn) 算量的基本途徑算量的基本途徑 nkNnkNWW*)(（2 2） W WN Nnknk的周期性的周期性 )()(NknNkNnNnkNWWW（3 3） W WN Nnknk的可

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

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

8、N/2點(diǎn)的序列為： 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 按時(shí)間抽?。ò磿r(shí)間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原理（庫(kù)利-圖基算法）偶數(shù)序列偶數(shù)序列 the range: 02rN-2 (N is even) 0r(N/2)-1奇數(shù)序列奇數(shù)序列 the range: 12r+1N-1 (N is even) 02rN-2 0r(N/2)-13 3.2.2 按時(shí)間抽?。ò磿r(shí)間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原

9、理（庫(kù)利-圖基算法）3 3.2.2 按時(shí)間抽?。ò磿r(shí)間抽?。―ITDIT）的基）的基-2 FFT-2 FFT 算法算法原理原理（庫(kù)利-圖基算法） 則則x(n)的的DFT：rkNNrkNrkNNrkrNNrrkNNrNnnnkNNnNnnnkNnkNWrxWWrxWrxWrxWnxWnxWnxnxDFTkX)()( )() 12()2()()()()()(2120221201) 12(1202120101010為奇數(shù)為偶數(shù)故故: :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：表示上述算法可用蝶形結(jié)（表示上述算法可用蝶形結(jié)（ butterf

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

13、kXkXkN運(yùn)算量？運(yùn)算量？x(n)x(n)y(n)y(n)數(shù)字信數(shù)字信號(hào)處理號(hào)處理？ 例：直接計(jì)算直接計(jì)算DFT【例例：】 計(jì)算有限長(zhǎng)序列, N=4的DFT X(k)?！窘狻?由于x(n)是4點(diǎn)序列，因此X(k)也是4點(diǎn)序列。 ( )2, 4, 3, 4x n 340,03nknX kx n Wk 2j44ejW 所以，若將所以，若將k k的具體值代入，可得的具體值代入，可得 x(n)x(n)y(n)y(n)數(shù)字信數(shù)字信號(hào)處理號(hào)處理？ 例：離散傅里葉變換（離散傅里葉變換（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)數(shù)字信數(shù)字信號(hào)處理號(hào)處理？例：例： 離散傅里葉變換（離散傅里葉變換（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點(diǎn)的點(diǎn)的DFTDFT： 1212/2kNkNX kX kW XkX kNX kW Xk12/, 0Nk 例：求例：求 N N=2=23 3=8=8點(diǎn)點(diǎn)FFTFFT變換變換rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201) 12()()()2()()( 例：求例：求 N N=2=23 3=8=8點(diǎn)點(diǎn)FFTFFT變換變換 將N=8點(diǎn)DFT分解成2個(gè)4點(diǎn)DFT： 時(shí)域上時(shí)域上：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點(diǎn)分解成點(diǎn)分解成2 2個(gè)個(gè)4 4點(diǎn)的點(diǎn)的DFTDFT的信號(hào)流圖的信號(hào)流圖 4點(diǎn)DFTx1(0)=x(0)x1(1)=x(2)x1(2)=x(4)x1(3)=x(6)4點(diǎn)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點(diǎn)點(diǎn))-N/4(2)-N/4(2點(diǎn)點(diǎn))FFT)FFT 若將N/2(4點(diǎn))子序列按奇/偶分解成兩個(gè)N/4點(diǎn)(2點(diǎn))子序列。即對(duì)將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)(2點(diǎn))點(diǎn)的子序列。(a)將4點(diǎn)分解成2點(diǎn)的DFT：(2) N/2(4(2) N/2(4點(diǎn)點(diǎn))-N/4(2)-N/4(2點(diǎn)點(diǎn))FFT)FFT 104:26xxx rxx、偶序列、 奇序列 13142 0101214xLxLNLLxLXL偶序列若設(shè)：，在此，奇序列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點(diǎn)點(diǎn))-N/4(2)-N/4(2點(diǎn)點(diǎn))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點(diǎn)的點(diǎn)的DFT (c) 一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)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點(diǎn)DFT2點(diǎn)DFTX4(0)X4(1)04W14Wx4(0)=x1(1)=x(2)x4(1)=x1(3)=x(6) (d) 另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)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點(diǎn)點(diǎn))DFT)DFT再分解成再分解成2 2個(gè)個(gè)1 1點(diǎn)的點(diǎn)的DFTDFT(a) 求2個(gè)一點(diǎn)的DFT 21200000322220100322221220 102200404(1)04040,1;0,1NnknnknknknkNNX kx n WXxWxWxWxWXxWxWxWxWWWWWnkWW 代入上面流圖可知：這是一蝶形結(jié)這里用到對(duì)稱性，則，其中 最后剩下兩點(diǎn)DFT，它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。(b) 2個(gè)1點(diǎn)的D

21、FT蝶形流圖 1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)02W進(jìn)一步簡(jiǎn)化為蝶形流圖：02WX3(0)X3(1)x(0)x(4) 032032004 04104 04XxW xxxXxW xxx其中：(4)一個(gè)完整一個(gè)完整N=8的按時(shí)間抽取的按時(shí)間抽取FFT的運(yùn)算流圖的運(yùn)算流圖 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點(diǎn)點(diǎn)DIT-FFT運(yùn)算流程圖運(yùn)算流程圖(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算法與直接計(jì)算算法與直接計(jì)算DFTDFT運(yùn)算量的比較運(yùn)算量的比較: : 由前面介紹的DIT-FFT運(yùn)算流圖可見(jiàn)： 每級(jí)都由N/2個(gè)蝶形單元構(gòu)成，因此每一級(jí)運(yùn)算都需要N/2次復(fù)乘和N次復(fù)加（每個(gè)結(jié)加減各一次）。這樣（N=2M)M級(jí)運(yùn)算共需要： 復(fù)乘次數(shù)： 復(fù)加次數(shù)： 可以得出如下結(jié)論：按時(shí)間抽取法所需的復(fù)乘數(shù)和復(fù)加數(shù)都是與成正比。而直接計(jì)算DFT時(shí)所需的復(fù)乘數(shù)與復(fù)加數(shù)則都是與N2成正比.(復(fù)乘數(shù)N2,復(fù)加數(shù)N(N-1)N2)NNMNCM2log2

23、22 NNMNCA2log2NN2log DIT-FFTDIT-FFT算法與直接計(jì)算算法與直接計(jì)算DFTDFT運(yùn)算量的比較運(yùn)算量的比較: :復(fù)數(shù)乘法復(fù)數(shù)乘法：3.3 DIT-FFT DIT-FFT的運(yùn)算規(guī)律及編程思想的運(yùn)算規(guī)律及編程思想1、原位運(yùn)算：、原位運(yùn)算：利用同一單元存儲(chǔ)蝶形計(jì)算的輸入、輸出數(shù)據(jù)。每個(gè)蝶形的輸入和輸出均為相同位數(shù)。原位運(yùn)算可節(jié)省大量?jī)?nèi)存，因而硬件成本低。一個(gè)完整一個(gè)完整N=8的按時(shí)間抽取的按時(shí)間抽取FFT的運(yùn)算流圖的運(yùn)算流圖 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點(diǎn)點(diǎn)DIT-FFT運(yùn)算流程圖運(yùn)算流程圖(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、原位運(yùn)算：、原位運(yùn)算： 蝶形運(yùn)算的特點(diǎn)蝶形運(yùn)算的特點(diǎn): :首先每一個(gè)蝶形運(yùn)算都需要兩個(gè)輸入數(shù)據(jù)，計(jì)算結(jié)果也是兩個(gè)數(shù)據(jù)，與其它結(jié)點(diǎn)的數(shù)據(jù)無(wú)關(guān)，其它蝶形運(yùn)算也與這兩結(jié)點(diǎn)的數(shù)據(jù)無(wú)關(guān)、因此，一個(gè)蝶形 運(yùn)算一旦計(jì)算完畢，原輸入數(shù)據(jù)便失效了。這就意味著輸出數(shù)據(jù)可以立即使用原輸 人數(shù)據(jù)結(jié)點(diǎn)所占用的內(nèi)存。原來(lái)的數(shù)據(jù)也就消失了。輸

25、出、輸人數(shù)據(jù)利用同一內(nèi)存單 元的這種蝶形計(jì)算稱為同位(址)計(jì)算。 同址運(yùn)算的優(yōu)點(diǎn)同址運(yùn)算的優(yōu)點(diǎn)：可以節(jié)省存儲(chǔ)單元，從而降低對(duì)計(jì)算機(jī)存儲(chǔ)量的要求或降低硬件實(shí)現(xiàn)的成本。3 3. .3 3 DIT-FFT DIT-FFT的的算法特點(diǎn)算法特點(diǎn)及編程思想及編程思想2、蝶形運(yùn)算兩個(gè)節(jié)點(diǎn)的距離蝶形運(yùn)算兩個(gè)節(jié)點(diǎn)的距離：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點(diǎn)點(diǎn)DIT-FFT運(yùn)算流程圖運(yùn)算流程圖(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的的算法特點(diǎn)算法特點(diǎn)及編程思想及編程思想2、蝶形運(yùn)算兩個(gè)節(jié)點(diǎn)的距離蝶形運(yùn)算兩個(gè)節(jié)點(diǎn)的距離：3 3. .3 3 DIT-FFT DIT-FFT的的算法特點(diǎn)算法特點(diǎn)及編程思想及編程思想3、旋轉(zhuǎn)因子的變化規(guī)律：、旋轉(zhuǎn)因子的變化規(guī)律：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、倒位序倒位序規(guī)律規(guī)律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點(diǎn)點(diǎn)DIT-FFT運(yùn)算流程圖運(yùn)算流程圖(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、倒位序倒位序規(guī)律規(guī)律倒序是有規(guī)律的。由于 ，所以順序數(shù)可用M位二進(jìn)制數(shù)（ ）表示。先按n0的0和1進(jìn)行偶奇分解，再按n1、n2、依次進(jìn)行分解。 MN20121. nnnnMM4 4、倒位序倒位序規(guī)律規(guī)律 000 0 100 4 010 2 110 6 001 1 101 5 011 3 111 7 形成倒序的樹(shù)狀圖(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為奇數(shù)為奇數(shù)n n0 0為偶數(shù)為偶數(shù)二進(jìn)制數(shù)二進(jìn)制數(shù) 十進(jìn)制數(shù)十進(jìn)制數(shù)3 3. .3 3 頻率抽取法頻率抽取法FFT(DIF-FFT)FFT(DIF-FFT)DITDIT算法算法：把x(n)按奇數(shù)偶數(shù)分解為越來(lái)越短的傅里葉變換；DIFDIF算法算法：把X(k)按奇數(shù)偶數(shù)分解為越來(lái)越短的傅里葉變換；頻率抽選基2FFT算法簡(jiǎn)稱為頻率抽選，它的推導(dǎo)過(guò)程遵循兩個(gè)規(guī)則規(guī)則：對(duì)時(shí)間前后分；對(duì)頻率偶奇分。3 3. .3 3 頻率抽取法頻率抽取法FFT(DIF-FFT)FFT(DIF-FFT)設(shè)序列x(n)長(zhǎng)度為 ，將其前后對(duì)半分開(kāi)，得：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 偶數(shù)，奇數(shù) /2 1/202NkNknNNnNx nWx nW再將X(k)分解成偶數(shù)組和奇數(shù)組k為偶數(shù)時(shí)： /2 120/2 1/2022 2NrnNnNrnNnNXrx nx nWNx nx nWk為奇數(shù)時(shí)： /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蝶形運(yùn)算流圖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)數(shù)字信數(shù)字信號(hào)處理號(hào)處理？ 例：直接計(jì)算直接計(jì)算DFT【例例：】 計(jì)算有限長(zhǎng)序列, N=4的DFT X(k)?！窘狻?由于x(n)是4點(diǎn)序列，因此X(k)也是4點(diǎn)序列。 ( )2, 4, 3, 4x n 340,03nknX kx n Wk 2j44ejW 所以，若將所以，若將k k的具體值代入，可得的具體值代入，可得 x(n)x(n

32、)y(n)y(n)數(shù)字信數(shù)字信號(hào)處理號(hào)處理？ 例：離散傅里葉變換（離散傅里葉變換（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)數(shù)字信數(shù)字信號(hào)處理號(hào)處理？例：例： 離散傅里葉變換（離散傅里葉變換（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運(yùn)算流圖(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點(diǎn)點(diǎn)DIF-FFT運(yùn)算流程圖運(yùn)算流程圖(N=8)DITDIT與與DIFDIF的異同的異同 運(yùn)算量相同：L級(jí)，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形一次復(fù)乘，兩次復(fù)加； 與時(shí)間抽選算法一樣，頻率抽選FFT算法也具有同址(原位)計(jì)算的優(yōu)點(diǎn)。但是，與時(shí)間抽選不同的是，頻率抽選FFT算法的信號(hào)輸入為正序排列，輸出為碼位倒置排列，因此輸出要進(jìn)行變址計(jì)算。 利用轉(zhuǎn)置定理，可以使DIT和DIF的基本蝶

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