1、第四章第四章快速傅里葉變換快速傅里葉變換（FFT）主要內(nèi)容主要內(nèi)容qDIT-FFT算法算法 qDIF-FFT算法算法qIFFT算法算法q線性卷積的線性卷積的FFT算法算法4.1 引言引言q FFT: Fast Fourier Transformq 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)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號(hào)處理等。號(hào)處理等。q DSP芯片實(shí)

2、現(xiàn)。芯片實(shí)現(xiàn)。q 典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等)()(kXnxDFT )()()(nynhnxFFTnhnyIFFTFFTnx)()()( 系統(tǒng)分析系統(tǒng)分析 頻譜分析與功率譜計(jì)算頻譜分析與功率譜計(jì)算4.2 直接計(jì)算直接計(jì)算DFT的問(wèn)題及改進(jìn)途徑的問(wèn)題及改進(jìn)途徑10)()(NnknNWnxkX10)(1)(NkknNWkXNnx1、 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 1N個(gè)個(gè)X(k)(N點(diǎn)點(diǎn)DFT)N 2N (N 1)10( )NnkNnx n Wajbc

3、jdacbdj 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)算量的考慮nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW對(duì)稱性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可約性/nknk mNN mWW0/2(/2) 11Nk NkNNNNWWWW 特殊點(diǎn)：2jnknkNNWeNknkNNWWnNnk

4、NNWW2jmnkmNe221NjjNee FFT算法分類算法分類:q 時(shí)間抽選法時(shí)間抽選法DIT: Decimation-In-Timeq 頻率抽選法頻率抽選法DIF: Decimation-In-FrequencyFFTDFTDFTDFTDFT算法的基本思想： 利用系數(shù)的特性，合并運(yùn)算中的某些項(xiàng)， 把長(zhǎng)序列短序列，從而減少其運(yùn)算量。4.3 按時(shí)間抽?。ò磿r(shí)間抽取（DIT）的）的FFT算法算法12/.210) 12()()2()(21Nrrxrxrxrx，（Decimation In Time）1、算法原理、算法原理設(shè)序列點(diǎn)數(shù)設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。為整數(shù)。 若不滿足，則補(bǔ)零若

5、不滿足，則補(bǔ)零將序列將序列x(n)按按n的奇偶分成兩組：的奇偶分成兩組：N為為2的整數(shù)冪的的整數(shù)冪的FFT算法稱算法稱基基-2FFT算法算法。將將N點(diǎn)點(diǎn)DFT定義式分解為兩個(gè)長(zhǎng)度為定義式分解為兩個(gè)長(zhǎng)度為N/2的的DFT10)()()(NnknNWnxnxDFTkXkrNnNrrkNnNrWrxWrx)12(12/0212/0) 12()2( 為奇為偶 )(12/02/2)(2/12/0121)()(kXNrrkNkNkXrkNNrWrxWWrx)()()(21kXWkXkXkN記：記： （1 1）rkNrkNWW2/2（這一步利用：（這一步利用： ）,0,1,./2 1r kN再利用周期性求再

6、利用周期性求X(k)的后半部分的后半部分/22NkNkkNNNNWWWW 又)(2)()()(222112/02/112/0)2/(2/11kXkNXkXWrxWrxkNXNrrkNNrkNrNrkNkNrNWW2/)2/(2/)2()2()2()2(12/,.2 , 1 , 0)()()(2)2/(121kNXWkNXkNXNkkXWkXkXkNNkN，12/,.2 , 1 , 0)()(21NkkXWkXkN，將上式表達(dá)的運(yùn)算用一個(gè)專用將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形蝶形”表示。表示。1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,

7、/21kN蝶形結(jié)的另外一種表示方法蝶形結(jié)的另外一種表示方法)(1kX)(2kX)()(21kXWkXkN)()(21kXWkXkNkNW注：注：a. 上支路為加法，下支路為減法；上支路為加法，下支路為減法； b. 乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。用用“蝶形結(jié)蝶形結(jié)”表示上面運(yùn)算的分解：表示上面運(yùn)算的分解： 328N分解后的運(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è)蝶形12N/2個(gè)蝶形個(gè)蝶形N/2N總計(jì)總計(jì)22/2/2/2NNN2/2 1/

8、2N NNN運(yùn)算量減少了近一半運(yùn)算量減少了近一半進(jìn)一步分解進(jìn)一步分解MN2122MN2N4N由于由于 ， 仍為偶數(shù)，因此，兩個(gè)仍為偶數(shù)，因此，兩個(gè) 點(diǎn)點(diǎn)DFTDFT又可同樣進(jìn)一步分解為又可同樣進(jìn)一步分解為4 4個(gè)個(gè) 點(diǎn)的點(diǎn)的DFTDFT。1314(2 )( )(21)( )xlx lxlx l0,1,.,/4 1lN13/2413/24( )( )( )()( )( )4kNkNX kXkWXkNX kXkWXk0,1,.,14Nk 02/NW12/NW)(3lx)(4lx)2(x)4(x)6(x)0(x)0(1X) 1 (1X)2(1X) 3(1X) 0(3X) 1 (3X)0(4X) 1

9、(4XDFTN點(diǎn)4DFTN點(diǎn)4“蝶形蝶形”信流圖表示信流圖表示 N點(diǎn)點(diǎn)DFT分解為四個(gè)分解為四個(gè)N/4點(diǎn)的點(diǎn)的DFTDFTN點(diǎn)4DFTN點(diǎn)4DFTN點(diǎn)4DFTN點(diǎn)4)2(x)4( x)6( x)0( x) 1 ( x) 3 ( x)5(x)7( x0NW2NW0NW2NW1NW0NW2NW3NW)0(X) 1 (X) 2(X) 3(X) 4(X) 5(X)6(X)7(X)(.kX)(.nxq 類似的分解一直繼續(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)

10、一步分解1點(diǎn)點(diǎn)DFTx(0)1點(diǎn)點(diǎn)DFTx(4)X3(0)X3(1)02W進(jìn)一步簡(jiǎn)化為蝶形流圖：進(jìn)一步簡(jiǎn)化為蝶形流圖：0NWX3(0)X3(1)x(0)x(4)4()0()4()0()0(004/3xWxxWxXNN)4()0()4()0() 1 (014/3xWxxWxXNN因此因此8 8點(diǎn)點(diǎn)FFTFFT時(shí)間抽取方法的信流圖如下時(shí)間抽取方法的信流圖如下)2(x)4(x)6(x)0(x) 1 ( x) 3 ( x)5(x)7(x0NW0NW0NW0NW第一級(jí).0NW2NW0NW2NW 第二級(jí).)(0kX1m)(1kX)(2kX)(3kX2m3m1NW0NW2NW3NW)0(X) 1 (X)2(

11、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í)有級(jí)運(yùn)算；每一級(jí)有N/2個(gè)蝶形結(jié)。個(gè)蝶形結(jié)。2每一級(jí)有每一級(jí)有N個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)(中間數(shù)據(jù)中間數(shù)據(jù))，且每級(jí)只用到本級(jí)，且每級(jí)只用到本級(jí)的轉(zhuǎn)入中間數(shù)據(jù)，適合于迭代運(yùn)算。的轉(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定

12、義式運(yùn)算定義式運(yùn)算量相比量相比(倍數(shù)倍數(shù)) N2/(Nlog2N) 。當(dāng)。當(dāng) N大時(shí)，此倍數(shù)大時(shí)，此倍數(shù)很大。很大。222()2()loglog2FFmDFTNNNmFFTNN比較比較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)更突出。 例例 用用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í)，

13、點(diǎn)時(shí)，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘算法處理一幅二維圖像所需復(fù)數(shù)乘法約為法約為 次，僅為直接計(jì)算次，僅為直接計(jì)算DFT所需時(shí)間的所需時(shí)間的10萬(wàn)萬(wàn)分之一。分之一。 即原需要即原需要3000小時(shí)，現(xiàn)在只需要小時(shí)，現(xiàn)在只需要2 分鐘。分鐘。 722210log2NN4.4 按頻率抽?。ò搭l率抽?。―IF）的）的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

14、(n)按按n的順序分成前后兩半：的順序分成前后兩半：（Decimation In Frequency)一、算法原理一、算法原理12/12/0)()()(NNnnkNNnnkNWnxWnxkX12/0)(212/02)()(NnknNNNnnkNNWnxWnx12/022/)()(NnnkNNkNNWnxWnxkNkNW) 1(2/2 10( )( 1)2NknkNnNx nx nW 0,1,.,1kN下面討論下面討論：的)(12,2kXrrk12/02/212/022) 1 ()()()()()2(NnnrNNNnrnNNWnxnxWnxnxrX12/02/212/0)12(2)2()()()

15、()() 12(NnnrNnNNNnnrNNWWnxnxWnxnxrX按按k k的奇偶將的奇偶將X(k)X(k)分成兩部分：分成兩部分：顯然：顯然：。點(diǎn)的對(duì)應(yīng)兩個(gè)DFTNrXrX2/) 12(),2(nNNNWnxnxnxnxnxnx)()()()()()(2221)()(2NnxnxnNNNWnxnxnxnx)()()()(22nNW令：令：用蝶型結(jié)構(gòu)圖表示為：用蝶型結(jié)構(gòu)圖表示為：x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(

16、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)1NW0NW2NW3NW311411/2( )( )(/4)( ) ( )(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 313414( )(2 ) ( )( )(21)( )X kXkDFT x nX kXkDFT x n0,1,.,14Nk N/2仍為偶數(shù)，進(jìn)一步分解：仍為偶數(shù)，進(jìn)一步分解：N/2 N/4x3(0)x3(1)-1-1x4(0)x4(1)N/4點(diǎn)DFTN/4點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)X3(0)=

17、X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)0/2NW1/2NWq 按照以上思路繼續(xù)分解，即一個(gè)按照以上思路繼續(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)DFTx3(1)X(0)X(4)02W02WX(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

18、)2(X)3(X)4(X)5(X)6(X)7(X0NW0NW1NW2NW3NW0NW0NW0NW2NW0NW2NW0NW1m第一級(jí)： 2m第二級(jí)：3m第三級(jí)：DIT與與DIF的異同的異同q 基本蝶形不同基本蝶形不同2log2FNmN2logFaNNq DIT: 先復(fù)乘后加減先復(fù)乘后加減q DIF: 先減后復(fù)乘先減后復(fù)乘q 運(yùn)算量相同運(yùn)算量相同q DIT和和DIF的基本蝶形互為轉(zhuǎn)置的基本蝶形互為轉(zhuǎn)置4.5 IDFT的的FFT算法算法（FFT應(yīng)用）應(yīng)用） 一、從定義比較分析一、從定義比較分析knNNkWkXNkXIDFTnx10)(1)()(10)()()(NnknNWnxnxDFTkX與與DFT

19、的比較：的比較： 1）、旋轉(zhuǎn)因子）、旋轉(zhuǎn)因子WN-kn 的不同；的不同； 2）、結(jié)果還要乘）、結(jié)果還要乘 1/N。 )(10*10*)(1)(1)()(kXDFTknNNkknNNkWkXNWkXNkXIDFTnx二、實(shí)現(xiàn)算法二、實(shí)現(xiàn)算法直接使用直接使用FFT程序的算法程序的算法*)(1)(kXDFTNnx共軛共軛FFT共軛共軛乘乘1/ N( )X k*( )Xk( )x n直接調(diào)用直接調(diào)用FFT子程序計(jì)算子程序計(jì)算IFFT的方法：的方法：一、基本算法思路一、基本算法思路10)()()()()(MmmnxmhnhnxnyLMMd)1()(nMhnh2/LMmd4.7 線性卷積的線性卷積的FFT

20、算法算法（FFT應(yīng)用）應(yīng)用）若若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法：以圓周卷積代替線性卷積法：以圓周卷積代替線性卷積21mNML令 ( )01( )01x nnLx nLnN( )01( )01h nnMh nMnNN( )( )* ( )( ) ( )y nx nh nx nh n則 NN2log2NN2log2NN2log2)()() 1nhFFTkH)()()2nxFFTkX)()()()3kXkHkY)()()4kYIFFTnyN總運(yùn)算量：總

21、運(yùn)算量： 次乘法次乘法NNNmF2log23比較直接計(jì)算和比較直接計(jì)算和FFT法計(jì)算的運(yùn)算量法計(jì)算的運(yùn)算量22(1 3/2*log)dmFmMLKmNN22241 3/2*(1log)106logmMMKMMM223logmMKL討論：討論：ML12NMLM 則1）當(dāng)）當(dāng)1NMLL 則2）當(dāng)）當(dāng)mLK 需采用分段卷積重疊相加法重疊保留法ML x(n)長(zhǎng)度很長(zhǎng)時(shí)，將長(zhǎng)度很長(zhǎng)時(shí)，將x(n)分為分為L(zhǎng)長(zhǎng)的若干長(zhǎng)的若干小的片段，小的片段，L與與M可比擬。可比擬。nLiniLnxnxi，其它，01) 1()()(iinxnx)()()()()(nhnxnyiinhnx)()(1 1、重疊相加法、重疊相加

22、法iiny)( 則：則： 輸出：輸出：)()()(nhnxnyii1MLN其中：其中：可以用圓周卷積計(jì)算：可以用圓周卷積計(jì)算：MN2 選選 ，上面圓周卷積可用，上面圓周卷積可用FFTFFT計(jì)算。計(jì)算。 )()()(nhnxnyiiN 由于由于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)的。的。iinyny)()(h(n)0N 1M 1x(n)0L2L3LnnnnnL 10 x0(n)N 10 x1(n)L2L 1LN 13L 10 x2(n)2L2LN 1重疊相加法圖形重疊相加法圖形nnnN 1

23、0y0(n)x0(n) h (n)N2L2L N 100L N 1Ly1(n)x1(n) h (n)Ny2(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)（包括重疊部分）相加，（包括重疊部分）相加， .重疊相加的名稱是由于各輸出段的重疊部分相加而得名的。重疊相加的名稱是由于各輸出段

24、的重疊部分相加而得名的。 )()(0nynyii例例 已知序列已知序列xn=n+2,0 n 12, hn=1,2,1試試?yán)弥丿B相加法計(jì)算線性卷積利用重疊相加法計(jì)算線性卷積, 取取L=5 。yn=2, 7, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 41, 14解解: 重疊相加法重疊相加法x1n=2, 3, 4, 5, 6x2n=7, 8, 9, 10, 11x3n=12,13, 14y1n=2, 7, 12, 16, 20, 17, 6y2n= 7, 22, 32, 36, 40, 32, 11y3n=12, 37, 52, 41, 142 2、重疊保存法、重疊保存法q 此方法與上述方法稍有不同。此方法與上述方法稍有不同。q 先將先將x(n)分段，每段分段，