離散傅里葉變換

離散傅里葉變換第1頁，共61頁，2023年，2月20日，星期一

快速傅里葉變換(FastFourierTrasform。簡稱FFT)是一種減少DFT計(jì)算時(shí)間的算法。在此出現(xiàn)之前，雖然DFT為離散信號的分析從理論上提供了變換工具，但是很難實(shí)現(xiàn)，因?yàn)橛?jì)算時(shí)間很長。例如，對采樣點(diǎn)N＝l000，DFT算法運(yùn)算量約需200萬次，而FFT僅約需1.5萬次，可見FFT方法大大地提高了運(yùn)算效率。因此，F(xiàn)FT方法于1965年由美國庫利—圖基(J.W.Cooley—J.W.Tukey)首先提出時(shí)，曾被認(rèn)為是信號分析技術(shù)的劃時(shí)代的進(jìn)步。第2頁，共61頁，2023年，2月20日，星期一FFT:FastFourierTransform1965年，JamesW.Cooley和JohnW.Tukey在《計(jì)算數(shù)學(xué)》（《MathematicsofComputation》）上發(fā)表了“一種用機(jī)器計(jì)算復(fù)序列傅立葉級數(shù)的算法（AnalgorithmforthemachinecalculationofcomplexFourierseries）”論文。Dr.JamesW.CooleyJohnW.Tukey(1915-2000)W.M.GENTLEMAN&G.SANDE,FastFourierTransforms-ForFunandProfit,FallJointComputerConferenceAFIPSProc.,1966,v.29,563-578.自此之后，新的算法不斷涌現(xiàn)。一種是對N等于2的整數(shù)次冪的算法，如基2算法，基4算法。另一種是N不等于2的整數(shù)次冪的算法，例如Winagrad算法，素因子算法。第3頁，共61頁，2023年，2月20日，星期一計(jì)算DFT復(fù)數(shù)運(yùn)算量計(jì)算一個(gè)X

(k)值，運(yùn)算量為例k=1則要進(jìn)行N次復(fù)數(shù)乘法，(N-1)次復(fù)數(shù)加法所以，要完成整個(gè)DFT運(yùn)算，其計(jì)算量為：N*N次復(fù)數(shù)相乘，N*(N-1)次復(fù)數(shù)加法第4頁，共61頁，2023年，2月20日，星期一利用的固有對稱性和周期性

改善DFT的運(yùn)算效率的對稱性：的周期性：因?yàn)椋河纱丝傻贸觯旱?頁，共61頁，2023年，2月20日，星期一第6頁，共61頁，2023年，2月20日，星期一時(shí)間抽取基-2FFT算法

Decimation-in-Time(DIT)

第7頁，共61頁，2023年，2月20日，星期一一、算法原理設(shè)輸入序列長度為N=2M(M為正整數(shù)，將該序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基2按時(shí)間抽取的FFT算法。也稱為Coolkey-Tukey算法。其中基數(shù)2----N=2M，M為整數(shù)。若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長）使其達(dá)到N=2M。第8頁，共61頁，2023年，2月20日，星期一二、按時(shí)間抽選的基-2FFT算法1、算法推導(dǎo)設(shè)序列點(diǎn)數(shù)N=2M，M

為整數(shù)。若不滿足，則補(bǔ)零將序列x(n)按n的奇偶分成兩組：N為2的整數(shù)冪的FFT算法稱基-2FFT算法。第9頁，共61頁，2023年，2月20日，星期一則x(n)的DFT:第10頁，共61頁，2023年，2月20日，星期一一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k)，X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：

再應(yīng)用W系數(shù)的周期性，求出用X1(k)，X2(k)表達(dá)的后半部的X(k+N/2)的值。第11頁，共61頁，2023年，2月20日，星期一再利用周期性求X(k)的后半部分第12頁，共61頁，2023年，2月20日，星期一求出后半部的表示式后半部的k值所對應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對應(yīng)的X1(k),X2(k)的值。第13頁，共61頁，2023年，2月20日，星期一頻域中的N個(gè)點(diǎn)頻率成分為：結(jié)論：只要求出（0~N/2-1）區(qū)間內(nèi)的各個(gè)整數(shù)k值所對應(yīng)的X1(k),X2(k)值，即可以求出(0~N-1)整個(gè)區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。第14頁，共61頁，2023年，2月20日，星期一由于N=2^L，因此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)算。第15頁，共61頁，2023年，2月20日，星期一例子：求N=23=8點(diǎn)FFT變換

（1）先按N=8-->N/2=4，做4點(diǎn)的DFT：先將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)給出第16頁，共61頁，2023年，2月20日，星期一2、蝶形結(jié)即蝶式計(jì)算結(jié)構(gòu)也即為蝶式信號流圖上面頻域中前/后半部分表示式可以用蝶形信號流圖表示。X1(k)X2(k)作圖要素：(1)左邊兩路為輸入(2)右邊兩路為輸出(3)中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸出、右下路為相減輸出)(4)如果在某一支路上信號需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。(5)當(dāng)支路上沒有箭頭及系數(shù)時(shí)，則該支路的傳輸比為1。第17頁，共61頁，2023年，2月20日，星期一將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號流圖

X(4)~X(7)同學(xué)們自已寫4點(diǎn)DFTx(0)x(2)x(4)x(6)4點(diǎn)DFTx(1)x(3)x(5)x(7)X(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ù)序列x1(r)x2(r)第18頁，共61頁，2023年，2月20日，星期一(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT

a

先將4點(diǎn)分解成2點(diǎn)的DFT：

因?yàn)?點(diǎn)DFT還是比較麻煩，所以再繼續(xù)分解。若將N/2(4點(diǎn))子序列按奇/偶分解成兩個(gè)N/4點(diǎn)（2點(diǎn)）子序列。即對將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)（2點(diǎn)）點(diǎn)的子序列。第19頁，共61頁，2023年，2月20日，星期一b求2點(diǎn)的DFT第20頁，共61頁，2023年，2月20日，星期一c一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)第21頁，共61頁，2023年，2月20日，星期一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)同理：第22頁，共61頁，2023年，2月20日，星期一(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT

a

求2個(gè)一點(diǎn)的DFT

最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。第23頁，共61頁，2023年，2月20日，星期一b2個(gè)1點(diǎn)的DFT蝶形流圖

1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)進(jìn)一步簡化為蝶形流圖：X3(0)X3(1)x(0)x(4)第24頁，共61頁，2023年，2月20日，星期一(4)一個(gè)完整N=8的按時(shí)間抽取FFT的運(yùn)算流圖

x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)m=0m=1m=2x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(1)x6(0)第25頁，共61頁，2023年，2月20日，星期一3按時(shí)間抽取FFT算法的特點(diǎn)原位運(yùn)算（in-place)碼位倒序規(guī)則第26頁，共61頁，2023年，2月20日，星期一算法特點(diǎn)原位計(jì)算m表示第m級迭代，k，j表示數(shù)據(jù)所在的行數(shù)第27頁，共61頁，2023年，2月20日，星期一例：N=8FFT運(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(4)=x(4)A(5)=x(5)A(6)=x(6)A(7)=x(7)R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位運(yùn)算結(jié)構(gòu)運(yùn)算后，A(0)…A(7)正好順序存放X(0)…X(7),可以直接順序輸出。第28頁，共61頁，2023年，2月20日，星期一

碼位倒序規(guī)則我們從輸入序列的序號及整序規(guī)律得到碼位倒讀規(guī)則。由N=8蝶形圖看出：原位計(jì)算時(shí)，F(xiàn)FT輸出的X(k)的次序正好是順序排列的，即X(0)…X(7),但輸入x(n)都不能按自然順序存入到存儲單元中，而是按x(0),x(4),x(2),x(6)….的順序存入存儲單元即為亂序輸入，順序輸出。這種順序看起來相當(dāng)雜亂，然而它是有規(guī)律的。即碼位倒讀規(guī)則。第29頁，共61頁，2023年，2月20日，星期一例子以N=8為例：01234567000001010011100101110111自然順序二進(jìn)制碼表示碼位倒讀碼位倒置順序00010001011000110101111104261537看出：碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。第30頁，共61頁，2023年，2月20日，星期一倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111n0n1n200011011001101第31頁，共61頁，2023年，2月20日，星期一1.計(jì)算速度當(dāng)N=2L時(shí)，共有L級蝶形，每級N/2個(gè)蝶形，每個(gè)蝶形有1次復(fù)數(shù)乘法2次復(fù)數(shù)加法。復(fù)數(shù)乘法：復(fù)數(shù)加法：比較DFT

第32頁，共61頁，2023年，2月20日，星期一第33頁，共61頁，2023年，2月20日，星期一復(fù)乘次數(shù)NN2第34頁，共61頁，2023年，2月20日，星期一如N=512、1024和8192時(shí)，DFT的復(fù)數(shù)乘法運(yùn)算

N2=5122=218=262144（26萬次）

N2=10242=220=1048576（105萬次）

N2=81922=226=67108864（6千7百萬次）對于大的N，在實(shí)際中是不能接受的，無法“實(shí)時(shí)”應(yīng)用DFT。Cooley與Tukey提出的FFT算法，大大減少了計(jì)算次數(shù)。如N=512時(shí)，F(xiàn)FT的乘法次數(shù)約為2000次，提高了約128倍，而且簡化隨N的增加而巨增，因而，用數(shù)值方法計(jì)算頻譜得到實(shí)際應(yīng)用。第35頁，共61頁，2023年，2月20日，星期一頻率抽取基-2FFT算法

Decimation-in-Frequency(DIF)

第36頁，共61頁，2023年，2月20日，星期一

算法原理設(shè)序列點(diǎn)數(shù)N=2M，M為整數(shù)。將X(k)按k的奇偶分組前，先將輸入x(n)按n的順序分成前后兩半。第37頁，共61頁，2023年，2月20日，星期一第38頁，共61頁，2023年，2月20日，星期一

按k的奇偶將X(k)分成兩部分：第39頁，共61頁，2023年，2月20日，星期一令則X(2r)和X(2r+1)分別是x1(n)和x2(n)的N/2點(diǎn)DFT，記為X1(k)和X2(k)第40頁，共61頁，2023年，2月20日，星期一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(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)第41頁，共61頁，2023年，2月20日，星期一N/2仍為偶數(shù)，進(jìn)一步分解：N/2N/4第42頁，共61頁，2023年，2月20日，星期一x3(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)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)第43頁，共61頁，2023年，2月20日，星期一同理：其中：第44頁，共61頁，2023年，2月20日，星期一第45頁，共61頁，2023年，2月20日，星期一逐級分解，直到2點(diǎn)DFT當(dāng)N=8時(shí)，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,1第46頁，共61頁，2023年，2月20日，星期一x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)第47頁，共61頁，2023年，2月20日，星期一DIF與DIT比較1相同之處

DIF與DIT兩種算法均為原位運(yùn)算。

DIF與DIT運(yùn)算量相同。運(yùn)算量第48頁，共61頁，2023年，2月20日，星期一不同之處DIF與DIT兩種算法結(jié)構(gòu)倒過來

DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。

DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。蝶形結(jié)不同

DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。

DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。DIF與DIT比較2第49頁，共61頁，2023年，2月20日，星期一快速傅