DSP-5-2014(新)

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

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

3、。算法。另一種是另一種是N不等于不等于 2 的整數(shù)次冪的算法的整數(shù)次冪的算法，例如，例如 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. 2022-2-283FFT：直接計算 DFT 的運

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

5、：直接計算 DFT 的運算量分析計算量分析計算量分析N次復數(shù)次復數(shù)相乘相乘N-1次復次復數(shù)相加數(shù)相加N2次復數(shù)相乘次復數(shù)相乘N（N-1）次復數(shù)相加）次復數(shù)相加第第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次復數(shù)相乘次復數(shù)相乘N（N-1）次復數(shù)相加）次復數(shù)相加一次復數(shù)乘法

6、需四次實數(shù)乘法和二次實數(shù)加法一次復數(shù)乘法需四次實數(shù)乘法和二次實數(shù)加法一次復數(shù)加法需兩次實數(shù)加法一次復數(shù)加法需兩次實數(shù)加法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)直接利用 計算： 復乘次數(shù)為 ，復加次數(shù)為 。 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 算法，大大減少了計算算法，大大減少了計算次數(shù)。如次數(shù)。如 N =512 時，時，F(xiàn)FT 的乘法次數(shù)約為的乘法次數(shù)約為 2000 次，次，提高了約提高了約 128 倍，而且倍，而且簡化隨簡化隨 N 的增加而巨增的增加而巨增，因而，因而，用數(shù)值方法計算頻譜得到實際應用。用數(shù)值方法計算頻譜得到實際應用

9、。FFT：直接計算 DFT 的運算量分析第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：旋轉(zhuǎn)因子的特點把長序列分解成短序列計算，然后再組合出結(jié)果。nkNW主要原理是利用系數(shù)主要原理是利用系數(shù) 的以下特性對的以下特性對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利用利用旋轉(zhuǎn)因子旋轉(zhuǎn)因子的的4個特點：個特點：)3() 1 ()2()0()0(xxxxX14)3() 1 ()2()0() 1 (WxxxxX-14)3() 1 ()2()0()3(WxxxxX-)3() 1 ()2()0()

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

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

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

14、 WxrW 2 12 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)偶數(shù)取樣點偶數(shù)取樣點DFT為：為： NN-1-122krkr1N 21N 2r=0r=0X (k) =x(2r)W=x (r)W112222002122X ( )()(r)NNkrkrNNrrkxrWxW0 12 1, ,./

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

16、FT：基2時間抽選法-算法原理第第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 偶數(shù)點的偶數(shù)點的 DFT奇數(shù)點的奇數(shù)點的 DFT( )X k ()2NX kMorpho Butterfly大閃蝶大閃蝶( 南美洲南美洲)FFT：基2時間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)122()( )( )kNNX kXkWXkFFT：基2時間抽選法-算法原理偶數(shù)序列偶數(shù)序列奇數(shù)序列奇數(shù)序列12( )( )( )kNX kXkWXk以以N=8為為例，例，分解分解為為2個個4點點的的DFT，然后做然后做8/2=4次

19、次蝶形運算蝶形運算即可求出即可求出所有所有8點點X(k)的值。的值。第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)復數(shù)乘法次數(shù)：復數(shù)乘法次數(shù)： N2復數(shù)加法次數(shù)：復數(shù)加法次數(shù)： N(N1)復數(shù)乘法次數(shù)：復數(shù)乘法次數(shù)： 2*(N/2)2+N/2=N2/2+N/2復數(shù)加法次數(shù)：復數(shù)加法次數(shù)： 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(

20、2h)、 x4(l) = x1(2h+1)，根據(jù)上面推導可得：根據(jù)上面推導可得：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

21、,1,N/4-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

22、/ 400( )( )( )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：

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

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

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

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

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

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

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

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

33、法：時間抽選法：是把輸入是把輸入 x(n) 按奇偶分解成兩個子序列，即按奇偶分解成兩個子序列，即 N 點點x(n) 序列序列 N/2 點子序列，而輸出點子序列，而輸出 X(k) 是按自然順序是按自然順序排列的。排列的。Q頻率抽選法：頻率抽選法：是把輸入是把輸入 x(n) 按照前后對半分開，而不是奇按照前后對半分開，而不是奇偶數(shù)分開，而輸出偶數(shù)分開，而輸出 X(k) 逐項分解成偶數(shù)點子序列和奇數(shù)點逐項分解成偶數(shù)點子序列和奇數(shù)點子序列。子序列。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)(

35、FFT) 按按 k 的奇偶將的奇偶將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 為為偶偶數(shù)數(shù)： 數(shù)數(shù) 為為奇奇：0,1,.,12Nn 則則 X(2r) 和和 X(2r+1) 分別是分別是 x1(n) 和和 x2(n) 的的 N/2 點點 DFT，記為記為 X1(k) 和和 X2(k)。1211202()( )NnrNnXrxXWkkn 為為偶偶數(shù)數(shù)：12222021()( )NnrNnXrxnkXWk為為奇奇數(shù)數(shù)：FFT：基2頻率抽選法 (DIF-FFT)第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-