DSP-5-2014(新)

1、第五章第五章 快速傅里葉變換快速傅里葉變換(FFT)數(shù)字信號(hào)處理數(shù)字信號(hào)處理 Digital Signal Processing中國(guó)民航大學(xué) 航空自動(dòng)化學(xué)院第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：引言Q直接計(jì)算直接計(jì)算DFT的問題及改進(jìn)的途徑的問題及改進(jìn)的途徑Q按按時(shí)間抽取時(shí)間抽取的基的基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 在在計(jì)算數(shù)學(xué)計(jì)算數(shù)學(xué)（Mathematics of Computation）上發(fā)表了）上發(fā)表了“ 一種用機(jī)器計(jì)算復(fù)一種用機(jī)器計(jì)算復(fù)序列傅立葉級(jí)數(shù)的算法（序列傅立葉級(jí)數(shù)的算法（An algorithm for the machine calculation of complex Fourier series）” 論文。論文。v 自此之后，新的算法不斷涌現(xiàn)。一種是自此之后，新的算法不斷涌現(xiàn)。一種是對(duì)對(duì)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：直接計(jì)算 DFT 的運(yùn)

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

5、：直接計(jì)算 DFT 的運(yùn)算量分析計(jì)算量分析計(jì)算量分析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 時(shí)，時(shí)，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：直接計(jì)算 DFT 的運(yùn)算量分析采用通用計(jì)算機(jī)，速度為平均每次復(fù)乘為采用通用計(jì)算機(jī)，速度為平均每次復(fù)乘為5s，每次復(fù)加為，每次復(fù)加為1 s，所用，所用時(shí)間時(shí)間:T=5*10-6 *10242+ 10-6 *1024*1023=6.290s第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)1.如果一臺(tái)通用計(jì)算機(jī)的速度為平均每次復(fù)乘 ，每次復(fù)加 ，用它來計(jì)算512點(diǎn)的

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

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

9、。FFT：直接計(jì)算 DFT 的運(yùn)算量分析第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：旋轉(zhuǎn)因子的特點(diǎn)把長(zhǎng)序列分解成短序列計(jì)算，然后再組合出結(jié)果。nkNW主要原理是利用系數(shù)主要原理是利用系數(shù) 的以下特性對(duì)的以下特性對(duì)DFT進(jìn)行分解：進(jìn)行分解： nkNW（1）對(duì)稱性）對(duì)稱性 ()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)長(zhǎng)的信號(hào)，對(duì)其做點(diǎn)長(zhǎng)的信號(hào)，對(duì)其做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個(gè)特點(diǎn)：個(gè)特點(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計(jì)算量？計(jì)算量？計(jì)算量？計(jì)算量？FFT：旋轉(zhuǎn)因子的特點(diǎn)顯然顯然N值越小越有利！值越小越有利！第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)vFFT 算法分類算法分類: 時(shí)間時(shí)間抽選法抽選法 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 計(jì)算，以此達(dá)到降低運(yùn)算量的目的。計(jì)

12、算，以此達(dá)到降低運(yùn)算量的目的。Q迭代：迭代：利用利用 WNkn 的周期性、特殊點(diǎn)和對(duì)稱性，合并的周期性、特殊點(diǎn)和對(duì)稱性，合并 DFT 計(jì)算中很多重復(fù)的計(jì)算，達(dá)到降低運(yùn)算量的目的。計(jì)算中很多重復(fù)的計(jì)算，達(dá)到降低運(yùn)算量的目的。Q低點(diǎn)數(shù)：低點(diǎn)數(shù)：將傅氏變換將傅氏變換 DFT 分解成相繼小的分解成相繼小的DFT計(jì)算，計(jì)算，即即 N 變小，而計(jì)算量與變小，而計(jì)算量與 N2 成正比。成正比。FFT：基本思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時(shí)間抽選法-算法原理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ù)序號(hào)組成，另一組由奇數(shù)序號(hào)組成。即一組由偶數(shù)序號(hào)組成，另一組由奇數(shù)序號(hào)組成。12( )(2 )0,1,12( )(21)x rxrNrx rxr 偶偶序序列列奇奇序序列列注意其長(zhǎng)度為注意其長(zhǎng)度為 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時(shí)間抽選法-算法原理第第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 的整個(gè)范圍為的整個(gè)范圍為 0(N-1)，而，而X1(k)、X2(k) 是由是由 N/2 個(gè)樣點(diǎn)形成的個(gè)樣點(diǎn)形成的 DFT，x(2r) 和和 x(2r1）的長(zhǎng)度為）的長(zhǎng)度為 N/2； 由這兩個(gè)偶數(shù)和奇數(shù)由這兩個(gè)偶數(shù)和奇數(shù) N/2 個(gè)時(shí)域樣值可以計(jì)算出前個(gè)時(shí)域樣值可以計(jì)算出前 N/2 個(gè)個(gè) DFT 系數(shù)，也可系數(shù)，也可以計(jì)算出后以計(jì)算出后 N/2 個(gè)個(gè) DFT 系數(shù)。系數(shù)。 問題：這前后問題：這前后 N/2 個(gè)個(gè) DFT 有無關(guān)系？有無關(guān)系？k 在在 N/2 (N-1) 時(shí)，時(shí)， X1(k)、X2(k)、WN 情況如何？情況如何？F

16、FT：基2時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)1122 , NNkN當(dāng)當(dāng)時(shí)時(shí)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時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT

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

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時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)122()( )( )kNNX kXkWXkFFT：基2時(shí)間抽選法-算法原理偶數(shù)序列偶數(shù)序列奇數(shù)序列奇數(shù)序列12( )( )( )kNX kXkWXk以以N=8為為例，例，分解分解為為2個(gè)個(gè)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時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)二次分解：二次分解：Q 將將x1(r)按按r取奇、偶可分解成取奇、偶可分解成2個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為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個(gè)長(zhǎng)個(gè)長(zhǎng)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時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)由于由于 N=2M，這樣逐級(jí)分解，直到，這樣逐級(jí)分解，直到 2 點(diǎn)點(diǎn) DFT當(dāng)當(dāng) N = 8時(shí)，可分解三次時(shí)，可分解三次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時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：基2時(shí)間抽選法-算法原理第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：

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

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

25、存儲(chǔ)單元中可依次存放單元中可依次存放X(k)的的N個(gè)值。個(gè)值。v原位計(jì)算原位計(jì)算：利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出數(shù)據(jù)的：利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出數(shù)據(jù)的方法。方法。v優(yōu)點(diǎn)優(yōu)點(diǎn)：節(jié)約存儲(chǔ)空間、降低設(shè)備成本。：節(jié)約存儲(chǔ)空間、降低設(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)算流圖中，每個(gè)蝶形都要乘以運(yùn)算流圖中，每個(gè)蝶形都要乘以旋轉(zhuǎn)因子旋轉(zhuǎn)因子WpN，p稱稱為旋轉(zhuǎn)因子的指數(shù)。為旋轉(zhuǎn)因子的指數(shù)。N8 23 時(shí)各級(jí)的旋轉(zhuǎn)因子時(shí)各級(jí)的旋轉(zhuǎn)因子 第一級(jí)：第一級(jí)：

26、L=1， 有有1個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子：WNp =WN/4J =W2LJ J=0 第二級(jí)：第二級(jí)：L=2，有，有2個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子：WNp =WN/2J =W2LJ J=0,1 第三級(jí)：第三級(jí)：L=3，有，有4個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子：WNp =WNJ =W2LJ J=0,1,2,3 對(duì)于對(duì)于N2M 的的一般情況，一般情況，第第L級(jí)級(jí)共有共有2L-1個(gè)不同的旋轉(zhuǎn)因子：個(gè)不同的旋轉(zhuǎn)因子： WNp =W2LJ J=0,1,2, ,2L-11 2L =2L M 2M = N 2L M 故：故： 按照上面兩式可以確定第按照上面兩式可以確定第L級(jí)運(yùn)算的旋轉(zhuǎn)因子。級(jí)運(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、同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目、同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目 第第L級(jí)級(jí)FFT運(yùn)算中，運(yùn)算中，同一旋轉(zhuǎn)因子同一旋轉(zhuǎn)因子用在用在2M-L個(gè)蝶形中；個(gè)蝶形中；4、同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的、同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的“距離距離” 第第L級(jí)中，蝶距：級(jí)中，蝶距：D=2L。5、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離 在輸入倒序，輸出原序的在輸入

28、倒序，輸出原序的FFT變換中，第變換中，第L級(jí)的每一個(gè)蝶形級(jí)的每一個(gè)蝶形的的2個(gè)輸入數(shù)據(jù)相距：個(gè)輸入數(shù)據(jù)相距：B=2L-1。 6、碼位顛倒、碼位顛倒 輸入序列輸入序列x(n)經(jīng)過經(jīng)過M級(jí)時(shí)域奇、偶抽選后，輸出序列級(jí)時(shí)域奇、偶抽選后，輸出序列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í)域抽選后，存入數(shù)組中，如果蝶形運(yùn)序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原

29、位計(jì)算，蝶形個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(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 分解為兩個(gè)分解為兩個(gè) 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ù)對(duì)照表順序和倒序二進(jìn)制數(shù)對(duì)照表FFT：DITFFT的運(yùn)算規(guī)律及編程思想第第5 5章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT)FFT：DITFFT的運(yùn)算規(guī)律及編程思想N個(gè)存

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

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