快速傅里葉變換武漢理工大學(xué)數(shù)字信號(hào)處理

1、第第5章章快速傅里葉變換快速傅里葉變換(FFT)Fast FourierTransforming快速付里葉變換快速付里葉變換FFT 有限長(zhǎng)序列通過離散傅里葉變換 (DFT)將其頻 域離散化成有限長(zhǎng)序列.但其計(jì)算量太大(與N的平方成正比）, 很難 實(shí)時(shí)地處理問題 , 因 此 引 出 了 快 速 傅 里 葉 變 換(FFT) . FFT 并 不 是 一 種 新 的 變 換 形 式 ,它 只 是 DFT 的 一 種 快快 速速 算算 法法 . 并 且 根 據(jù) 對(duì) 序 列 分 解 與 選 取 方 法 的 不 同 而 產(chǎn) 生 了 FFT 的 多 種 算 法 . FFT 在 離 散 傅 里 葉 反 變 換

2、 、 線 性 卷 積 和 線 性 相 關(guān) 等 方 面 也 有 重 要 應(yīng) 用.。二、FFT產(chǎn)生故事 當(dāng)時(shí)加文(Garwin)在自已的研究中極需要一個(gè)計(jì)算付里葉變換的快速方法。他注意到圖基(J.W.Turkey)正在寫有關(guān)付里葉變換的文章，因此詳細(xì)詢問了圖基關(guān)于計(jì)算付里葉變換的技術(shù)知識(shí)。圖基概括地對(duì)加文介紹了一種方法，它實(shí)質(zhì)上就是后來的著名的庫(kù)利(Cooley J.W)圖基算法。在加文的迫切要求下，庫(kù)利很快設(shè)計(jì)出一個(gè)計(jì)算機(jī)程序。1965年庫(kù)利-圖基在、Mathematic of Computation 雜志上發(fā)表了著名的“機(jī)器計(jì)算付里級(jí)數(shù)的一種算法”文章，提出一種快速計(jì)算DFT的方法和計(jì)算機(jī)程序

3、-揭開了FFT發(fā)展史上的第一頁(yè)，促使FFT算法產(chǎn)生原因還有1967年至1968年間FFT的數(shù)字硬件制成，電子數(shù)字計(jì)算機(jī)的條件， 使DFT的運(yùn)算大簡(jiǎn)化了。直接計(jì)算DFT的問題及改進(jìn)的基本途徑1.比較DFT與IDFT之間的運(yùn)算量10)()()(NnknNDFTWnxkXnx1, 1 , 0Nk101( )( )( )NIDFTknNkX kx nX k WN 1, 1 , 0Nn其中x(n)為復(fù)數(shù)， 也為復(fù)數(shù)所以。knNjknNeW22.以DFT為例，計(jì)算DFT復(fù)數(shù)運(yùn)算量 計(jì)算一個(gè)X(k)(一個(gè)頻率成分)值，運(yùn)算量為例k=1則要進(jìn)行N次復(fù)數(shù)乘法 (N-1)次復(fù)數(shù)加法所以，要完成整個(gè)DFT運(yùn)算，其計(jì)

4、算量為：N*N次復(fù)數(shù)相乘和次復(fù)數(shù)相乘和N*(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法10)() 1 (NnnNWnxX3.一次復(fù)數(shù)乘法換算成實(shí)數(shù)運(yùn)算量 復(fù)數(shù)運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間長(zhǎng)。 一個(gè)復(fù)數(shù)乘法包括4個(gè)實(shí)數(shù)乘法個(gè)實(shí)數(shù)乘法 和和2個(gè)實(shí)數(shù)加法個(gè)實(shí)數(shù)加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad) 4次實(shí)數(shù)乘法2次實(shí)數(shù)加法 每運(yùn)算一個(gè)X(k)的值，需要進(jìn)行4N次實(shí)數(shù)相乘和 2N+2(N-1)=2(2N-1)次實(shí)數(shù)相加.整個(gè)DFT運(yùn)算量為： 4N2次實(shí)數(shù)相乘和次實(shí)數(shù)相乘和2N(2N-1)次實(shí)數(shù)相加次實(shí)數(shù)相加.由此看出： 直接計(jì)算DFT時(shí)，乘法次數(shù)與加法次數(shù)都是和N2成比例的。當(dāng)N很

5、大時(shí)，所需工作量非?？捎^。)Re)(ImIm)(Re) Im)(ImRe)(Re)(10knNknNNnknNknNWnxWnxjWnxWnxkX例子 例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要： N2=220=1048576次，即一百多萬次的復(fù)乘運(yùn)算這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理(如雷達(dá)信號(hào)處理)來講，它對(duì)計(jì)算速度有十分苛刻的要求-迫切需要改進(jìn)DFT的計(jì)算方法，以減少總的運(yùn)算次數(shù)。 例2：石油勘探，24道記錄，每道波形記錄長(zhǎng)度5秒，若每秒抽樣500點(diǎn)/秒，每道總抽樣點(diǎn)數(shù)=500*5=2500點(diǎn)24道總抽樣點(diǎn)數(shù)=24*2500=6萬點(diǎn)DFT運(yùn)算時(shí)間=N2=(60000)2=36*108次二、改善D

6、FT運(yùn)算效率的基本途徑利用DFT運(yùn)算的系數(shù) 的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率。1. 合并法：合并DFT運(yùn)算中的某些項(xiàng)。2. 分解法： 將長(zhǎng)序列DFT利用對(duì)稱性和周期性，分解為短序列DFT。knNW利用DFT運(yùn)算的系數(shù) 的固有對(duì)稱性 和周期性，改善DFT的運(yùn)算效率knNWknNW的對(duì)稱性：*()()knnkN n kNNNWWWknNW的周期性：()()knn N kn N kNNNWWW1)()(22kjkNNjkNNeeW因?yàn)椋?, 1 , 0Nk1)()(22njNnNjNnNeeW1, 1 , 0Nn由此可得出：nkNknNNkNnNWWW)()()(1sincos)(222/

7、jeWNNjNN2()NkkNNWW例子 例:1454)54(494WWWW1898178258WWWW利用以上特性,得到改進(jìn)DFT直接算法的方法.(1) 合并法： 合并DFT運(yùn)算中的有些項(xiàng) 對(duì)虛實(shí)部而言 所以帶入DFT中：*()()knk NnNNWWknNnNkNWWReRe)(knNnNkNWWImIm)(分解成虛實(shí)部1010Re)(ImIm)(ReIm)(ImRe)(Re)(NnnkNnkNNnnkNnkNWnxWnxjWnxWnxkX展開：1010Im)Re(Im)(Re)()(NnnkNnkNNnnkNWjWnxjnxWnxkX代入DFT中nkNnNkNnkNWnNxnxWnNxW

8、nxRe)(Re)(ReRe)(ReRe)(Re)(nkNnNkNnkNWnNxnxWnNxWnxIm)(Im)(ImIm)(ImIm)(Im)(knNnNkNWWReRe)(knNnNkNWWImIm)(根據(jù)：有：合并有些項(xiàng) 由此找出其它各項(xiàng)的類似歸并方法：乘法次數(shù)可以減少一半。例：1545) 15(515Re)4(Re) 1 (ReRe)4(Re) 1 (Re) 15 (ReRe) 1 (ReWxxWxxWxWx結(jié)論2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT-思路 因?yàn)镈FT的運(yùn)算量與的運(yùn)算量與N2成正比的成正比的 如果一個(gè)大點(diǎn)數(shù)N的DFT能分解為若干小點(diǎn)數(shù)DFT的組合，則顯然

9、可以達(dá)到減少運(yùn)算工作量的效果。2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT-方法22)()()(NNNkXkXkX把N點(diǎn)數(shù)據(jù)分成二半：其運(yùn)算量為：2)2(N2)2(N2N再分二半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N這樣一直分下去，剩下兩點(diǎn)的變換兩點(diǎn)的變換。2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT-結(jié)論 快速付里時(shí)變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來的，并產(chǎn)生了多種FFT算法，其基本上可分成兩大類： 按抽取方法分： 時(shí)間抽取法(DIT);頻率抽取法(DIF) 按“基數(shù)”分：基-2FFT算法；基-

10、4FFT算 法；混合基FFT算法；分裂基FFT算法 其它方法：線性調(diào)頻Z變換(CZT法)按時(shí)間抽取的基-2 FFT算法Decimation-in-Time(DIT)(Coolkey-Tukey)一、算法原理 設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基2按時(shí)間抽取的FFT算法。也稱為Coolkey-Tukey算法。 其中基數(shù)2-N=2M，M為整數(shù).若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長(zhǎng)）使其達(dá)到 N=2M例子 設(shè)一序列設(shè)一序列x(n)的長(zhǎng)度為的長(zhǎng)度為L(zhǎng)=9,應(yīng)加零補(bǔ)長(zhǎng)為應(yīng)加零補(bǔ)長(zhǎng)為 N=24=16 應(yīng)補(bǔ)應(yīng)補(bǔ)7個(gè)零值。個(gè)零值。 0 1

11、2 3 4 5 6 7 8 9 10 11 12 13 14 15 nx(n)二、算法步驟1.分組，變量置換分組，變量置換DFT變換：10)()(NnknNWnxkX0,1kN先將x(n)按n的奇偶分為兩 組，作變量置換:當(dāng)n=偶數(shù)時(shí)，令n=2r;當(dāng)n=奇數(shù)時(shí)，令n=2r+1;得到：x(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 則可得其DFT為兩部分：前半部分前半部分：后半部分后半部分：( )1( )2( )kNX kX kW Xk0,/2 1kN(/2)1( )2( )kNX kNX kW Xk2.代入DFT中)( 2)( 1) 12 ()2 ()()rxDFTr

12、xDFTrxDFTrxDFTnxDFTkX（生成兩個(gè)子序列x(0),x(2)x(2r)偶數(shù)點(diǎn)x(1),x(3)x(2r+1)奇數(shù)點(diǎn)12/, 0Nr代入DFT變換式：/2 1/2 12(21)00/2 1/2 10022221/2/222)(2 )(21)1( )2( )()()rkNNrkrkNNrrNNrrjrjNNkkNNNNNWWX kxr WxrWx rxrWeeWW（3.求出子序列的DFT上式得：/2/2/2 1/2 1120012/2 1/2 111/2/200/2 1/2 122/2/200)( )( )( )( )( )( )(2 )( )( )(20,1/112)NNrrkN

13、NNrkrkNNrrNNrkrrkkNNkNkNrrrNX kx rxrXkW XkXkx r Wxr WXkxrWWxrWWkWN（其中：12/, 0Nk4.結(jié)論 一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：12)( )( )0,1/21kNX kXkW XkNDFTkN（又合成 點(diǎn)中的前半部分 再應(yīng)用W系數(shù)的周期性，求出用X1(k),X2(k)表達(dá)的后半部的X(k+N/2)的值。5.求出后半部的表示式/2 1/2 1(/2)11/21/2100/2 1/2 1(/2)22/22(/2)/2/2/2200()( )( )( )2()( )(

14、)( )2rkr kNNr NkrkNNrrNNr NkrkNNrNNNrNXkx r Wx r WX kNXkx r Wx r WX kWW看出：后半部的k值所對(duì)應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對(duì)應(yīng)的X1(k),X2(k)的值。/2)12/2( )( )( )NkNkkNNkNNNWWX kX kW X kWW（又后半部分：6.結(jié)論2頻域中的N個(gè)點(diǎn)頻率成分為：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：結(jié)論：只要求出（0N/2-1）區(qū)間內(nèi)的各個(gè)整數(shù)k值所對(duì)應(yīng)的X1(k),X2(k)值，即可以求出(0N-1)整個(gè)區(qū)間內(nèi)全部

15、X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。7.結(jié)論3由于N=2M，因此N/2仍為偶數(shù)，可以依照上面方法進(jìn)一步把每個(gè)N/2點(diǎn)子序列，再按輸入n的奇偶分解為兩個(gè)N/4點(diǎn)的子序列，按這種方法不斷劃分下去，直到最后剩下的是2點(diǎn)DFT，兩點(diǎn)DFT實(shí)際上只是加減運(yùn)算加減運(yùn)算。) 1 ()0() 1 () 1 ()0()0(2,)()(10 xxXxxXNWnxkXNnknN時(shí)三、蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu)也即為蝶式信號(hào)流圖上面頻域頻域中前/后半部分表示式可以用蝶形信號(hào)流圖表示。X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作圖要素：作圖要素：(1)左邊兩路為輸入左邊兩路為輸入

16、(2)右邊兩路為輸出右邊兩路為輸出(3)中間以一個(gè)小圓表示加、中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸減運(yùn)算（右上路為相加輸出、右下路為相減輸出出、右下路為相減輸出)(4)如果在某一支路上信號(hào)需要進(jìn)行如果在某一支路上信號(hào)需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。將相乘的系數(shù)標(biāo)在箭頭旁。(5)當(dāng)支路上沒有箭頭及系當(dāng)支路上沒有箭頭及系數(shù)時(shí)，則該支路的傳輸比數(shù)時(shí)，則該支路的傳輸比為為1。例子：求 N=23=8點(diǎn)FFT變換 （1）先按）先按N=8-N/2=4，做做4點(diǎn)的點(diǎn)的DFT：)()() 2/()()()(2121kXWkXNkXkXWkX

17、kXkNkN12/, 0Nk先將N=8DFT分解成2個(gè)4點(diǎn)DFT：可知：時(shí)域上：x(0),x(2),x(4),x(6)為偶子序列 x(1),x(3),x(5),x(7)為奇子序列 頻域上：X(0)X(3)，由X(k)給出 X(4)X(7),由X(k+N/2)給出(a)比較N=8點(diǎn)直接DFT與分解2個(gè)4點(diǎn)DFT的FFT運(yùn)算量N=8點(diǎn)的直接直接DFT的計(jì)算量為：N2次(64次）復(fù)數(shù)相乘,N(N-1)次(8(8-1)=56次)復(fù)數(shù)相加.共計(jì)120次。（b)求 一個(gè)蝶形結(jié)需要的運(yùn)算量要運(yùn)算一個(gè)蝶形結(jié)，需要一次乘法 ， 兩次加法。)(2kXWkN)()() 2/()()()(2121kXWkXNkXkX

18、WkXkXkNkN（c）分解為兩個(gè)N/2=4點(diǎn)的DFT的運(yùn)算量分解2個(gè)N/2點(diǎn)（4點(diǎn)）的DFT：) 12 ()2 ()rxDFTrxDFTkX（偶數(shù)其復(fù)數(shù)相乘為復(fù)數(shù)相加為奇數(shù)其復(fù)數(shù)相乘為復(fù)數(shù)相加為22）（N）（122NN22）（N）（122NN次。共計(jì)為次，（次，復(fù)數(shù)相加為復(fù)數(shù)相乘為5624) 123222NNN(d)用2個(gè)4點(diǎn)來求N=8點(diǎn)的FFT所需的運(yùn)算量再將N/2點(diǎn)（4點(diǎn)）合成N點(diǎn)(8點(diǎn))DFT時(shí)，需要進(jìn)行N/2個(gè)蝶形運(yùn)算)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk還需N/2次（4次）乘法 及 次(8次）加法運(yùn)算。22N)(2kXWkN計(jì)算

19、量。分解就可以節(jié)省約一半次。看出僅做一次共計(jì)為次復(fù)數(shù)加法次復(fù)數(shù)乘法）共需求點(diǎn)所以68,322) 12(,36221(22)(8222NNNNNNNNNkXFFT(e)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖 4點(diǎn)DFTx(0)x(2)x(4)x(6)4點(diǎn)DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶數(shù)序列奇數(shù)序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXW

20、XXXWXXXWXXX）（）（）（）（如：X(4)X(7)同理x1(r)x2(r)(2)N/2(4點(diǎn))-N/4(2點(diǎn))FFT(a)先將先將4點(diǎn)分解成點(diǎn)分解成2點(diǎn)的點(diǎn)的DFT： 因?yàn)?點(diǎn)DFT還是比較麻煩，所以再繼續(xù)分解。 若將N/2(4點(diǎn))子序列按奇/偶分解成兩個(gè)N/4點(diǎn)（2點(diǎn)）子序列。即對(duì)將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)（2點(diǎn)）點(diǎn)的子序列。奇序列、偶序列、) 6() 2() 4() 0(: )(1xxxxrx奇序列、偶序列、同理：)7() 3 () 5 () 1 (: )(2xxxxrx1014012()()2(4131，），在此（）奇序列（）偶序列若設(shè)：LNLLXLxLxL

21、x1014012()()2(5252，），在此（）奇序列（）偶序列同理：LNLLXLxLxLx(b)求2點(diǎn)的DFT11/4 1/4 12(21)11/21/2003/2413/24225/2625/26( )( )(2 )(21)( )( )01/4)( )( )( )( )( )( )(/4)( )DFTNNLkLkNNLLkNkNkNkNx rX kX kxL WxLWXLWXLLX kNXLWXLx rx kXLWXLx kNXLWXL 可分解為：（其中，同理： （同樣，也可分解為：）（c)一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X

22、4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(41431404314143140431XWXXXWXXXWXXXWXX其中（d)另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(61452604526145260452XWXXXWXXXWX

23、XXWXX其中同理：(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT(a)求2個(gè)一點(diǎn)的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，則這里用到對(duì)稱性這是一蝶形結(jié)代入上面流圖可知： 最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。(b)2個(gè)1點(diǎn)的DFT蝶形流圖 1點(diǎn)DFTx(0)1點(diǎn)DFTx(

24、4)X3(0)X3(1)02W進(jìn)一步簡(jiǎn)化為蝶形流圖：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋轉(zhuǎn)因子，共有m=0m=1m=2四、FFT算法中一些概念 （1）“級(jí)級(jí)”概念概念 將N 點(diǎn)DFT先分成兩個(gè)N/2點(diǎn)DFT，再是四個(gè)

25、N/4點(diǎn)DFT直至N/2個(gè)兩點(diǎn)DFT.每分一次稱為“一”級(jí)運(yùn)算。 因?yàn)镹=2M所以N點(diǎn)DFT可分成M級(jí) 如上圖所示依次m=0,m=1.M-1共M級(jí)（2）“組組”概念概念 每一級(jí)都有N/2個(gè)蝶形單元，例如：N=8,則每級(jí)都有4個(gè)蝶形單元。每一級(jí)的N/2個(gè)蝶形單元可以分成若干組，每一組具有相同的結(jié)構(gòu)，相同的 因子分布，第m級(jí)的組數(shù)為：rNW12mN例：N=8=23，分3級(jí)。m=0級(jí),分成四組,每組系數(shù)為m=1級(jí),分成二組,每組系數(shù)為m=2級(jí),分成一組,每組系數(shù)為080204/WWWN28082012/02/,WWWWWWNNNN382818083210,WWWWWWWWNNNN(3) 因子的分布r

26、NW121 , 0,3 , 2 , 102101001238281808828081404408022mkkkkkWmWWWWkWmWWWWkWmWWkWmm級(jí)的系數(shù)為看出：第，級(jí)，級(jí)，級(jí)，由上可知：結(jié)論：每由后向前（結(jié)論：每由后向前（m由由M-1-0級(jí)）推進(jìn)一級(jí)）推進(jìn)一級(jí)，則此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。級(jí)，則此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。（4）按時(shí)間抽取法2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)4點(diǎn)DFT兩個(gè)4點(diǎn)DFT兩個(gè)N/2點(diǎn)DFTX1(k).X2(k)X(k) 由于每一步分

27、解都是基于在每級(jí)按輸入時(shí)間序列的次序是屬于偶數(shù)還是奇數(shù)來分解為兩個(gè)更短的序列，所以稱為“按時(shí)間抽取法”.x(n)五、按時(shí)間抽取的FFT算法與直接計(jì)算DFT運(yùn)算量的比較 由前面介紹的按時(shí)間抽取的FFT運(yùn)算流圖可見： 每級(jí)都由N/2個(gè)蝶形單元構(gòu)成，因此每一級(jí)運(yùn)算都需要N/2次復(fù)乘和N次復(fù)加（每個(gè)結(jié)加減各一次）。這樣（N=2M)M級(jí)運(yùn)算共需要： 復(fù)乘次數(shù)： 復(fù)加次數(shù)： 可以得出如下結(jié)論：按時(shí)間抽取法所需的復(fù)乘數(shù)和復(fù)加數(shù)都是與成正比。而直接計(jì)算DFT時(shí)所需的復(fù)乘數(shù)與復(fù)加數(shù)則都是與N2成正比.(復(fù)乘數(shù)md=N2,復(fù)加數(shù)ad=N(N-1)N2)NFNMNm2log22NFNMNa2logNN2log例子

28、看N=8點(diǎn)和N=1024點(diǎn)時(shí)直接計(jì)算DFT與用基2-按時(shí)間抽取法FFT的運(yùn)算量。4.102102227.224648loglog1020102222NNNNNNN看出：當(dāng)N較大時(shí)，按時(shí)間抽取法將比直接法快一、二個(gè)數(shù)量級(jí)之多。六、按時(shí)間抽取FFT算法的特點(diǎn) 根據(jù)DIT基2-FFT算法原理，能得出任何N=2m點(diǎn)的FFT信號(hào)流圖，并進(jìn)而得出FFT計(jì)算程序流程圖。最后總結(jié)出按時(shí)間抽取法解過程的規(guī)律。 1.原位運(yùn)算（in-place) 2.碼位倒讀規(guī)則1.原位運(yùn)算（in-place) 原位運(yùn)算的結(jié)構(gòu)，可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。 定義：當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一組運(yùn)算的結(jié)果，仍然存放在這同一組存儲(chǔ)

29、器中直到最后輸出。02Wx(0)x(4)X3(0)X3(1)中放在一個(gè)暫存器中放在單元中，將放在單元例：將RWAxAx08) 1 ()4()0()0(單元送回單元送回將) 1 ()4()0()0()4()0(0808AxWxAxWx例子 例：N=8 FFT運(yùn)算,輸入:x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(

30、4)=x(4)A(5)=x(5)A(6)=x(6)A(7)=x(7)180818084,32,1WRWRWRWR暫存器R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位運(yùn)算結(jié)構(gòu)運(yùn)算后，A(0)A(7)正好順序存放X(0)X(7),可以直接順序輸出。2.碼位倒讀規(guī)則 我們從輸入序列的序號(hào)及整序規(guī)律得到碼位倒讀規(guī)則。由N=8蝶形圖看出：原位計(jì)算時(shí)，F(xiàn)FT輸出的X(k)的次序正好是順序排列的，即X(0)X(7),但輸入x(n)都不能按自然順序存入到存儲(chǔ)單元中，而是按x(0),x(4),x(2), x(6).的順序存入存儲(chǔ)單元即為亂序輸入亂序輸入，順序輸出順序輸出。這種順序看起來相當(dāng)雜亂，然

31、而它是有規(guī)律的。即碼位倒讀規(guī)則。例子以N=8為例：01234567000001010011100101110111自然順序二進(jìn)制碼表示碼位倒讀碼位倒置順序00010001011000110101111104261537看出：碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。整序重排子程序具體執(zhí)行時(shí)，只須將1與4對(duì)調(diào)送入，3與6對(duì)調(diào)送入，而0，2，5，7不變，僅需要一個(gè)中間存儲(chǔ)單元。n01234567n04261537 在實(shí)際運(yùn)算時(shí)，先按自然順序?qū)⑤斎胄蛄写嫒氪鎯?chǔ)單元，再通過變址運(yùn)算將自然順序變換成按時(shí)間抽取的FFT算法要求的順序。變址的過程可以用程序安排加以實(shí)現(xiàn)-稱為“整序”或“重排”（采用碼位倒

32、讀）且注意：(1)當(dāng)n=n時(shí)，數(shù)據(jù)不必調(diào)換；(2)當(dāng)nn時(shí)，必須將原來存放數(shù)據(jù)x(n)送入暫存器R，再將x(n)送入x(n),R中內(nèi)容送x(n).進(jìn)行數(shù)據(jù)對(duì)調(diào)。(3)為了避免再次考慮前面已調(diào)換過的數(shù)據(jù)，保證調(diào)換只進(jìn)行一次，否則又變回原狀。nn時(shí)，調(diào)換。七、按時(shí)間抽取的FFT算法的若干變體1.思路思路 對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連續(xù)的支路及其傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，最后所得結(jié)果都是x(n)的離散付里葉變換的正確結(jié)果。只是數(shù)據(jù)的提取和存放的次序不同而已。(2)輸入是自然順序而輸出是亂序?qū)⒃戎信cx(4)水平相鄰的所有節(jié)點(diǎn)跟x(1)水平相鄰的所有節(jié)點(diǎn)位置對(duì)調(diào)；將原

33、先中與x(6)水平相鄰的所有節(jié)點(diǎn)跟x(3)水平相鄰的所有節(jié)點(diǎn)位置對(duì)調(diào)，其余諸節(jié)點(diǎn)保持不變，則可得：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(3)X(5)X(7)它與輸入是亂序，輸出順序比較，看出：相同點(diǎn)：運(yùn)算量一樣；不同點(diǎn)：第一是數(shù)據(jù)存入方式不同；第二是取用系數(shù)的順序不同。(2)輸入和輸出都是自然順序?qū)斎胱匀豁樞?，輸出亂序的第二級(jí)，第三級(jí)節(jié)點(diǎn)作調(diào)整，可得輸入輸出都是順序，無需數(shù)據(jù)重排：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（1）它失掉了“

34、原位運(yùn)算”的性質(zhì)。（2）為了變換N點(diǎn)數(shù)據(jù)，至少需要2N個(gè)復(fù)數(shù)單元。在內(nèi)存比較緊張時(shí)，而對(duì)輸入數(shù)據(jù)整序并不困難時(shí)一般不用。為了爭(zhēng)取速度，才采取這種變體。基-2按頻率抽取的FFT算法Decimation-in-Frequency(DIF)(Sander-Tukey)一、算法原理 設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列的頻域的輸出序列X(k)(也是M點(diǎn)序列，按其頻域頻域順序的奇偶分解奇偶分解為越來越短的子序列，稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。二、算法步驟1.分組分組DFT變換：10)()(NnknNWnxkX1,0Nk已證明頻域上X(k)按k的奇偶分為兩組

35、，在時(shí)域上x(n)按n的順序分前后兩部分，現(xiàn)將輸入x(n)按n的順序分前后兩部分:前半子序列x(n),0nN/2-1;后半子序列x(n+N/2),0nN/2-1;例：N=8時(shí)，前半序列為：x(0),x(1),x(2),x(3); 后半序列為： x(4),x(5),x(6),x(7); 則由定義輸出（求DFT）2.代入DFT中112()2001122()200122022222)( ) ( )()2( )()2 ( )()211NNNnknknkNNNnnNNNnknkNNnnNNknkNNnNkNNjkkNj kNNNkNNX kx n Wx n Wx nWNx n Wx nWNx nx nW

36、WkWWeekW（偶數(shù)時(shí)又奇數(shù)時(shí)3. 變量置換變量置換-1）又代入令，令分偶數(shù)時(shí)，頻率的偶數(shù)部當(dāng)置換分成兩部分，進(jìn)行變量的奇偶將按2/2/2222/2212/012/02(12, 1 , 0)2()() 2(216 , 4 , 2 , 0)2()()(12, 1 , 02, 1)(nkNnkNjnkNjnkNnkNnkNNnnkNNnkNNWeeWWNkWNnxnxkXkkNkWNnxnxkXNkkkWkkXk12/, 0Nk一半。點(diǎn)，所以其運(yùn)算量降低序列只有由于求得。（序列的可以通過的偶數(shù)部分的頻域可見：（則設(shè)一個(gè)新序列：后一半序列前一半序列2)()()()(12, 1 , 0) )() 2

37、(122 , 1 , 0),2()()()()(12, 1 , 0)2()() 2(11112/12/0112/12/0NnxkDFTXnxkXnxNkkXWnxkXNnNnxnxnxnxnxNkWNnxnxkXnkNNnnkNNn）又代入令，令分奇數(shù)時(shí)，頻率的奇數(shù)部同理：當(dāng)）（2/2/2222/21212/012/02(12, 1 , 0)2()() 12(1217 , 5 , 3 , 1)2()()(12, 1 , 012, 1nkNnkNjnkNjnkNnkNknNNnnkNNnkNNWeeWWNkWNnxnxkXkkNkWNnxnxkXNkkkWk一半。點(diǎn)，所以其運(yùn)算量降低序列只有由于

38、求得。（序列的可以通過的奇數(shù)部分的頻域可見：（則設(shè)一個(gè)新序列：后一半序列前一半序列2)()()()(12, 1 , 0) )() 12(122 , 1 , 0,)2()()()()(12, 1 , 0)2()() 12(22122/12/0222/12/0NnxkDFTXnxkXnxNkkXWnxkXNnWNnxnxnxnxnxNkWWNnxnxkXnkNNnnNnkNnNNn4.結(jié)論 一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：DFTNNkkXkXkXkkkkNkkXkXNNDFTNkXkXkX點(diǎn)又合成分別代入再用，即先求出點(diǎn)點(diǎn)點(diǎn)1, 1 ,

39、 0,) 12() 2()(12, 212/1 , 0) () (2/2/) 12() 2()(2121可見：如此分解，直至分到2點(diǎn)的DFT為止。12, 1 , 0)2()()() (12, 1 , 0)2()()() (2/12/02/12/0222/12/02/12/011NkWWNnxnxWnxkXNkWNnxnxWnxkXnkNNnnNnkNNnnkNNnnkNNn三、蝶形流圖表示蝶形單元：時(shí)域時(shí)域中，前后半部表示式用蝶形結(jié)表示。x(n)x(n+N/2)nNW)() 2/()(1nxNnxnx)()2/()(2nxWNnxnxnN與時(shí)間抽取法的推演過程一樣，由于N=2L,N/2仍為偶數(shù)

40、，所以可以將N/2點(diǎn)DFT的輸出X(k)再分為偶數(shù)組和奇數(shù)組，這樣就將一個(gè)N/2點(diǎn)的DFT分成兩個(gè)N/4點(diǎn)DFT的輸入，也是將N/2點(diǎn)的DFT的輸入上、下對(duì)半分后通過蝶形運(yùn)算而形成，直至最后為2點(diǎn)DFT。例子：求 N=23=8點(diǎn)DIF （1）先按）先按N=8-N/2=4，做做4點(diǎn)的點(diǎn)的DIF：nNWNnxnxnxNnxnxnx)2()()()2()()(21先將N=8DFT分解成2個(gè)4點(diǎn)DFT：可知：時(shí)域上：x(0),x(1),x(2),x(3)為前半序列 x(4),x(5),x(6),x(7)為后半序列產(chǎn)生新的子序列： x1(n)、 x2(n) 頻域上：X(0),X(2),X(4),X(6)

41、由x1(n)給出 X(1),X(3),X(5),X(7),由x2(n)給出將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖 4點(diǎn)DFTx(0)x(1)x(2)x(3)4點(diǎn)DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列nNnNnNnNWxxxWxxxWxxxWxxxxxxxxxxxxxxx)7 () 3 (3,)6 () 2(2,)5 () 1 (1,)4() 0 (0) 7 () 3 (3),6 () 2(2),5 () 1 (1),4() 0 (022221111）（）（）（）（）（）（）（）（如：08W18

42、W28W38Wx1(n)x2(n)X2(k)(2)N/2(4點(diǎn))-N/4(2點(diǎn))FFT(a)先將先將4點(diǎn)分解成點(diǎn)分解成2點(diǎn)的點(diǎn)的DIF： 因?yàn)?點(diǎn)DIF還是比較麻煩，所以再繼續(xù)分解。后半部分序列、前半部分序列、) 3 () 2() 1 () 0(: )(11111xxxxnx10140)2()()()2()(411311，），在此（）（若設(shè)：LNLLxWNnxnxLxNnxnxnN后半部分序列、前半部分序列、同理：) 3 () 2() 1 () 0(: )(22222xxxxnx10140)2()()()2()(622522，），在此（）（同理：LNLLxWNnxnxLxNnxnxnN（b)一

43、個(gè)2點(diǎn)的DIF蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)08W28W) 3 () 1 () 1 (,) 2() 0() 0(113113xxxxxx其中(c)另一個(gè)2點(diǎn)的DIF蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)08W28W(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT(a)求2個(gè)一點(diǎn)的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4

44、()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，則這里用到對(duì)稱性這是一蝶形結(jié)代入上面流圖可知： 最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x3(0)、x3(1)為例。(b)2個(gè)1點(diǎn)的DFT蝶形流圖 1點(diǎn)DFTx3(0)1點(diǎn)DFTx3(1)X(0)X(4)02W進(jìn)一步簡(jiǎn)化為蝶形流圖：02WX(0)X(4)x3(0)x3(1)(4)一個(gè)完整N=8的按頻率抽取FFT的運(yùn)算流圖 x(0)x(1)x(2)x(3)x(4)x(5

45、)x(6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW其中旋轉(zhuǎn)因子，共有m=0m=1m=2(5)DIF的特點(diǎn)(a)輸入自然順序，輸出亂序且滿足碼位輸入自然順序，輸出亂序且滿足碼位倒置規(guī)則。倒置規(guī)則。(b)根據(jù)時(shí)域、頻域互換，可知：根據(jù)時(shí)域、頻域互換，可知：輸入亂序，輸出自然順序。輸入亂序，輸出自然順序。（6）DIF與DIT比較 相同之處： （1）DIF與DIT兩種算法均為原位運(yùn)算。 （2）DIF與DIT運(yùn)算量相同。 它們都需要算法是兩種等價(jià)的與次復(fù)加次復(fù)乘FFTDITDIFNa

46、NmNFNF22loglog2（6）DIF與DIT比較2 不同之處：（1）DIF與DIT兩種算法結(jié)構(gòu)倒過來。DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前減法之前。DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后減法之后。IFFT運(yùn)算方法 以上所討論的FFT的運(yùn)算方法同樣可用于IDFT的運(yùn)算，簡(jiǎn)稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導(dǎo)出下列二種利用FFT來計(jì)算FFT的方法。一、利用FFT計(jì)算IFFT的思路 將下列兩式進(jìn)行比較IDFTFFTNWWDFTWnxnxDFTkXWkXNkXIDFTnxnkNnkNNknkNNknkN算法都可以拿來運(yùn)算或頻率抽取抽?。┠敲匆陨嫌懻摰臅r(shí)間（將運(yùn)算結(jié)果都除以改成運(yùn)算中的每個(gè)