DSP-5-2014(新)

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

2、r Transformv 1965 年，年，James W. Cooley 和和 John W. Tukey 在在計算數(shù)學(xué)計算數(shù)學(xué)（Mathematics of Computation）上發(fā)表了）上發(fā)表了“ 一種用機(jī)器計算復(fù)一種用機(jī)器計算復(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 的運(yùn)

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

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

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

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

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

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

10、：高效運(yùn)算的可能性分析：假定假定x(n)為為4點(diǎn)長的信號，對其做點(diǎn)長的信號，對其做4點(diǎn)點(diǎn)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個特點(diǎn)：個特點(diǎn)：)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)因子的特點(diǎn)顯然顯然N值越小越有利！值越小越有利！第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)vFFT 算法分類算法分類: 時間時間抽選法抽選法 DIT: Decimation-In-Time 頻率頻率抽選法抽選法 DIF: Decimation-In-Frequencyv基本思路：基本思路：Q雖然存在不同的雖然存在不同的 FFT 方法，但其核心思想大致相同，方法，但其核心思想大致相同，即通過即通過迭代迭代，反復(fù)利用，反復(fù)利用低點(diǎn)數(shù)低點(diǎn)數(shù)的的 DFT 完成高點(diǎn)數(shù)的完成高點(diǎn)數(shù)的 DFT 計算，以此達(dá)到降低運(yùn)算量的目的。計

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

13、補(bǔ)零。 將序列將序列 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ù)取樣點(diǎn)偶數(shù)取樣點(diǎn)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ù)取樣點(diǎn)奇數(shù)取樣點(diǎn)DFT為：為： k 的整個范圍為的整個范圍為 0(N-1)，而，而X1(k)、X2(k) 是由是由 N/2 個樣點(diǎn)形成的個樣點(diǎn)形成的 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當(dāng)當(dāng)時時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) 的計算，可以分解為的計算，可以分解為前、后半部分前、后半部分的運(yùn)的運(yùn)算。而算。而只要求出前一半只要求出前一半，就可以由上式求出整個序列。，就可以由上式求出整個序列。同理同理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ù)點(diǎn)的偶數(shù)點(diǎn)的 DFT奇數(shù)點(diǎn)的奇數(shù)點(diǎn)的 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點(diǎn)點(diǎn)的的DFT，然后做然后做8/2=4次

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

20、2h)、 x4(l) = x1(2h+1)，根據(jù)上面推導(dǎo)可得：根據(jù)上面推導(dǎo)可得：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 點(diǎn)點(diǎn) DFT當(dāng)當(dāng) 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的信號流圖可知，當(dāng)?shù)男盘柫鲌D可知，當(dāng)N=2L時，共有時，共有 級級蝶形運(yùn)算；每級都由蝶形運(yùn)算；每級都由 個蝶形運(yùn)算組成，而每個蝶形有個蝶形運(yùn)算組成，而每個蝶形有 次復(fù)乘、次復(fù)乘、 次復(fù)加，因此每級運(yùn)算都需次復(fù)加，因此每級運(yùn)算都需 次復(fù)乘和次復(fù)乘和 次復(fù)加。次復(fù)加。 LN/2 N/2 12N按時間抽取基2-FFT算法與直接計算DFT運(yùn)算量的比較 第第5 5章章 快

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

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

27、 =W2LJ =WN 2L-M = WNp=J2M-L， J=0,1,2, ,2L-11FFT：DITFFT的運(yùn)算規(guī)律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)3、同一級中，同一旋轉(zhuǎn)因子對應(yīng)蝶形數(shù)目、同一級中，同一旋轉(zhuǎn)因子對應(yīng)蝶形數(shù)目 第第L級級FFT運(yùn)算中，運(yùn)算中，同一旋轉(zhuǎn)因子同一旋轉(zhuǎn)因子用在用在2M-L個蝶形中；個蝶形中；4、同一級中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的、同一級中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的“距離距離” 第第L級中，蝶距：級中，蝶距：D=2L。5、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離、同一蝶形運(yùn)算兩輸入數(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的運(yùn)算規(guī)律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)7、蝶形運(yùn)算的規(guī)律、蝶形運(yùn)算的規(guī)律 序列經(jīng)過時域抽選后，存入數(shù)組中，如果蝶形運(yùn)序列經(jīng)過時域抽選后，存入數(shù)組中，如果蝶形運(yùn)算的兩個輸入數(shù)據(jù)相距算的兩個輸入數(shù)據(jù)相距B個點(diǎn)，應(yīng)用原

29、位計算，蝶形個點(diǎn)，應(yīng)用原位計算，蝶形運(yùn)算可表示成如下形式：運(yùn)算可表示成如下形式： 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的運(yùn)算規(guī)律及編程思想的運(yùn)算規(guī)律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)8.輸入位序重排輸入位序重排 N 點(diǎn)點(diǎn) DFT 分解為兩個分解為兩個 N/2 點(diǎn)點(diǎn) DFT輸入序列按奇偶分組輸入序列按奇偶分組再分解再分解再奇偶重排再奇偶重排直到直到 2 點(diǎn)點(diǎn)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 十十進(jìn)進(jìn)制制01010101(000)(0)(100)(4)(010)(2)(110)(6)(001)(1)(101)(5)(011)(3)(111)(7)xxxxxxxxxxxxxxxx010011n0n1n2FFT：DITFFT的運(yùn)算規(guī)律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(F

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

32、儲器個存儲器FFT的實(shí)現(xiàn)的實(shí)現(xiàn)1. 輸入輸入x(n)-N個點(diǎn)；個點(diǎn)；2. 位倒序后存儲在位倒序后存儲在N個存儲器中；個存儲器中；3. 逐級蝶形運(yùn)算，輸逐級蝶形運(yùn)算，輸出結(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 點(diǎn)點(diǎn)x(n) 序列序列 N/2 點(diǎn)子序列，而輸出點(diǎn)子序列，而輸出 X(k) 是按自然順序是按自然順序排列的。排列的。Q頻率抽選法：頻率抽選法：是把輸入是把輸入 x(n) 按照前后對半分開，而不是奇按照前后對半分開，而不是奇偶數(shù)分開，而輸出偶數(shù)分開，而輸出 X(k) 逐項(xiàng)分解成偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)逐項(xiàng)分解成偶數(shù)點(diǎn)子序列和奇數(shù)點(diǎn)子序列。子序列。v DFT 變換表達(dá)式為：變換表達(dá)式為：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 點(diǎn)點(diǎn) 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)-