第四章 快速傅里葉變換(FFT)

1、第四章第四章 快速傅里葉變換快速傅里葉變換 （FFT） 主要內(nèi)容主要內(nèi)容 qDIT-FFT算法算法 qDIF-FFT算法算法 qIFFT算法算法 qChirp-FFT算法算法 q線性卷積的線性卷積的FFT算法算法 4.1 引言引言 q FFT: Fast Fourier Transform q 1965年，年，Cooley-Turky 發(fā)表文章發(fā)表文章機(jī)器計(jì)算傅機(jī)器計(jì)算傅 里葉級(jí)數(shù)的一種算法里葉級(jí)數(shù)的一種算法，提，提出出FFT算法，解決算法，解決 DFT運(yùn)算量太大，在實(shí)際使用中受限制的問(wèn)題。運(yùn)算量太大，在實(shí)際使用中受限制的問(wèn)題。 q FFT的應(yīng)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信的應(yīng)用。頻譜分析、

2、濾波器實(shí)現(xiàn)、實(shí)時(shí)信 號(hào)處理等。號(hào)處理等。 q DSP芯片實(shí)現(xiàn)。芯片實(shí)現(xiàn)。TI公司的公司的TMS 320c30，10MHz 時(shí)鐘，基時(shí)鐘，基2-FFT1024點(diǎn)點(diǎn)FFT時(shí)間時(shí)間15ms。 q 典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等 )()(kXnx DFT )()()(nynhnx FFTnh nyIFFT FFTnx )( )( )( 系統(tǒng)分析系統(tǒng)分析 頻譜分析與功率譜計(jì)算頻譜分析與功率譜計(jì)算 4.2 直接計(jì)算直接計(jì)算DFT的問(wèn)題及改進(jìn)途徑的問(wèn)題及改進(jìn)途徑 1 0 )()( N n kn N WnxkX 1 0 )( 1 )( N k kn N WkX N nx

3、1、 DFT與與IDFT ( )Nx n點(diǎn)有限長(zhǎng)序列 2、DFT與與IDFT運(yùn)算特點(diǎn)運(yùn)算特點(diǎn) 復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法 一個(gè)一個(gè)X(k)NN 1 N個(gè)個(gè)X(k) (N點(diǎn)點(diǎn)DFT) N 2N (N 1) 1 0 ( ) N nk N n x n W ajbcjdacbdj adcb 同理：同理：IDFT運(yùn)算量與運(yùn)算量與DFT相同。相同。 實(shí)數(shù)乘法實(shí)數(shù)乘法實(shí)數(shù)加法實(shí)數(shù)加法 一次復(fù)乘一次復(fù)乘42 一次復(fù)加一次復(fù)加2 一個(gè)一個(gè)X (k) 4N2N+2 (N 1)=2 (2N 1) N個(gè)個(gè)X (k) (N點(diǎn)點(diǎn)DFT) 4N 22N (2N 1) 3、降低、降低DFT運(yùn)算量的考慮運(yùn)算量的考慮 nk

4、 N W 的特性 *()() () nknkN n kn N k NNNN WWWW 對(duì)稱性 ()() nkN n kn N k NNN WWW 周期性 nkmnk NmN WW可約性 / / nknk m NN m WW 0/2(/2) 11 Nk Nk NNNN WWWW 特殊點(diǎn)： 2 jnk nk N N We Nknk NN WW nNnk NN WW 2 jmnk mN e 2 2 1 N j j N ee FFT算法分類算法分類: q 時(shí)間抽選法時(shí)間抽選法 DIT: Decimation-In-Time q 頻率抽選法頻率抽選法 DIF: Decimation-In-Frequen

5、cy FFT DFTDFT DFTDFT 算法的基本思想： 利用系數(shù)的特性，合并運(yùn)算中的某些項(xiàng)， 把長(zhǎng)序列短序列，從而減少其運(yùn)算量。 4.3 按時(shí)間抽?。ò磿r(shí)間抽?。―IT）的）的FFT算法算法 12/.210 ) 12()( )2()( 2 1 Nr rxrx rxrx ， （Decimation In Time） 1、算法原理、算法原理 設(shè)序列點(diǎn)數(shù)設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。為整數(shù)。 若不滿足，則補(bǔ)零若不滿足，則補(bǔ)零 將序列將序列x(n)按按n的奇偶分成兩組：的奇偶分成兩組： N為為2的整數(shù)冪的的整數(shù)冪的FFT算法稱算法稱基基-2FFT算法算法。 將將N點(diǎn)點(diǎn)DFT定義式分解為兩個(gè)

6、長(zhǎng)度為定義式分解為兩個(gè)長(zhǎng)度為N/2的的DFT 1 0 )()()( N n kn N WnxnxDFTkX kr N n N r rk N n N r WrxWrx )12( 12/ 0 2 12/ 0 ) 12()2( 為奇為偶 )( 12/ 0 2/2 )( 2/ 12/ 0 1 21 )()( kX N r rk N k N kX rk N N r WrxWWrx )()()( 21 kXWkXkX k N 記：記： （1 1） rk N rk N WW 2/ 2 （這一步利用：（這一步利用： ） ,0,1,./2 1r kN 再利用周期性求再利用周期性求X(k)的后半部分的后半部分 /

7、2 2 N k Nkk NNNN WWWW 又 )( 2 )()()( 2 22 1 12/ 0 2/1 12/ 0 )2/( 2/11 kXk N X kXWrxWrxk N X N r rk N N r kNr N rk N kNr N WW 2/ )2/( 2/ )2( ) 2 () 2 () 2 ( 12/,.2 , 1 , 0)()()( 2 )2/( 1 21 k N XWk N Xk N X NkkXWkXkX kN N k N ， 12/,.2 , 1 , 0)()( 21 NkkXWkX k N ， 將上式表達(dá)的運(yùn)算用一個(gè)專用將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形蝶形”信流圖表示。

8、信流圖表示。 )( 1 kX )( 2 kX )()( 21 kXWkX k N )()( 21 kXWkX k N k N W 12 12 ( )( )( ) ()( )( ) 2 k N k N X kX kW Xk N X kX kW Xk 0,1,.,/21kN 注：注：a. 上支路為加法，下支路為減法；上支路為加法，下支路為減法； b. 乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。 用用“蝶形結(jié)蝶形結(jié)”表示上面運(yùn)算的分解：表示上面運(yùn)算的分解： 3 28N )0(x )1 (x )2(x )3(x )4(x )5(x )6(x )7(x )0(X ) 1 (X )2(X )

9、3(X )4(X )5(X )6(X )7(X 1 N W 0 N W 2 N W 3 N W )0( 1 X )1 ( 1 X )2( 1 X )3( 1 X )0( 2 X )1 ( 2 X (3) 2 X )2( 2 X DFT N 點(diǎn) 2 DFT N 點(diǎn) 2 分解后的運(yùn)算量：分解后的運(yùn)算量： 復(fù)數(shù)乘法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法 一個(gè)一個(gè)N/2點(diǎn)點(diǎn)DFT(N/2)2N/2 (N/2 1) 兩個(gè)兩個(gè)N/2點(diǎn)點(diǎn)DFTN2/2N (N/2 1) 一個(gè)蝶形一個(gè)蝶形12 N/2個(gè)蝶形個(gè)蝶形N/2N 總計(jì)總計(jì) 2 2 /2/2 /2 NN N 2 /2 1 /2 N NN N 運(yùn)算量減少了近一半運(yùn)算量

10、減少了近一半 進(jìn)一步分解進(jìn)一步分解 M N2 1 2 2 M N 2 N 4 N 由于由于 ， 仍為偶數(shù)，因此，兩個(gè)仍為偶數(shù)，因此，兩個(gè) 點(diǎn)點(diǎn) DFTDFT又可同樣進(jìn)一步分解為又可同樣進(jìn)一步分解為4 4個(gè)個(gè) 點(diǎn)的點(diǎn)的DFTDFT。 13 14 (2 )( ) (21)( ) xlx l xlx l 0,1,.,/4 1lN 13/24 13/24 ( )( )( ) ()( )( ) 4 k N k N X kXkWXk N X kXkWXk 0,1,.,1 4 N k 0 2/N W 1 2/N W )( 3 lx )( 4 lx )2(x )4(x )6(x )0(x )0( 1 X )

11、1 ( 1 X )2( 1 X ) 3( 1 X ) 0( 3 X ) 1 ( 3 X )0( 4 X ) 1 ( 4 X DFT N 點(diǎn) 4 DFT N 點(diǎn) 4 “蝶形蝶形”信流圖表示信流圖表示 N點(diǎn)點(diǎn)DFT分解為四個(gè)分解為四個(gè)N/4點(diǎn)的點(diǎn)的DFT DFT N 點(diǎn) 4 DFT N 點(diǎn) 4 DFT N 點(diǎn) 4 DFT N 點(diǎn) 4 )2(x )4( x )6( x )0( x ) 1 ( x ) 3 ( x )5(x )7( x 0 N W 2 N W 0 N W 2 N W 1 N W 0 N W 2 N W 3 N W )0(X ) 1 (X ) 2(X ) 3(X ) 4(X ) 5(X

12、)6(X )7(X )( . kX )( . nx q 類似的分解一直繼續(xù)下去，直到分解為最類似的分解一直繼續(xù)下去，直到分解為最 后的兩類蝶形運(yùn)算為止后的兩類蝶形運(yùn)算為止(2點(diǎn)點(diǎn)DFT). q 如上述如上述N=8=23，N/4=2點(diǎn)中：點(diǎn)中： 類似進(jìn)一步分解類似進(jìn)一步分解 1點(diǎn)點(diǎn)DFTx(0) 1點(diǎn)點(diǎn)DFTx(4) X3(0) X3(1)0 2 W 進(jìn)一步簡(jiǎn)化為蝶形流圖：進(jìn)一步簡(jiǎn)化為蝶形流圖： 0 N W X3(0) X3(1) x(0) x(4) )4()0()4()0()0( 00 4/3 xWxxWxX NN )4()0()4()0() 1 ( 01 4/3 xWxxWxX NN 因此因

13、此8 8點(diǎn)點(diǎn)FFTFFT時(shí)間抽取方法的信流圖如下時(shí)間抽取方法的信流圖如下 )2(x )4(x )6(x )0(x ) 1 ( x ) 3 ( x )5(x )7(x 0 N W 0 N W 0 N W 0 N W 第一級(jí) . 0 N W 2 N W 0 N W 2 N W 第二級(jí) . )( 0 kX1m)( 1 kX)( 2 kX)( 3 kX 2m3m 1 N W 0 N W 2 N W 3 N W )0(X ) 1 (X )2(X )3(X )4(X )5(X )6(X )7(X 第三級(jí) . FFT運(yùn)算量與運(yùn)算特點(diǎn)運(yùn)算量與運(yùn)算特點(diǎn) 1 N=2L時(shí)，共有時(shí)，共有L=log2N級(jí)運(yùn)算；每一級(jí)有

14、級(jí)運(yùn)算；每一級(jí)有N/2 個(gè)蝶形結(jié)。個(gè)蝶形結(jié)。 2每一級(jí)有每一級(jí)有N個(gè)數(shù)據(jù)（中間數(shù)據(jù)），且每級(jí)只用到個(gè)數(shù)據(jù)（中間數(shù)據(jù)），且每級(jí)只用到 本級(jí)的轉(zhuǎn)入中間數(shù)據(jù)，適合于迭代運(yùn)算。本級(jí)的轉(zhuǎn)入中間數(shù)據(jù)，適合于迭代運(yùn)算。 3計(jì)算量：計(jì)算量： 每級(jí)每級(jí)N/2次復(fù)乘法，次復(fù)乘法，N次復(fù)加。（每蝶形只乘一次，次復(fù)加。（每蝶形只乘一次， 加減各一次）。共有加減各一次）。共有L*N/2=N/2log2N 次復(fù)乘法；次復(fù)乘法； 復(fù)加法復(fù)加法L*N=Nlog2N 次。與直接次。與直接DFT定義式運(yùn)算定義式運(yùn)算 量相比量相比(倍數(shù)倍數(shù)) N2/(Nlog2N) 。當(dāng)。當(dāng) N大時(shí)，此倍數(shù)大時(shí)，此倍數(shù) 很大。很大。 2 2 2

15、()2 ()log log 2 F F mDFTNN N mFFTN N 比較比較DFT 參考參考P150 表表4-1 圖圖4-6 可以直觀看出，當(dāng)點(diǎn)數(shù)可以直觀看出，當(dāng)點(diǎn)數(shù)N越大時(shí)，越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更突出。的優(yōu)點(diǎn)更突出。 按時(shí)間抽取按時(shí)間抽取FFT蝶形運(yùn)算特點(diǎn)蝶形運(yùn)算特點(diǎn) 1、關(guān)于、關(guān)于FFT運(yùn)算的混序與順序處理（位倒序處理）運(yùn)算的混序與順序處理（位倒序處理） 由于輸入序列按時(shí)間序位的奇偶抽取，故輸入序由于輸入序列按時(shí)間序位的奇偶抽取，故輸入序 列是混序的，為此需要先進(jìn)行混序處理。列是混序的，為此需要先進(jìn)行混序處理。 混序規(guī)律：混序規(guī)律： x(n)按按n位置進(jìn)行碼位（二進(jìn)制）倒置位置進(jìn)行碼

16、位（二進(jìn)制）倒置 規(guī)律輸入，而非自然排序，即得到混序排列。所規(guī)律輸入，而非自然排序，即得到混序排列。所 以稱為位倒序處理。以稱為位倒序處理。 位倒序?qū)崿F(xiàn)：位倒序?qū)崿F(xiàn)： （1）DSP實(shí)現(xiàn)采用位倒序?qū)ぶ穼?shí)現(xiàn)采用位倒序?qū)ぶ?（2）通用計(jì)算機(jī)實(shí)現(xiàn)可以有兩個(gè)方法：一是嚴(yán)格按）通用計(jì)算機(jī)實(shí)現(xiàn)可以有兩個(gè)方法：一是嚴(yán)格按 照位倒序含義進(jìn)行；二是倒進(jìn)位的加照位倒序含義進(jìn)行；二是倒進(jìn)位的加N/2。 倒位序倒位序自然序自然序 00000000 10041001 01022010 11063011 00114100 10155101 01136110 11177111 2102 ( )()x nnn n n倒位序倒位

17、序 例例 計(jì)算計(jì)算 ， 。計(jì)算。計(jì)算 點(diǎn)點(diǎn)FFTFFT。用時(shí)間抽取輸入倒序算法，。用時(shí)間抽取輸入倒序算法， 問(wèn)倒序前寄存器的數(shù)問(wèn)倒序前寄存器的數(shù) 和倒序后和倒序后 的的 數(shù)據(jù)值？數(shù)據(jù)值？ 2 )(nnx31.2 , 1 , 0n 32N )13( x)13( x 16913)13( 2 x 5 232 N 210 )01101()13( 102 )22()10110( 48422)13( 2 x 解：倒序前解：倒序前 倒序倒序 倒序?yàn)榈剐驗(yàn)?倒序后倒序后 DIT FFT中最主要的蝶形運(yùn)算實(shí)現(xiàn)中最主要的蝶形運(yùn)算實(shí)現(xiàn) （1）參與蝶形運(yùn)算的兩類結(jié)點(diǎn)（信號(hào)）間）參與蝶形運(yùn)算的兩類結(jié)點(diǎn)（信號(hào)）間“距離距

18、離” （碼地址）與其所處的第幾級(jí)蝶形有關(guān)；第（碼地址）與其所處的第幾級(jí)蝶形有關(guān)；第m 級(jí)的級(jí)的“結(jié)距離結(jié)距離”為為 (即原位計(jì)算迭代）即原位計(jì)算迭代） （2）每級(jí)迭形結(jié)構(gòu)為）每級(jí)迭形結(jié)構(gòu)為 ， 1 2 m )2(,.2 , 1 L NLm r N m mm m m r N m mmm WkXkXkX WkXkXkX )2()()2( )2()()( 1 11 1 1 11 q 蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表值，表 示成示成L位二進(jìn)制數(shù)，左移位二進(jìn)制數(shù)，左移L m位，把右位，把右 邊空出的位置補(bǔ)零，結(jié)果為邊空出的位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。的二進(jìn)制數(shù)。 2 (

19、 )2 L m rk （3） 的確定：的確定： 第第m級(jí)的級(jí)的r取值：取值： r N W k N W DIT算法的其他形式流圖算法的其他形式流圖 q 輸入倒位序輸出自然序輸入倒位序輸出自然序 q 輸入自然序輸出倒位序輸入自然序輸出倒位序 q 輸入輸出均自然序輸入輸出均自然序 q 相同幾何形狀相同幾何形狀 q 輸入倒位序輸出自然序輸入倒位序輸出自然序 q 輸入自然序輸出倒位序輸入自然序輸出倒位序 參考參考P154-155 時(shí)間抽取、時(shí)間抽取、 輸入自然順序、輸入自然順序、 輸出倒位序的輸出倒位序的FFTFFT流圖流圖 0 N W 0 N W 0 N W 2 N W 1 1 1 0 N W 1 0

20、 N W 2 N W 1 11 1 X(0)x(0) X(4)x(1) X(2)x(2) X(6)x(3) X(1)x(4) X(5)x(5) X(3)x(6) X(7)x(7) 1 1 0 N W 0 N W 2 N W 1 N W 3 N W 1 1 例例 用用FFT算法處理一幅算法處理一幅NN點(diǎn)的二維圖像，如用每秒可點(diǎn)的二維圖像，如用每秒可 做做10萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)萬(wàn)次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問(wèn)需要多少時(shí)間時(shí)，問(wèn)需要多少時(shí)間 （不考慮加法運(yùn)算時(shí)間）？（不考慮加法運(yùn)算時(shí)間）？ 解解 當(dāng)當(dāng)N=1024點(diǎn)時(shí)，點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘算法處理一幅二維圖像所需

21、復(fù)數(shù)乘 法約為法約為 次，僅為直接計(jì)算次，僅為直接計(jì)算DFT所需時(shí)間的所需時(shí)間的10萬(wàn)萬(wàn) 分之一。分之一。 即原需要即原需要3000小時(shí)，現(xiàn)在只需要小時(shí)，現(xiàn)在只需要2 分鐘。分鐘。 72 2 2 10log 2 N N 4.4 按頻率抽?。ò搭l率抽取（DIF）的）的FFT算法算法 q 與與DIT-FFT算法類似分解，但是抽取的是算法類似分解，但是抽取的是X(k)。 即分解即分解X(k)成奇數(shù)與偶數(shù)序號(hào)的兩個(gè)序列。成奇數(shù)與偶數(shù)序號(hào)的兩個(gè)序列。 q 設(shè)：設(shè)： N = 2L，L 為整數(shù)。將為整數(shù)。將X(k)按按k的奇偶分的奇偶分 組前，先將輸入組前，先將輸入x(n)按按n的順序分成前后兩半：的順序分

22、成前后兩半： （Decimation In Frequency) 一、算法原理一、算法原理 1 2/ 12/ 0 )()()( N Nn nk N N n nk N WnxWnxkX 12/ 0 )( 2 12/ 0 2 )()( N n kn N N N n nk N N WnxWnx 12/ 0 2 2/ )()( N n nk N N kN N WnxWnx kNk N W) 1( 2/ /2 1 0 ( )( 1) 2 N knk N n N x nx nW 0,1,.,1kN 下面討論下面討論 ：的)(12,2kXrrk 12/ 0 2/2 12/ 0 2 2 ) 1 ()()( )

23、()()2( N n nr N N N n rn N N Wnxnx WnxnxrX 12/ 0 2/2 12/ 0 )12( 2 )2()()( )()() 12( N n nr N n N N N n nr N N WWnxnx WnxnxrX 按按k k的奇偶將的奇偶將X(k)X(k)分成兩部分：分成兩部分： 顯然：顯然： 。點(diǎn)的對(duì)應(yīng)兩個(gè)DFTNrXrX2/) 12(),2( n N N N Wnxnxnx nxnxnx )()()( )()()( 22 21 )( )( 2 N nx nx n N N N Wnxnx nxnx )()( )()( 2 2 n N W 令：令： 用蝶型結(jié)

24、構(gòu)圖表示為：用蝶型結(jié)構(gòu)圖表示為： x1(0) x1(1) -1 x1(2) x1(3) -1 x2(0) x2(1) -1 x2(2) x2(3) -1 N/2點(diǎn) DFT N/2點(diǎn) DFT x(0) x(7) x(1) x(2) x(3) x(4) x(5) x(6) X1(0)=X(0) X2(0)=X(1) X1(1)=X(2) X1(2)=X(4) X1(3)=X(6) X2(1)=X(3) X2(2)=X(5) X2(3)=X(7) 1 N W 0 N W 2 N W 3 N W 311 411/2 ( )( )(/4) ( ) ( )(/4) n N x nx nx nN x nx

25、nx nNW 0,1,.,1 4 N n 313 414 ( )(2 ) ( ) ( )(21)( ) X kXkDFT x n X kXkDFT x n 0,1,.,1 4 N k N/2仍為偶數(shù)，進(jìn)一步分解：仍為偶數(shù)，進(jìn)一步分解：N/2 N/4 x3(0) x3(1) -1 -1 x4(0) x4(1) N/4點(diǎn) DFT N/4點(diǎn) DFT x1(0) x1(1) x1(2) x1(3) X3(0)=X1(0)=X(0) X4(0)=X1(1)=X(2) X3(1)=X1(2)=X(4) X4(1)=X1(3)=X(6) 0 /2N W 1 /2N W q 按照以上思路繼續(xù)分解，即一個(gè)按照以

26、上思路繼續(xù)分解，即一個(gè)N/2的的DFT分解成兩個(gè)分解成兩個(gè)N/4 點(diǎn)點(diǎn)DFT，直到只計(jì)算，直到只計(jì)算2點(diǎn)的點(diǎn)的DFT，這就是，這就是DIF-FFT算法。算法。 2個(gè)個(gè)1點(diǎn)的點(diǎn)的DFT蝶形流圖蝶形流圖 進(jìn)一步簡(jiǎn)化為蝶形流圖：進(jìn)一步簡(jiǎn)化為蝶形流圖： 1點(diǎn)點(diǎn)DFTx3(0) 1點(diǎn)點(diǎn)DFT x3(1) X(0) X(4) 0 2 W 0 2 W X(0) X(4) x3(0) x3(1) )2(x )4(x )6(x )0(x )1(x )3(x )5(x )7(x )0(X )1(X )2(X )3(X )4(X )5(X )6(X )7(X 0 N W 0 N W 1 N W 2 N W 3 N

27、W 0 N W 0 N W 0 N W 2 N W 0 N W 2 N W 0 N W 1m第一級(jí)： 2m第二級(jí)： 3m第三級(jí)： 二、按頻率抽取二、按頻率抽取FFT蝶形運(yùn)算特點(diǎn)蝶形運(yùn)算特點(diǎn) 1）原位計(jì)算）原位計(jì)算 11 11 ( )( )( ) ( )( )( ) mmm r mmmN XkXkXj XjXkXj W r N W 1( )m Xk 1( )m Xj ( ) m Xk ( ) m Xj -1 L級(jí)蝶形運(yùn)算，每級(jí)級(jí)蝶形運(yùn)算，每級(jí)N/2個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)：個(gè)蝶形，每個(gè)蝶形結(jié)構(gòu)： m表示第表示第m級(jí)迭代，級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)表示數(shù)據(jù)所在的行數(shù) 2）蝶形運(yùn)算）蝶形運(yùn)算 對(duì)對(duì)

28、N=2L點(diǎn)點(diǎn)FFT，輸入自然序，輸出倒位序，輸入自然序，輸出倒位序， 兩節(jié)點(diǎn)距離：兩節(jié)點(diǎn)距離：2L-m=N / 2m 11 11 ( )( ) 2 ( ) 22 mmm m r mmmN mm N XkXkXk NN XkXkXkW 第第m級(jí)運(yùn)算：級(jí)運(yùn)算： q 蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為蝶形運(yùn)算兩節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)為k值，表示值，表示 成成L位二進(jìn)制數(shù)，左移位二進(jìn)制數(shù)，左移m-1位，把右邊空出的位，把右邊空出的 位置補(bǔ)零，結(jié)果為位置補(bǔ)零，結(jié)果為r的二進(jìn)制數(shù)。的二進(jìn)制數(shù)。 r N W 的確定 1 2 ( )2mrk 存儲(chǔ)單元存儲(chǔ)單元 輸入序列輸入序列x(n) : N個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元 r N

29、W系數(shù)系數(shù) ：N / 2個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元 三、三、DIT與與DIF的異同的異同 q 基本蝶形不同基本蝶形不同 2 log 2 F N mN 2 log F aNN q DIT: 先復(fù)乘后加減先復(fù)乘后加減 q DIF: 先減后復(fù)乘先減后復(fù)乘 q 運(yùn)算量相同運(yùn)算量相同 q 都可原位運(yùn)算都可原位運(yùn)算 q DIT和和DIF的基本蝶形互為轉(zhuǎn)置的基本蝶形互為轉(zhuǎn)置 4.5 IDFT的的FFT算法算法 （FFT應(yīng)用一）應(yīng)用一） 一、從定義比較分析一、從定義比較分析 kn N N k WkX N kXIDFTnx 1 0 )( 1 )()( 1 0 )()()( N n kn N WnxnxDFTkX 與與

30、DFT的比較：的比較： 1）、旋轉(zhuǎn)因子）、旋轉(zhuǎn)因子WN-kn 的不同；的不同； 2）、結(jié)果還要乘）、結(jié)果還要乘 1/N。 )( 1 0 * 1 0 * * * * )( 1 )( 1 )()( kXDFT kn N N k kn N N k WkX N WkX N kXIDFTnx 二、實(shí)現(xiàn)算法二、實(shí)現(xiàn)算法直接使用直接使用FFT程序的算法程序的算法 * * )( 1 )(kXDFT N nx 共軛共軛FFT共軛共軛 乘乘1/ N ( )X k * ( )Xk( )x n 直接調(diào)用直接調(diào)用FFT子程序計(jì)算子程序計(jì)算IFFT的方法：的方法： 4.6 線性調(diào)頻線性調(diào)頻Z變換（變換（Chirp-Z變換

31、）算變換）算 法法 （FFT應(yīng)用二）應(yīng)用二） 單位圓與非單位圓采樣單位圓與非單位圓采樣 （a） 沿單位圓采樣沿單位圓采樣; (b) 沿沿AB弧采樣弧采樣 oo oo AB X(ej) RezRez jImzjImz A B (a)(b) X(ej) 螺線采樣螺線采樣 0 jImz Rezo 0 A0 1.0 zM1 A0W01 z0 (M I) 0 zk=AW-k k=0, 1, , M-1 0 0 0 0 j j eWW eAA Chirp-Z變換的線性系統(tǒng)表示變換的線性系統(tǒng)表示 x(n) 2/ 2 )( n Wnh 2/ 2 nnW A g(n) h(n) 1 / h(n) X(zn) 由

32、于系統(tǒng)的單位脈沖響應(yīng)由于系統(tǒng)的單位脈沖響應(yīng) 可以想象為頻率可以想象為頻率 隨時(shí)間隨時(shí)間(n)(n)呈線性增長(zhǎng)的復(fù)指數(shù)序列。在雷達(dá)系統(tǒng)中呈線性增長(zhǎng)的復(fù)指數(shù)序列。在雷達(dá)系統(tǒng)中, ,這這 種信號(hào)稱為種信號(hào)稱為線性調(diào)頻信號(hào)（線性調(diào)頻信號(hào)（Chirp SignalChirp Signal），因此，這，因此，這 里的變換稱為里的變換稱為線性調(diào)頻線性調(diào)頻Z Z變換變換。 2 2 )( n Wnh 一、基本算法思路一、基本算法思路 1 0 )()()()()( M m mnxmhnhnxny LMM d )1()(nMhnh 2/LMmd 4.7 線性卷積的線性卷積的FFT算法算法 （FFT應(yīng)用三）應(yīng)用三）

33、若若L點(diǎn)點(diǎn)x(n)，M點(diǎn)點(diǎn)h(n)， 則直接計(jì)算其線性卷積則直接計(jì)算其線性卷積y(n) 需運(yùn)算量：需運(yùn)算量： 若系統(tǒng)滿足線性相位，即：若系統(tǒng)滿足線性相位，即： 則需運(yùn)算量：則需運(yùn)算量： FFT法：以圓周卷積代替線性卷積法：以圓周卷積代替線性卷積 21 m NML令 ( )01 ( ) 01 x nnL x n LnN ( )01 ( ) 01 h nnM h n MnN N( )( )* ( )( ) ( )y nx nh nx nh n則 N N 2 log 2 N N 2 log 2 N N 2 log 2 )()() 1nhFFTkH )()()2nxFFTkX )()()()3kXkH

34、kY )()()4kYIFFTny N 總運(yùn)算量：總運(yùn)算量： 次乘法次乘法NN N mF 2 log 2 3 比較直接計(jì)算和比較直接計(jì)算和FFT法計(jì)算的運(yùn)算量法計(jì)算的運(yùn)算量 2 2(1 3/2*log) d m F mML K mNN 2 22 41 3/2*(1log)106log m MM K MMM 2 23log m M K L 討論：討論： ML12NMLM 則1）當(dāng)）當(dāng) 1NMLL 則2）當(dāng)）當(dāng) m LK 需采用分段卷積 重疊相加法 重疊保留法 ML 見(jiàn)見(jiàn) P183 表表 x(n)長(zhǎng)度很長(zhǎng)時(shí)，將長(zhǎng)度很長(zhǎng)時(shí)，將x(n)分為分為L(zhǎng)長(zhǎng)的若干長(zhǎng)的若干 小的片段，小的片段，L與與M可比擬?？?/p>

35、比擬。 n LiniLnx nxi ，其它 ， 0 1) 1()( )( i i nxnx)()( )()()(nhnxny i i nhnx)()( 1 1、重疊相加法、重疊相加法 i i ny)( 則：則： 輸出：輸出： )()()(nhnxny ii 1MLN 其中：其中： 可以用圓周卷積計(jì)算：可以用圓周卷積計(jì)算： m N2 選選 ，上面圓周卷積可用，上面圓周卷積可用FFTFFT計(jì)算。計(jì)算。 )()()(nhnxny ii N 由于由于yi(n)長(zhǎng)度為長(zhǎng)度為N，而，而xi(n)長(zhǎng)度長(zhǎng)度L ，必有，必有M-1 點(diǎn)重疊，點(diǎn)重疊， yi(n)應(yīng)相加才能構(gòu)成最后應(yīng)相加才能構(gòu)成最后y(n)的。的。

36、 i i nyny)()( h(n) 0N 1 M 1 x(n) 0 L 2L3L n n n n n L 1 0 x 0(n) N 1 0 x 1(n) L 2L 1 LN 1 3L 1 0 x 2(n) 2L 2LN 1 重疊相加法圖形重疊相加法圖形 n n n N 1 0 y0(n)x0(n) h (n)N 2L2L N 1 0 0 L N 1 L y1(n)x1(n) h (n)N y2(n)x2(n) h (n)N 和上面的討論一樣，和上面的討論一樣， 用用FFT法實(shí)現(xiàn)重疊相加法的步驟如下法實(shí)現(xiàn)重疊相加法的步驟如下: 計(jì)算計(jì)算N點(diǎn)點(diǎn)FFT， H(k)=DFTh(n)； 計(jì)算計(jì)算N點(diǎn)點(diǎn)FFT，Xi(k)=DFTxi(n)； 相乘，相乘，Yi(k)=Xi(k)H(k)； 計(jì)算計(jì)算N點(diǎn)點(diǎn)IFFT，yi(n)=IDFTYi(k)； 將各段將各段yi(n)（包括重疊部分）相加，（包括重疊部分）相加， 。 重疊相加的名稱是由于各輸出段的重疊部分相加而得名的。重疊相加的名稱是由于各輸出段的重疊部分相加而得名的。 )()( 0 nyny i i 例例 已知序列已知序列xn=n+2,0 n 12, hn=1,2,1試試 利用重疊相加法計(jì)算線性卷積利用重疊相加法計(jì)算線性卷積, 取取L=5 。 yn=2, 7, 12, 16, 20, 24,