1、第五章第五章 快速傅里葉變換快速傅里葉變換(FFT)數字信號處理數字信號處理 Digital Signal Processing中國民航大學 航空自動化學院第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：引言Q直接計算直接計算DFT的問題及改進的途徑的問題及改進的途徑Q按按時間抽取時間抽取的基的基2-FFT算法算法 (掌握掌握)Q按按頻率抽取頻率抽取的基的基2-FFT算法算法 (掌握掌握)本章主要內容本章主要內容Q進一步減少運算量的措施進一步減少運算量的措施 (理解理解)第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)v FFT: Fast Fourie

2、r Transformv 1965 年，年，James W. Cooley 和和 John W. Tukey 在在計算數學計算數學（Mathematics of Computation）上發表了）上發表了“ 一種用機器計算復一種用機器計算復序列傅立葉級數的算法（序列傅立葉級數的算法（An algorithm for the machine calculation of complex Fourier series）” 論文。論文。v 自此之后，新的算法不斷涌現。一種是自此之后，新的算法不斷涌現。一種是對對N等于等于 2 的整數次冪的算法的整數次冪的算法，如基如基 2 算法，基算法，基 4 算法

3、。算法。另一種是另一種是N不等于不等于 2 的整數次冪的算法的整數次冪的算法，例如，例如 Winagrad 算法，素因子算法。算法，素因子算法。Dr. James W. CooleyWorked at IBM Watson Research Center in Yorktown Heights, N.Y.After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. FFT：直接計算 DFT 的運算量分析第第5 5章

4、章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)N 點有限長序列 x(n) 的 DFT 變換對的定義為：10( )( )NnkNnX kx n W 0,1kN 2jNNWe 101( )( )NnkNkx nX k WN 0,1nN 其中假設 x(n) 是復序列， 同時 X(k) 一般也是復數。FFT：直接計算 DFT 的運算量分析第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：直接計算 DFT 的運算量分析第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)10102X(k)=( )( )NnNnkNnjnkNx nn eWx FFT：直接計算 DFT

5、 的運算量分析計算量分析計算量分析N次復數次復數相乘相乘N-1次復次復數相加數相加N2次復數相乘次復數相乘N（N-1）次復數相加）次復數相加第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)v 如如 N=512、1024 和和 8192 時，時，DFT 的乘法運算的乘法運算 N2 = 5122 = 218 = 262144（26萬次）萬次） N2 = 10242 = 220 = 1048576（105萬次）萬次） N2 = 81922 = 226 = 67108864（6千千7百萬次）百萬次）N2次復數相乘次復數相乘N（N-1）次復數相加）次復數相加一次復數乘法需四次實數乘法和二

6、次實數加法一次復數乘法需四次實數乘法和二次實數加法一次復數加法需兩次實數加法一次復數加法需兩次實數加法1010ImRe)(Im)(Re)()(NnnkNnkNnkNNnWjWnxjnxWnxkXFFT：直接計算 DFT 的運算量分析采用通用計算機，速度為平均每次復乘為采用通用計算機，速度為平均每次復乘為5s，每次復加為，每次復加為1 s，所用，所用時間時間:T=5*10-6 *10242+ 10-6 *1024*1023=6.290s第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)1.如果一臺通用計算機的速度為平均每次復乘 ，每次復加 ，用它來計算512點的 ，問直接計算需要多

7、少時間，用 運算需要多少時間。 5 s0.5 s DFT x nFFT解：(1)直接利用 計算： 復乘次數為 ，復加次數為 。 DFT2N1N N 復乘所需時間 626215 105 105121.31072TNs復加所需時間 6260.5 1010.5 10512512 10.130816TNNs所以直接利用DFT 計算所需時間： 121.441536TTTsFFT：直接計算 DFT 的運算量分析第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)Q對于大對于大 N，在實際中是不能接受的，無法，在實際中是不能接受的，無法“實時實時”應應用用 DFT。 一般地，在計算機中，一次加法

8、比一次乘法所需時一般地，在計算機中，一次加法比一次乘法所需時間要短間要短; 在在DSP中，由于乘法用特殊的硬件電路專門完成，中，由于乘法用特殊的硬件電路專門完成，因此乘法和加法所需機器周期相同。因此乘法和加法所需機器周期相同。QCooley 與與 Turkey 提出的提出的 FFT 算法，大大減少了計算算法，大大減少了計算次數。如次數。如 N =512 時，時，FFT 的乘法次數約為的乘法次數約為 2000 次，次，提高了約提高了約 128 倍，而且倍，而且簡化隨簡化隨 N 的增加而巨增的增加而巨增，因而，因而，用數值方法計算頻譜得到實際應用。用數值方法計算頻譜得到實際應用。FFT：直接計算

9、DFT 的運算量分析第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：旋轉因子的特點把長序列分解成短序列計算，然后再組合出結果。nkNW主要原理是利用系數主要原理是利用系數 的以下特性對的以下特性對DFT進行分解：進行分解： nkNW（1）對稱性）對稱性 ()nkNW()k N nNW（2）周期性）周期性 ()()n N kn k NnkNNNWWW（3）可約性）可約性 mnknkmNNWW/nknk mNN mWW另外，另外，12/NNWkNNkNWW)2/(第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)vDFT高效運算的可能性分析：高效運算的可能性分

10、析：假定假定x(n)為為4點長的信號，對其做點長的信號，對其做4點點DFT：04040404)3()2() 1 ()0()0(WxWxWxWxX34241404)3()2() 1 ()0() 1 (WxWxWxWxX64442404)3()2() 1 ()0()2(WxWxWxWxX94643404)3()2() 1 ()0()3(WxWxWxWxX利用利用旋轉因子旋轉因子的的4個特點：個特點：)3() 1 ()2()0()0(xxxxX14)3() 1 ()2()0() 1 (WxxxxX-14)3() 1 ()2()0()3(WxxxxX-)3() 1 ()2()0()2(xxxxX計算量

11、？計算量？計算量？計算量？FFT：旋轉因子的特點顯然顯然N值越小越有利！值越小越有利！第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)vFFT 算法分類算法分類: 時間時間抽選法抽選法 DIT: Decimation-In-Time 頻率頻率抽選法抽選法 DIF: Decimation-In-Frequencyv基本思路：基本思路：Q雖然存在不同的雖然存在不同的 FFT 方法，但其核心思想大致相同，方法，但其核心思想大致相同，即通過即通過迭代迭代，反復利用，反復利用低點數低點數的的 DFT 完成高點數的完成高點數的 DFT 計算，以此達到降低運算量的目的。計算，以此達到降低運算

12、量的目的。Q迭代：迭代：利用利用 WNkn 的周期性、特殊點和對稱性，合并的周期性、特殊點和對稱性，合并 DFT 計算中很多重復的計算，達到降低運算量的目的。計算中很多重復的計算，達到降低運算量的目的。Q低點數：低點數：將傅氏變換將傅氏變換 DFT 分解成相繼小的分解成相繼小的DFT計算，計算，即即 N 變小，而計算量與變小，而計算量與 N2 成正比。成正比。FFT：基本思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時間抽選法-算法原理v算法原理算法原理 設序列點數設序列點數 N = 2M，M 為整數。若不滿足，則補零。為整數。若不滿足，則補零。 將序列將序列

13、 x(n) 按按 n 的奇偶分成兩組：的奇偶分成兩組：N 為為 2 的整數冪的的整數冪的 FFT 算法稱基算法稱基-2 FFT算法。算法。即一組由偶數序號組成，另一組由奇數序號組成。即一組由偶數序號組成，另一組由奇數序號組成。12( )(2 )0,1,12( )(21)x rxrNrx rxr 偶偶序序列列奇奇序序列列注意其長度為注意其長度為 N/2 第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT) 111000NNNnknknkNNNnnnX kx n Wx n Wx n W n為為偶偶數數n為為奇奇數數2 1212 1200221/NNrkrkNNrrxr WxrW 2 1

14、2 1221200/NNrkrkkNNNrrxrWWxrW 2 12 1120202/NNNrkkrkrNNrxr WWxr W 12kNXkW Xk0 112, ,.k= 0,1,.N-1Nr 注意：注意：這里的這里的k的的取值范圍為取值范圍為0，1，N-1FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)偶數取樣點偶數取樣點DFT為：為： NN-1-122krkr1N 21N 2r=0r=0X (k) =x(2r)W=x (r)W112222002122X ( )()(r)NNkrkrNNrrkxrWxW0 12 1, ,./k= 0,1,.N

15、-1rN奇數取樣點奇數取樣點DFT為：為： k 的整個范圍為的整個范圍為 0(N-1)，而，而X1(k)、X2(k) 是由是由 N/2 個樣點形成的個樣點形成的 DFT，x(2r) 和和 x(2r1）的長度為）的長度為 N/2； 由這兩個偶數和奇數由這兩個偶數和奇數 N/2 個時域樣值可以計算出前個時域樣值可以計算出前 N/2 個個 DFT 系數，也可系數，也可以計算出后以計算出后 N/2 個個 DFT 系數。系數。 問題：這前后問題：這前后 N/2 個個 DFT 有無關系？有無關系？k 在在 N/2 (N-1) 時，時， X1(k)、X2(k)、WN 情況如何？情況如何？FFT：基2時間抽選

16、法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)1122 , NNkN當當時時0122 , ,NNkll令令觀察觀察21( )()(kNXkXWX kk 分分為為三三部部分分第第一一第第三三第第二二則則2221122()22110012102( )()(2 )(2 )2(2 )( )NNNNNNNrlrrlrrNrlNrNX kXlxr Wxr WWxr WX l 2222221NjrNNrjrNWee N-12kr1N 2r=0X (k) =x(2r)WFFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT) 因此：整個因此

17、：整個 X(k) 的計算，可以分解為的計算，可以分解為前、后半部分前、后半部分的運的運算。而算。而只要求出前一半只要求出前一半，就可以由上式求出整個序列。，就可以由上式求出整個序列。同理同理2222( )()( )NXkXlXl而而2()222(1) NNNljkljNNNNNWWWWee 因此因此1122( )( )( )()( )( )2 kNkNNX kX kWX XkkX kWXk0,1,12Nk FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT) 上式表示為信號流程圖：上式表示為信號流程圖： 此信號流程圖也稱為此信號流程圖也稱為蝶形蝶形流

18、程圖流程圖1122( )( )( )()( )( )2 kNkNNX kX kWX XkkX kWXk0,1,12Nk 偶數點的偶數點的 DFT奇數點的奇數點的 DFT( )X k ()2NX k Morpho Butterfly大閃蝶大閃蝶( 南美洲南美洲)FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)122()( )( )kNNX kXkWXkFFT：基2時間抽選法-算法原理偶數序列偶數序列奇數序列奇數序列12( )( )( )kNX kXkWXk以以N=8為為例，例，分解分解為為2個個4點點的的DFT，然后做然后做8/2=4次次蝶形運算蝶

19、形運算即可求出即可求出所有所有8點點X(k)的值。的值。第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)復數乘法次數：復數乘法次數： N2復數加法次數：復數加法次數： N(N1)復數乘法次數：復數乘法次數： 2*(N/2)2+N/2=N2/2+N/2復數加法次數：復數加法次數： 2*(N/2)(N/21)+2*N/2=N2/2QN點點 FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)二次分解：二次分解：Q 將將x1(r)按按r取奇、偶可分解成取奇、偶可分解成2個長度為個長度為N/4的子序列的子序列 x3(l)= x1(2h)、 x

20、4(l) = x1(2h+1)，根據上面推導可得：根據上面推導可得：X1 (k)= X3(k)+ WN/2k X4(k)， k=0,1,N/2-1Q 將將x2(r)按按r取奇、偶可分解成取奇、偶可分解成2個長個長N/4的子序列的子序列 x5(l)= x2(2h) ， h=0,1,，N/4 x6(l) = x2(2h+1) ； 同理得同理得h=0,1,，N/4-1；X1 (k+N/2)=X3(k) WN/2k X4(k)， k=0,1,N/4-1；X1 (k)=X3(k)+WN/2k X4(k)， k=0,1,N/4-1；X2(k) = X5(k)+ WN/2k X6(k)， k=0,1,N/4

21、-1 ；X2(k+N/2) = X5(k) WN/2k X6(k), k=0,1,N/4-1；FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)由于由于 N=2M，這樣逐級分解，直到，這樣逐級分解，直到 2 點點 DFT當當 N = 8時，可分解三次時，可分解三次00033223010332230010410104( )( )( )( )( )( )( )( )( )( )NNXxWW xxW xXxWW xxW x / 4 1133/ 43/ 400(

22、 )( )( )NlklkNNllXkxl Wxl W 0,1k0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x 4 114444400/( )( )( )NlklkNNllXkxl Wxl W 0,1kFFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時間抽選

23、法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)L=1L=2L=3FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)由按時間抽取法由按時間抽取法FFT的信號流圖可知，當的信號流圖可知，當N=2L時，共有時，共有 級級蝶形運算；每級都由蝶形運算；每級都由 個蝶形運算組成，而每個蝶形有個蝶形運算組成，而每個蝶形有 次復乘、次復乘、 次復加，因此每級運算都需次復加，因此每級運算都需 次復乘和次復乘和 次復加。次復加。 LN/2 N/2 12N按時間抽取基2-FFT算法與直接計算DFT運算量的比較 第第5 5章章 快速傅里葉變換

24、快速傅里葉變換(FFT)(FFT)1.原位計算原位計算序列長為序列長為N=2M點的點的FFT，有，有M級蝶形級蝶形，每級有，每級有N/2個蝶形運算個蝶形運算。 同一級中，每個蝶形的兩個輸入數據只對本蝶形有用同一級中，每個蝶形的兩個輸入數據只對本蝶形有用，每，每個蝶形的輸入、輸出數據節點在用一條水平線上。這樣，當計算個蝶形的輸入、輸出數據節點在用一條水平線上。這樣，當計算完一個蝶形后，所得的輸出數據可立即存入原輸入數據所占用的完一個蝶形后，所得的輸出數據可立即存入原輸入數據所占用的存儲單元。存儲單元。經過經過M級運算后，原來存放輸入序列數據的級運算后，原來存放輸入序列數據的N個存儲個存儲單元中可

25、依次存放單元中可依次存放X(k)的的N個值。個值。v原位計算原位計算：利用同一存儲單元存儲蝶形計算輸入、輸出數據的：利用同一存儲單元存儲蝶形計算輸入、輸出數據的方法。方法。v優點優點：節約存儲空間、降低設備成本。：節約存儲空間、降低設備成本。FFT：DITFFT的運算規律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)2.旋轉因子的變化規律旋轉因子的變化規律N點點DITFFT運算流圖中，每個蝶形都要乘以運算流圖中，每個蝶形都要乘以旋轉因子旋轉因子WpN，p稱稱為旋轉因子的指數。為旋轉因子的指數。N8 23 時各級的旋轉因子時各級的旋轉因子v 第一級：第一級：L=1，

26、有有1個旋轉因子：個旋轉因子：WNp =WN/4J =W2LJ J=0v 第二級：第二級：L=2，有，有2個旋轉因子：個旋轉因子：WNp =WN/2J =W2LJ J=0,1v 第三級：第三級：L=3，有，有4個旋轉因子：個旋轉因子：WNp =WNJ =W2LJ J=0,1,2,3v 對于對于N2M 的的一般情況，一般情況，第第L級級共有共有2L-1個不同的旋轉因子：個不同的旋轉因子： WNp =W2LJ J=0,1,2, ,2L-11 2L =2L M 2M = N 2L M 故：故： 按照上面兩式可以確定第按照上面兩式可以確定第L級運算的旋轉因子。級運算的旋轉因子。JJ 2M-LWNp =

27、W2LJ =WN 2L-M = WNp=J2M-L， J=0,1,2, ,2L-11FFT：DITFFT的運算規律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)3、同一級中，同一旋轉因子對應蝶形數目、同一級中，同一旋轉因子對應蝶形數目 第第L級級FFT運算中，運算中，同一旋轉因子同一旋轉因子用在用在2M-L個蝶形中；個蝶形中；4、同一級中，蝶形運算使用相同旋轉因子之間相隔的、同一級中，蝶形運算使用相同旋轉因子之間相隔的“距離距離” 第第L級中，蝶距：級中，蝶距：D=2L。5、同一蝶形運算兩輸入數據的距離、同一蝶形運算兩輸入數據的距離 在輸入倒序，輸出原序的在輸入倒序

28、，輸出原序的FFT變換中，第變換中，第L級的每一個蝶形級的每一個蝶形的的2個輸入數據相距：個輸入數據相距：B=2L-1。 6、碼位顛倒、碼位顛倒 輸入序列輸入序列x(n)經過經過M級時域奇、偶抽選后，輸出序列級時域奇、偶抽選后，輸出序列X(k)的順的順序和輸入序列的順序關系為序和輸入序列的順序關系為倒位關系倒位關系。FFT：DITFFT的運算規律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)7、蝶形運算的規律、蝶形運算的規律 序列經過時域抽選后，存入數組中，如果蝶形運序列經過時域抽選后，存入數組中，如果蝶形運算的兩個輸入數據相距算的兩個輸入數據相距B個點，應用原位計

29、算，蝶形個點，應用原位計算，蝶形運算可表示成如下形式：運算可表示成如下形式： XL-1(J)X L-1 (J+B)XL (J)= XL-1(J)+ WNp X L-1 (J+B)XL (J) = XL-1(J) WNp X L-1 (J+B)p=J2M-L， J=0,1,2, ,2L-11FFT：DITFFT的運算規律及編程思想的運算規律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)8.輸入位序重排輸入位序重排 N 點點 DFT 分解為兩個分解為兩個 N/2 點點 DFT輸入序列按奇偶分組輸入序列按奇偶分組再分解再分解再奇偶重排再奇偶重排直到直到 2 點點DFT。

30、即即 FFT 輸出自輸出自然序列然序列 輸入序列輸入序列 x(n) 位序重排位序重排。2 1 0210()()(000)(0)(001)(1)(010)(2)(011)(3)(100)(4)(101)(5)(110)(6)(111)(7)n n nxxxxxxxxxxxxxxxxxn n nx 十十進進制制01010101(000)(0)(100)(4)(010)(2)(110)(6)(001)(1)(101)(5)(011)(3)(111)(7)xxxxxxxxxxxxxxxx010011n0n1n2FFT：DITFFT的運算規律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT

31、)(FFT)思考題：思考題：已知已知N=16點，在點，在DIT-FFT運算中，序數為運算中，序數為2的二進制的二進制經數倒序后為多少經數倒序后為多少?順序數順序數增加增加1，是在順序數的是在順序數的二進制數的二進制數的最最低位加低位加1，向，向左左進位進位到序數是在到序數是在M位 二 進 制 數位 二 進 制 數的的最高位加最高位加1，向右向右進位進位(0010-0100)(0010-0100)順序和倒序二進制數對照表順序和倒序二進制數對照表FFT：DITFFT的運算規律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：DITFFT的運算規律及編程思想N個存儲器

32、個存儲器FFT的實現的實現輸入輸入x(n)-N個點；個點；位倒序后存儲在位倒序后存儲在N個存儲器中；個存儲器中；逐級蝶形運算，輸逐級蝶形運算，輸出結果仍存回存儲出結果仍存回存儲器中；器中；最后最后N個存儲器中個存儲器中存放的是存放的是FFT的結的結果果X(k)。x(n)的位倒序的位倒序X(k)的自然順序的自然順序rNW輸入序列輸入序列x(n) : N個存儲單元個存儲單元系數系數 ： N / 2個存儲單元個存儲單元存儲單元存儲單元第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)v 算法原理：算法原理：根據時間根據時間-頻率的對偶性頻率的對偶性Q時間抽選法：時間抽選法：是把輸入是把

33、輸入 x(n) 按奇偶分解成兩個子序列，即按奇偶分解成兩個子序列，即 N 點點x(n) 序列序列 N/2 點子序列，而輸出點子序列，而輸出 X(k) 是按自然順序是按自然順序排列的。排列的。Q頻率抽選法：頻率抽選法：是把輸入是把輸入 x(n) 按照前后對半分開，而不是奇按照前后對半分開，而不是奇偶數分開，而輸出偶數分開，而輸出 X(k) 逐項分解成偶數點子序列和奇數點逐項分解成偶數點子序列和奇數點子序列。子序列。v DFT 變換表達式為：變換表達式為：10( )( )NnkNnX kx n W (1)2NnN如果將輸入如果將輸入 x(n) 按前后等分，即將求和分成兩部分，范圍分別為：按前后等分

34、，即將求和分成兩部分，范圍分別為：0 (1)2Nn FFT：基2頻率抽選法 (DIF-FFT)第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)12 10201/( )( )( )( )NNnknkNn NnkNNNnnX kx n Wx n Wx n W0022 12 12/( )NNnknkNnNNnNx n WxnW22 102/( )NnkNNNknNx nxnWW 2 1021/()()NknkNnNx nxnW 0,1,.,1kN/21NNW FFT：基2頻率抽選法 (DIF-FFT)第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT) 按按 k 的奇偶將

35、的奇偶將X(k)分成兩部分：分成兩部分：221krkr0,1,.,12Nr 2 12022/()( )NnrNnNXrx nx nW2 1210212/()()( )NnrNnNXrx nx nW2 1202/( )NnrNnNx nx nW 2 1202/( )NnrNnnNWNx nx nWFFT：基2頻率抽選法 (DIF-FFT)第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)令令: :1222( )( )( )( )nNNx nx nx nNxnx nx nkkW 為為偶偶數數： 數數 為為奇奇：0,1,.,12Nn 則則 X(2r) 和和 X(2r+1) 分別是分別是 x1(n) 和和 x2(n) 的的 N/2 點點 DFT，記為記為 X1(k) 和和 X2(k)。1211202()( )NnrNnXrxXWkkn 為為偶偶數數：12222021()( )NnrNnXrx nkXWk為為奇奇數數：FFT：基2頻率抽選法 (DIF-FFT)第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(