DSPFFT深入淺出詳細(xì)講解快速傅里葉變換

DSPFFT深入淺出詳細(xì)講解快速傅里葉變換DSPFFT深入淺出詳細(xì)講解快速傅里葉變換1第一節(jié)

引言第一節(jié)

引言2一、快速付里葉變換FFT有限長(zhǎng)序列通過(guò)離散傅里葉變換(DFT)將其頻域離散化成有限長(zhǎng)序列.但其計(jì)算量太大(與N的平方成正比〕,很難實(shí)時(shí)地處理問(wèn)題,因此引出了快速傅里葉變換(FFT).FFT并不是一種新的變換形式,它只是DFT的一種快速算法.并且根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法.FFT在離散傅里葉反變換、線性卷積和線性相關(guān)等方面也有重要應(yīng)用.。一、快速付里葉變換FFT有限長(zhǎng)序列通過(guò)離散傅里葉變換(DF3二、FFT產(chǎn)生故事當(dāng)時(shí)加文(Garwin)在自已的研究中極需要一個(gè)計(jì)算付里葉變換的快速方法。他注意到圖基(J.W.Turkey)正在寫(xiě)有關(guān)付里葉變換的文章，因此詳細(xì)詢(xún)問(wèn)了圖基關(guān)于計(jì)算付里葉變換的技術(shù)知識(shí)。圖基概括地對(duì)加文介紹了一種方法，它本質(zhì)上就是后來(lái)的著名的庫(kù)利(CooleyJ.W)圖基算法。在加文的迫切要求下，庫(kù)利很快設(shè)計(jì)出一個(gè)計(jì)算機(jī)程序。1965年庫(kù)利--圖基在<計(jì)算數(shù)學(xué)>、MathematicofComputation雜志上發(fā)表了著名的“機(jī)器計(jì)算付里級(jí)數(shù)的一種算法〞文章，提出一種快速計(jì)算DFT的方法和計(jì)算機(jī)程序--揭開(kāi)了FFT開(kāi)展史上的第一頁(yè)，促使FFT算法產(chǎn)生原因還有1967年至1968年間FFT的數(shù)字硬件制成，電子數(shù)字計(jì)算機(jī)的條件，使DFT的運(yùn)算大簡(jiǎn)化了。二、FFT產(chǎn)生故事當(dāng)時(shí)加文(Garwin)在自已4三、本章主要內(nèi)容1.直接計(jì)算DFT算法存在的問(wèn)題及改進(jìn)途徑。2.多種DFT算法(時(shí)間抽取算法DIT算法，頻率抽取算法DIF算法，線性調(diào)頻Z變換即CZT法)三、本章主要內(nèi)容1.直接計(jì)算DFT算法存在的問(wèn)題及改進(jìn)途徑。5第二節(jié)

直接計(jì)算DFT算法存在的問(wèn)題及改進(jìn)途徑第二節(jié)

直接計(jì)算DFT算法存在的問(wèn)題及改進(jìn)途徑6一、直接計(jì)算DFT計(jì)算量

問(wèn)題提出：設(shè)有限長(zhǎng)序列x(n),非零值長(zhǎng)度為N,計(jì)算對(duì)x(n)進(jìn)展一次DFT運(yùn)算，共需多大的運(yùn)算工作量?一、直接計(jì)算DFT計(jì)算量

問(wèn)題提出：設(shè)有限長(zhǎng)序列x(n),7其中x(n)為復(fù)數(shù)，也為復(fù)數(shù)所以DFT與IDFT二者計(jì)算量一樣。其中x(n)為復(fù)數(shù)，82.以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ì)算量為：N*N次復(fù)數(shù)相乘和N*(N-1)次復(fù)數(shù)加法2.以DFT為例，計(jì)算DFT復(fù)數(shù)運(yùn)算量計(jì)算一個(gè)X(k)(一個(gè)9復(fù)數(shù)運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間長(zhǎng)。一個(gè)復(fù)數(shù)乘法包括4個(gè)實(shí)數(shù)乘法和2個(gè)實(shí)數(shù)相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)

4次實(shí)數(shù)乘法2次實(shí)數(shù)加法復(fù)數(shù)運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間長(zhǎng)。4次實(shí)數(shù)乘法2次10每運(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ù)相乘和2N(2N-1)次實(shí)數(shù)相加.由此看出：直接計(jì)算DFT時(shí)，乘法次數(shù)與加法次數(shù)都是和N2成比例的。當(dāng)N很大時(shí)，所需工作量非?？捎^。DSPFFT深入淺出詳細(xì)講解快速傅里葉變換11例子例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：N2=220=1048576次，即一百多萬(wàn)次的復(fù)乘運(yùn)算這對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理(如雷達(dá)信號(hào)處理)來(lái)講，它對(duì)計(jì)算速度有非?？量痰囊?->迫切需要改進(jìn)DFT的計(jì)算方法，以減少總的運(yùn)算次數(shù)。例2：石油勘探，24道記錄，每道波形記錄長(zhǎng)度5秒，假設(shè)每秒抽樣500點(diǎn)/秒，每道總抽樣點(diǎn)數(shù)=500*5=2500點(diǎn)24道總抽樣點(diǎn)數(shù)=24*2500=6萬(wàn)點(diǎn)DFT運(yùn)算時(shí)間=N2=(60000)2=36*108次例子例1:當(dāng)N=1024點(diǎn)時(shí)，直接計(jì)算DFT需要：12作業(yè)作業(yè)13二、改善DFT運(yùn)算效率的根本途徑利用DFT運(yùn)算的系數(shù)的固有對(duì)稱(chēng)性和周期性，改善DFT的運(yùn)算效率。1.合并法：合并DFT運(yùn)算中的某些項(xiàng)。3.分解法：將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性，分解為短序列DFT。二、改善DFT運(yùn)算效率的根本途徑利用DFT運(yùn)算的系數(shù)14利用DFT運(yùn)算的系數(shù)的固有對(duì)稱(chēng)性和周期性，改善DFT的運(yùn)算效率的對(duì)稱(chēng)性：的周期性：因?yàn)椋河纱丝傻贸觯豪肈FT運(yùn)算的系數(shù)的固有對(duì)稱(chēng)性和周期性，改15例子例:利用以上特性,得到改進(jìn)DFT直接算法的方法.例子例:利用以上特性,得到改進(jìn)DFT直接算法的方法.16(1)合并法：步驟1分解成虛實(shí)部合并DFT運(yùn)算中的有些項(xiàng)對(duì)虛實(shí)部而言所以帶入DFT中：(1)合并法：步驟1分解成虛實(shí)部合并DFT運(yùn)算中的有些項(xiàng)17(1)合并法：步驟2代入DFT中展開(kāi)：(1)合并法：步驟2代入DFT中展開(kāi)：18(1)合并法：步驟3合并有些項(xiàng)根據(jù)：有：(1)合并法：步驟3合并有些項(xiàng)根據(jù)：有：19(1)合并法：步驟4結(jié)論由此找出其它各項(xiàng)的類(lèi)似歸并方法：乘法次數(shù)可以減少一半。例：(1)合并法：步驟4結(jié)論由此找出其它各項(xiàng)的202、將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT--思路因?yàn)镈FT的運(yùn)算量與N2成正比的假設(shè)一個(gè)大點(diǎn)數(shù)N的DFT能分解為假設(shè)干小點(diǎn)數(shù)DFT的組合，那么顯然可以到達(dá)減少運(yùn)算工作量的效果。2、將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT--思212、將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT--方法把N點(diǎn)數(shù)據(jù)分成二半：其運(yùn)算量為：再分二半：+=+++=這樣一直分下去，剩下兩點(diǎn)的變換。2、將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT--方222、將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT--結(jié)論快速付里時(shí)變換(FFT)就是在此特性根底上開(kāi)展起來(lái)的，并產(chǎn)生了多種FFT算法，其根本上可分成兩大類(lèi)：按抽取方法分：時(shí)間抽取法(DIT);頻率抽取法(DIF)按“基數(shù)〞分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：線性調(diào)頻Z變換(CZT法)2、將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT--結(jié)23第三節(jié)

基--2按時(shí)間抽取的FFT算法Decimation-in-Time(DIT)

(Coolkey-Tukey)第三節(jié)

基--2按時(shí)間抽取的FFT算法Decimation-24一、算法原理設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列按時(shí)間順序的奇偶分解為越來(lái)越短的子序列，稱(chēng)為基2按時(shí)間抽取的FFT算法。也稱(chēng)為Coolkey-Tukey算法。其中基數(shù)2----N=2M，M為整數(shù).假設(shè)不滿(mǎn)足這個(gè)條件，可以人為地加上假設(shè)干零值〔加零補(bǔ)長(zhǎng)〕使其到達(dá)N=2M一、算法原理設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列按25例子設(shè)一序列x(n)的長(zhǎng)度為L(zhǎng)=9,應(yīng)加零補(bǔ)長(zhǎng)為N=24=16

應(yīng)補(bǔ)7個(gè)零值。0123456789101112131415nx(n)例子設(shè)一序列x(n)的長(zhǎng)度為L(zhǎng)=9,應(yīng)加零補(bǔ)長(zhǎng)為026二、算法步驟

1.分組，變量置換DFT變換：先將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=0…N/2-1;那么可得其DFT為兩局部：前半局部：后半局部：二、算法步驟

1.分組，變量置換DFT變換：先將x(n)按n27生成兩個(gè)子序列x(0),x(2)…x(2r)偶數(shù)點(diǎn)x(1),x(3)…x(2r+1)奇數(shù)點(diǎn)代入DFT變換式：生成兩個(gè)子序列x(0),x(2)…x(2r)偶數(shù)點(diǎn)代入DFT28上式得：上式得：29一個(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)的值。一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X230看出：后半部的k值所對(duì)應(yīng)的X1(k),X2(k)那么完全重復(fù)了前半局部的k值所對(duì)應(yīng)的X1(k),X2(k)的值?？闯觯汉蟀氩康膋值所對(duì)應(yīng)的X1(k),X2(k)那么完全重復(fù)31頻域中的N個(gè)點(diǎn)頻率成分為：結(jié)論：只要求出〔0~N/2-1〕區(qū)間內(nèi)的各個(gè)整數(shù)k值所對(duì)應(yīng)的X1(k),X2(k)值，即可以求出(0~N-1)整個(gè)區(qū)間內(nèi)全部X(k)值，這就是FFT能大量節(jié)省計(jì)算的關(guān)鍵。頻域中的N個(gè)點(diǎn)頻率成分為：結(jié)論：只要求出〔0~N/2-1〕區(qū)32由于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)算。由于N=2M，因此N/2仍為偶數(shù)，可以按照上面方法進(jìn)一步把每33三、蝶形結(jié)即蝶式計(jì)算構(gòu)造也即為蝶式信號(hào)流圖上面頻域中前/后半局部表示式可以用蝶形信號(hào)流圖表示。X1(k)X2(k)作圖要素：(1)左邊兩路為輸入(2)右邊兩路為輸出(3)中間以一個(gè)小圓表示加、減運(yùn)算〔右上路為相加輸出、右下路為相減輸出)(4)假設(shè)在某一支路上信號(hào)需要進(jìn)展相乘運(yùn)算，那么在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。(5)當(dāng)支路上沒(méi)有箭頭及系數(shù)時(shí)，那么該支路的傳輸比為1。三、蝶形結(jié)即蝶式計(jì)算構(gòu)造也即為蝶式信號(hào)流圖X1(k)X2(k34例子：求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)給出例子：求N=23=8點(diǎn)FFT變換

〔1〕先按N=8-->35(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次。(a)比較N=8點(diǎn)直接DFT與分解2個(gè)4點(diǎn)DFT的FFT運(yùn)算36〔b)求一個(gè)蝶形結(jié)需要的運(yùn)算量要運(yùn)算一個(gè)蝶形結(jié)，需要一次乘法，兩次加法?！瞓)求一個(gè)蝶形結(jié)需要的運(yùn)算量要運(yùn)算一個(gè)蝶形結(jié)，需要一次乘37〔c〕分解為兩個(gè)N/2=4點(diǎn)的DFT的運(yùn)算量分解2個(gè)N/2點(diǎn)〔4點(diǎn)〕的DFT：偶數(shù)其復(fù)數(shù)相乘為復(fù)數(shù)相加為奇數(shù)其復(fù)數(shù)相乘為復(fù)數(shù)相加為〔c〕分解為兩個(gè)N/2=4點(diǎn)的DFT的運(yùn)算量分解2個(gè)N/2點(diǎn)38(d)用2個(gè)4點(diǎn)來(lái)求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)算還需N/2次〔4次〕乘法及次(8次〕加法運(yùn)算。(d)用2個(gè)4點(diǎn)來(lái)求N=8點(diǎn)的FFT所需的運(yùn)算量再將N/2點(diǎn)39(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)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ù)序列X(4)~X(7)同學(xué)們自已寫(xiě)x1(r)x2(r)(e)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖4點(diǎn)x(040(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還是比較費(fèi)事，所以再繼續(xù)分解。假設(shè)將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)的子序列。(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT

(a)先將441(b)求2點(diǎn)的DFT(b)求2點(diǎn)的DFT42〔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)〔c)一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x43〔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)同理：〔d)另一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)44(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就等于輸入信號(hào)本身，所以?xún)牲c(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。(3)將N/4〔2點(diǎn)〕DFT再分解成2個(gè)1點(diǎn)的DFT

(a)45(b)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFTx(4)X3(0)X3(1)進(jìn)一步簡(jiǎn)化為蝶形流圖：X3(0)X3(1)x(0)x(4)(b)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx(0)1點(diǎn)DFT46(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=2(4)一個(gè)完好N=8的按時(shí)間抽取FFT的運(yùn)算流圖x(0)X47四、FFT算法中一些概念

〔1〕“級(jí)〞概念將N點(diǎn)DFT先分成兩個(gè)N/2點(diǎn)DFT，再是四個(gè)N/4點(diǎn)DFT…直至N/2個(gè)兩點(diǎn)DFT.每分一次稱(chēng)為“一〞級(jí)運(yùn)算。因?yàn)镹=2M所以N點(diǎn)DFT可分成M級(jí)如上圖所示依次m=0,m=1….M-1共M級(jí)四、FFT算法中一些概念

〔1〕“級(jí)〞概念將N點(diǎn)DFT先48〔2〕“組〞概念每一級(jí)都有N/2個(gè)蝶形單元，例如：N=8,那么每級(jí)都有4個(gè)蝶形單元。每一級(jí)的N/2個(gè)蝶形單元可以分成假設(shè)干組，每一組具有一樣的構(gòu)造，一樣的因子分布，第m級(jí)的組數(shù)為：例：N=8=23，分3級(jí)。m=0級(jí),分成四組,每組系數(shù)為m=1級(jí),分成二組,每組系數(shù)為m=2級(jí),分成一組,每組系數(shù)為〔2〕“組〞概念每一級(jí)都有N/2個(gè)蝶形單元，例如：N49(3)因子的分布結(jié)論：每由后向前〔m由M-1-->0級(jí)〕推進(jìn)一級(jí)，那么此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。(3)因子的分布結(jié)論：每由后向前〔m由M-1-->50〔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)由于每一步分解都是基于在每級(jí)按輸入時(shí)間序列的次序是屬于偶數(shù)還是奇數(shù)來(lái)分解為兩個(gè)更短的序列，所以稱(chēng)為“按時(shí)間抽取法〞.x(n)〔4〕按時(shí)間抽取法2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT251五、按時(shí)間抽取的FFT算法與直接計(jì)算DFT運(yùn)算量的比較由前面介紹的按時(shí)間抽取的FFT運(yùn)算流圖可見(jià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)五、按時(shí)間抽取的FFT算法與直接計(jì)算DFT運(yùn)算量的比較由前面52例子看N=8點(diǎn)和N=1024點(diǎn)時(shí)直接計(jì)算DFT與用基2-按時(shí)間抽取法FFT的運(yùn)算量?？闯觯寒?dāng)N較大時(shí)，按時(shí)間抽取法將比直接法快一、二個(gè)數(shù)量級(jí)之多。例子看N=8點(diǎn)和N=1024點(diǎn)時(shí)直接計(jì)算DFT與用基2-按時(shí)53作業(yè)作業(yè)54六、按時(shí)間抽取FFT算法的特點(diǎn)根據(jù)DIT基2-FFT算法原理，能得出任何N=2m點(diǎn)的FFT信號(hào)流圖，并進(jìn)而得出FFT計(jì)算程序流程圖。最后總結(jié)出按時(shí)間抽取法解過(guò)程的規(guī)律。1.原位運(yùn)算〔in-place)六、按時(shí)間抽取FFT算法的特點(diǎn)根據(jù)DIT基2-FFT算法原理551.原位運(yùn)算〔in-place)原位運(yùn)算的構(gòu)造，可以節(jié)省存儲(chǔ)單元，降低設(shè)備本錢(qián)。定義：當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器以后，每一組運(yùn)算的結(jié)果，仍然存放在這同一組存儲(chǔ)器中直到最后輸出。x(0)x(4)X3(0)X3(1)1.原位運(yùn)算〔in-place)原位運(yùn)算的構(gòu)造，可以節(jié)省存儲(chǔ)56例子例：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)算構(gòu)造運(yùn)算后，A(0)…A(7)正好順序存放X(0)…X(7),可以直接順序輸出。例子例：N=8FFT運(yùn)算,輸入:x(0)A(0)A(0)A57我們從輸入序列的序號(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ǔ)單元即為亂序輸入，順序輸出。這種順序看起來(lái)相當(dāng)雜亂，然而它是有規(guī)律的。即碼位倒讀規(guī)那么。我們從輸入序列的序號(hào)及整序規(guī)律得到碼位倒讀規(guī)那么。由N=8蝶58例子以N=8為例：01234567000001010011100101110111自然順序二進(jìn)制碼表示碼位倒讀碼位倒置順序00010001011000110101111104261537看出：碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。例子以N=8為例：0000自然順序二進(jìn)制碼表示碼位倒讀碼位倒59整序重排子程序詳細(xì)執(zhí)行時(shí)，只須將1與4對(duì)調(diào)送入，3與6對(duì)調(diào)送入，而0，2，5，7不變，僅需要一個(gè)中間存儲(chǔ)單元。n01234567n’04261537在實(shí)際運(yùn)算時(shí)，先按自然順序?qū)⑤斎胄蛄写嫒氪鎯?chǔ)單元，再通過(guò)變址運(yùn)算將自然順序變換成按時(shí)間抽取的FFT算法要求的順序。變址的過(guò)程可以用程序安排加以實(shí)現(xiàn)--稱(chēng)為“整序〞或“重排〞〔采用碼位倒讀〕且注意：(1)當(dāng)n=n’時(shí)，數(shù)據(jù)不必調(diào)換；(2)當(dāng)n≠n時(shí)，必須將原來(lái)存放數(shù)據(jù)x(n)送入暫存器R，再將x(n’)送入x(n),R中內(nèi)容送x(n’).進(jìn)展數(shù)據(jù)對(duì)調(diào)。(3)為了防止再次考慮前面已調(diào)換過(guò)的數(shù)據(jù)，保證調(diào)換只進(jìn)展一次，否那么又變回原狀。n’>n時(shí)，調(diào)換。整序重排子程序詳細(xì)執(zhí)行時(shí)，只須將1與4對(duì)調(diào)送入，3與6對(duì)調(diào)送60作業(yè)編寫(xiě)N=128點(diǎn)的基2--按時(shí)間抽取的FFT算法。要求用C語(yǔ)言編寫(xiě)，并將輸入數(shù)據(jù)放在文件inputdata.dat中，輸出數(shù)據(jù)放在outputdata.dat文件中。作業(yè)編寫(xiě)N=128點(diǎn)的基2--按時(shí)間抽取的FFT算法。要求用61七、按時(shí)間抽取的FFT算法的假設(shè)干變體

對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連續(xù)的支路及其傳輸系數(shù)不變，那么不管節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，最后所得結(jié)果都是x(n)的離散付里葉變換的正確結(jié)果。只是數(shù)據(jù)的提取和存放的次序不同而已。七、按時(shí)間抽取的FFT算法的假設(shè)干變體

對(duì)于任何流62(2)輸入是自然順序而輸出是亂序?qū)⒃戎信cx(4)程度相鄰的所有節(jié)點(diǎn)跟x(1)程度相鄰的所有節(jié)點(diǎn)位置對(duì)調(diào)；將原先中與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ū)⒃戎信cx(4)程度相鄰的63(2)輸入和輸出都是自然順序?qū)斎胱匀豁樞?，輸出亂序的第二級(jí)，第三級(jí)節(jié)點(diǎn)作調(diào)整，可得輸入輸出都是順序，無(wú)需數(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〕它失掉了“原位運(yùn)算〞的性質(zhì)?！?〕為了變換N點(diǎn)數(shù)據(jù)，至少需要2N個(gè)復(fù)數(shù)單元。在內(nèi)存比較緊張時(shí)，而對(duì)輸入數(shù)據(jù)整序并不困難時(shí)一般不用。為了爭(zhēng)取速度，才采取這種變體。(2)輸入和輸出都是自然順序?qū)斎胱匀豁樞?，輸出亂序的第二級(jí)64第四節(jié)

基--2按頻率抽取的FFT算法Decimation-in-Frequency(DIF)

(Sander-Tukey)第四節(jié)

基--2按頻率抽取的FFT算法Decimation-65一、算法原理設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列的頻域的輸出序列X(k)(也是M點(diǎn)序列，按其頻域順序的奇偶分解為越來(lái)越短的子序列，稱(chēng)為基2按頻率抽取的FFT算法。也稱(chēng)為Sander-Tukey算法。一、算法原理設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列的66二、算法步驟

DFT變換：已證明頻域上X(k)按k的奇偶分為兩組，在時(shí)域上x(chóng)(n)按n的順序分前后兩局部，現(xiàn)將輸入x(n)按n的順序分前后兩局部:前半子序列x(n),0≤n≤N/2-1;后半子序列x(n+N/2),0≤n≤N/2-1;例：N=8時(shí)，前半序列為：x(0),x(1),x(2),x(3);后半序列為：x(4),x(5),x(6),x(7);那么由定義輸出〔求DFT〕二、算法步驟

DFT變換：已證明頻域上X(k)按k的奇偶分為67DSPFFT深入淺出詳細(xì)講解快速傅里葉變換683.變量置換--13.變量置換--1693.變量置換--23.變量置換--2703.變量置換--33.變量置換--3713.變量置換--43.變量置換--472一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：可見(jiàn)：如此分解，直至分到2點(diǎn)的DFT為止。一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X273DSPFFT深入淺出詳細(xì)講解快速傅里葉變換74三、蝶形流圖表示蝶形單元：時(shí)域中，前后半部表示式用蝶形結(jié)表示。x(n)x(n+N/2)與時(shí)間抽取法的推演過(guò)程一樣，由于N=2L,N/2仍為偶數(shù)，所以可以將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ì)半分后通過(guò)蝶形運(yùn)算而形成，直至最后為2點(diǎn)DFT。三、蝶形流圖表示蝶形單元：時(shí)域中，前后半部表示式用蝶形結(jié)表示75例子：求N=23=8點(diǎn)DIF

〔1〕先按N=8-->N/2=4，做4點(diǎn)的DIF：先將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)由x1(n)給出X(1),X(3),X(5),X(7),由x2(n)給出例子：求N=23=8點(diǎn)DIF

〔1〕先按N=8-->N/76將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)前半局部序列后半局部序列x1(n)x2(n)X2(k)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖4點(diǎn)x(0)4點(diǎn)77(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT

(a)先將4點(diǎn)分解成2點(diǎn)的DIF：因?yàn)?點(diǎn)DIF還是比較費(fèi)事，所以再繼續(xù)分解。(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT

(a)先將478〔b)一個(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)〔b)一個(gè)2點(diǎn)的DIF蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx1(0)79(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)(c)另一個(gè)2點(diǎn)的DIF蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx2(080(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就等于輸入信號(hào)本身，所以?xún)牲c(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x3(0)、x3(1)為例。(3)將N/4〔2點(diǎn)〕DFT再分解成2個(gè)1點(diǎn)的DFT

(a)81(b)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx3(0)1點(diǎn)DFTx3(1)X(0)X(4)進(jìn)一步簡(jiǎn)化為蝶形流圖：X(0)X(4)x3(0)x3(1)(b)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx3(0)1點(diǎn)DF82(4)一個(gè)完好N=8的按頻率抽取FFT的運(yù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(5)X(3)X(7)m=0m=1m=2(4)一個(gè)完好N=8的按頻率抽取FFT的運(yùn)算流圖x(0)X83(5)DIF的特點(diǎn)(a)輸入自然順序，輸出亂序且滿(mǎn)足碼位倒置規(guī)那么。(b)根據(jù)時(shí)域、頻域互換，可知：輸入亂序，輸出自然順序。(5)DIF的特點(diǎn)(a)輸入自然順序，輸出亂序且滿(mǎn)足碼位倒置84〔6〕DIF與DIT比較1一樣之處：〔1〕DIF與DIT兩種算法均為原位運(yùn)算?！?〕DIF與DIT運(yùn)算量一樣。它們都需要〔6〕DIF與DIT比較1一樣之處：85〔6〕DIF與DIT比較2不同之處：〔1〕DIF與DIT兩種算法構(gòu)造倒過(guò)來(lái)。DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀〞程序。DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀〞程序，再進(jìn)展求DFT?！?〕DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出如今減法之前。DIF的復(fù)數(shù)相乘出如今減法之后。〔6〕DIF與DIT比較2不同之處：86作業(yè)作業(yè)87第五節(jié)IFFT運(yùn)算方法以上所討論的FFT的運(yùn)算方法同樣可用于IDFT的運(yùn)算，簡(jiǎn)稱(chēng)為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導(dǎo)出以下二種利用FFT來(lái)計(jì)算FFT的方法。第五節(jié)IFFT運(yùn)算方法以上所討論的FFT的運(yùn)算方法同樣可用于88一、利用FFT計(jì)算IFFT的思路1將以下兩式進(jìn)展比較一、利用FFT計(jì)算IFFT的思路1將以下兩式進(jìn)展比較89二、利用FFT計(jì)算IFFT的思路2利用FFT計(jì)算IFFT時(shí)在命名上應(yīng)注意：(1)把FFT的時(shí)間抽取法，用于IDFT運(yùn)算時(shí)，由于輸入變量由時(shí)間序列x(n)改成頻率序列X(k),原來(lái)按x(n)的奇、偶次序分組的時(shí)間抽取法FFT，如今就變成了按X(k)的奇偶次序抽取了。〔2〕同樣，頻率抽取的FFT運(yùn)算用于IDFT運(yùn)算時(shí)，也應(yīng)改變?yōu)闀r(shí)間抽取的IFFT。二、利用FFT計(jì)算IFFT的思路2利用FFT計(jì)算IFFT時(shí)在90在IFFT的運(yùn)算中，常常把1/N分解為(1/2)m，并且在M級(jí)運(yùn)算中每一級(jí)運(yùn)算都分別乘以1/2因子，就可得到IFFT的兩種根本蝶形運(yùn)算構(gòu)造。〔并不常用此方法〕在IFFT的運(yùn)算中，常常把1/N分解為(1/2)m，并且在M91ABAB(a)頻率抽取IFFT的蝶形運(yùn)算(b)時(shí)間抽取IFFT的蝶形運(yùn)算ABAB(a)頻率抽取IFFT的蝶形運(yùn)算(b)時(shí)間抽取IFF92前面的兩種IFFT算法，排程序很方便，但要改變FFT的程序和參數(shù)才能實(shí)現(xiàn)?，F(xiàn)介紹第三種IFFT算法，那么可以完全不必改動(dòng)FFT程序。前面的兩種IFFT算法，排程序很方便，但要改變FFT的程序和93可知：只須將頻域成份一個(gè)求共軛變換，即〔1〕將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對(duì)運(yùn)算結(jié)果取一次共軛變換，并乘以常數(shù)1/N，即可以求出IFFT變換的x(n)的值。此為DFT可用FFT程序可知：只須將頻域成份一個(gè)求共軛變換，即〔1〕將X(k)的虛部94〔1〕FFT與IFFT連接應(yīng)用時(shí)，注意輸入輸出序列的排列順序，即應(yīng)注意是自然順序還是倒序?！?〕FFT和IFFT共用同一個(gè)程序時(shí)，也應(yīng)注意利用FFT算法輸入輸出的排列順序，即應(yīng)注意自然順序還是例位序〔3〕當(dāng)把頻率抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱(chēng)時(shí)間抽取IFFT流圖?！?〕當(dāng)把時(shí)間抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱(chēng)頻率抽取IFFT流圖。〔1〕FFT與IFFT連接應(yīng)用時(shí)，注意輸入輸出序列的排列順序95作業(yè)用C語(yǔ)言完成N=1024點(diǎn)的IDIT，IDIF。作業(yè)用C語(yǔ)言完成N=1024點(diǎn)的IDIT，IDIF。96第六節(jié)

線性調(diào)頻Z變換第六節(jié)

線性調(diào)頻Z變換97一、引入以上提出FFT算法，可以很快地求出全部DFT值。即求出有限長(zhǎng)序列x(n)的z變換X(z)在單位園上N個(gè)等間隔抽樣點(diǎn)zk處的抽樣值。它要求N為高度復(fù)合數(shù)。即N可以分解成一些因子的乘積。例N=2L實(shí)際上：〔1〕也許對(duì)其它圍線上z變換取樣發(fā)生興趣。如語(yǔ)音處理中，常常需要知道某一圍線z變換的極點(diǎn)所處的復(fù)頻率?！?〕只需要計(jì)算單位圓上某一段的頻譜。如窄帶信號(hào)，希望在窄帶頻率內(nèi)頻率抽樣可以非常密集，進(jìn)步分辨率，帶外那么不考慮?！?〕假設(shè)N是大素?cái)?shù)時(shí)，不能加以分解，又如何有效計(jì)算這種序列DFT。例N=311，假設(shè)用基2那么須補(bǔ)N=28=512點(diǎn)，要補(bǔ)211個(gè)零點(diǎn)。一、引入以上提出FFT算法，可以很快地求出全部DFT值。即求98二、問(wèn)題提出由上面三個(gè)問(wèn)題提出：為了進(jìn)步DFT的靈敏性，須用新的方法。線性調(diào)頻z變換(CZT)就是適用這種更為一般情況下，由x(n)求X(zk)的快速變換CZT：來(lái)自于雷達(dá)專(zhuān)業(yè)的專(zhuān)用詞匯。二、問(wèn)題提出由上面三個(gè)問(wèn)題提出：99Z變換采用螺線抽樣,可適用于更一般情況下由x(n)求X(zk)的快速算法,這種變換稱(chēng)為線性調(diào)頻Z變換(簡(jiǎn)稱(chēng)CZT).Z變換采用螺線抽樣,可適用于更一100為適應(yīng)z可以沿平面內(nèi)更一般的途徑取值，故：沿z平面上的一段螺線作等分角的抽樣，那么z的取樣點(diǎn)Zk可表示為：已知x(n)，0≤n≤N-1,那么它的z變換是：其中M：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。M不一定等于N。A，都為任意復(fù)數(shù)。為適應(yīng)z可以沿平面內(nèi)更一般的途徑取值，故：已知x(n)101DSPFFT深入淺出詳細(xì)講解快速傅里葉變換102DSPFFT深入淺出詳細(xì)講解快速傅里葉變換103DSPFFT深入淺出詳細(xì)講解快速傅里葉變換104DSPFFT深入淺出詳細(xì)講解快速傅里葉變換1055、圖形5、圖形1066、說(shuō)明1〔1〕A為起始樣點(diǎn)位置6、說(shuō)明1〔1〕A為起始樣點(diǎn)位置1076、說(shuō)明2〔2〕zk是z平面一段螺線上的等分角上某一采樣點(diǎn)。6、說(shuō)明2〔2〕zk是z平面一段螺線上的等分角上某一采樣點(diǎn)。1086、說(shuō)明36、說(shuō)明31096、說(shuō)明46、說(shuō)明41106、說(shuō)明56、說(shuō)明51117、CZT的實(shí)現(xiàn)步驟17、CZT的實(shí)現(xiàn)步驟11127、CZT的實(shí)現(xiàn)步驟27、CZT的實(shí)現(xiàn)步驟21137、CZT的實(shí)現(xiàn)步驟37、CZT的實(shí)現(xiàn)步驟31147、CZT的實(shí)現(xiàn)步驟47、CZT的實(shí)現(xiàn)步驟41157、CZT的實(shí)現(xiàn)步驟57、CZT的實(shí)現(xiàn)步驟51167、CZT的實(shí)現(xiàn)步驟67、CZT的實(shí)現(xiàn)步驟61177、CZT的實(shí)現(xiàn)步驟77、CZT的實(shí)現(xiàn)步驟71188、CZT變換運(yùn)算流程圖8、CZT變換運(yùn)算流程圖1199、CZT運(yùn)算量的估算19、CZT運(yùn)算量的估算11209、CZT運(yùn)算量的估算29、CZT運(yùn)算量的估算212110、CZT運(yùn)算量與直接運(yùn)算量比較當(dāng)M、N足夠小時(shí)，直接算法運(yùn)算量少。但M、N值比較大時(shí)〔大于50〕，CZT算法比直接算法的運(yùn)算量少得多。例M=50，N=50，N*M=2500次而CZT<1600次。10、CZT運(yùn)算量與直接運(yùn)算量比較當(dāng)M、N足夠小時(shí)，直接算法12211、CZT算法的特點(diǎn)與標(biāo)準(zhǔn)FFT算法相比，CZT算法有以下特點(diǎn)：〔1〕輸入序列長(zhǎng)N及輸出序列長(zhǎng)M不需要相等?！?〕N及M不必是高度合成數(shù)，二者均可為素?cái)?shù)?！?〕Zk的角間隔是任意的，其頻率分辨率也是任意的?！?〕周線不必是z平面上的圓，在語(yǔ)音分析中螺旋周線具有某些優(yōu)點(diǎn)。〔5〕起始點(diǎn)z0可任意選定，因此可以從任意頻率上開(kāi)場(chǎng)對(duì)輸入數(shù)據(jù)進(jìn)展窄帶高分辨率的分析。〔6〕假設(shè)A=1,M=N,可用CZT來(lái)計(jì)算DFT，即使N為素?cái)?shù)時(shí)，也可以?？傊珻ZT算法具有很大的靈敏性，在某種意義上說(shuō)，它是一個(gè)一般化的DFT。11、CZT算法的特點(diǎn)與標(biāo)準(zhǔn)FFT算法相比，CZT算法有以下12312、CZT變換的應(yīng)用1〔1〕利用CZT變換計(jì)算DFT。12、CZT變換的應(yīng)用1〔1〕利用CZT變換計(jì)算DFT。12412、CZT變換的應(yīng)用2〔2〕對(duì)信號(hào)的頻譜進(jìn)展細(xì)化分析。其中對(duì)窄帶信號(hào)頻譜或?qū)植扛信d趣的頻譜進(jìn)展細(xì)化分析。這樣CZT只對(duì)感興趣的頻率區(qū)段進(jìn)展采樣。計(jì)算量小很多，有利于實(shí)時(shí)處理?；蛟诒ＷC實(shí)時(shí)處理的情況下，可大進(jìn)步頻率分辨率。12、CZT變換的應(yīng)用2〔2〕對(duì)信號(hào)的頻譜進(jìn)展細(xì)化分析。其中12512、CZT變換的應(yīng)用3〔3〕求解z變換X(z)的零、極點(diǎn)。用于語(yǔ)音信號(hào)處理過(guò)程中。詳細(xì)方法：利用不同半徑同心圓，進(jìn)展等間隔的采樣。12、CZT變換的應(yīng)用3〔3〕求解z變換X(z)的零、極點(diǎn)。126作業(yè)作業(yè)127第七節(jié)

分裂基FFT算法第七節(jié)

分裂基FFT算法128一、開(kāi)展史自從基2快速算法出現(xiàn)以來(lái)，人們?nèi)栽诓粩鄬で蟾斓乃惴??；?FFT算法就比最初的基2FFT算法更快。從理論上講，用較大的基數(shù)還可以進(jìn)一步減少運(yùn)算次數(shù)，但要以程序〔或硬件〕變得更為復(fù)雜為代價(jià)。甚至得不償失。1984年，法國(guó)的杜梅爾(P.Dohamel)和霍爾曼(H.Hollmann)將基2分解和基4分解糅合在一起，提出了分裂基FFT算法。其運(yùn)算量比前幾種算法都有所減少，運(yùn)算流圖卻與基2FFT很接近，運(yùn)算程序也很短。它是目前一種實(shí)用的高效新算法。一、開(kāi)展史自從基2快速算法出現(xiàn)以來(lái)，人們?nèi)栽诓粩鄬で蟾斓乃?29二、分裂基FFT算法原理二、分裂基FFT算法原理130DSPFFT深入淺出詳細(xì)講解快速傅里葉變換131DSPFFT深入淺出詳細(xì)講解快速傅里葉變換132DSPFFT深入淺出詳細(xì)講解快速傅里葉變換133DSPFFT深入淺出詳細(xì)講解快速傅里葉變換134DSPFFT深入淺出詳細(xì)講解快速傅里葉變換135結(jié)論1結(jié)論1136N/2點(diǎn)DFTN/4點(diǎn)DFT...N/4點(diǎn)DFT...........................................-jN/2點(diǎn)N/4.N/4.............-j137結(jié)論2結(jié)論2138結(jié)論3結(jié)論3139例子下面以N=16為例，說(shuō)明完好的分裂基FFT運(yùn)算流圖的畫(huà)法和排列形式。例子下面以N=16為例，說(shuō)明完好的分裂基FFT運(yùn)算流圖的畫(huà)法140DSPFFT深入淺出詳細(xì)講解快速傅里葉變換141DSPFFT深入淺出詳細(xì)講解快速傅里葉變換142N/2點(diǎn)〔8點(diǎn)〕DFTN/4點(diǎn)〔4點(diǎn)〕DFTN/4點(diǎn)〔4點(diǎn)〕DFT-j-j-j-jN/2點(diǎn)N/4N/4-j-j-j-j143DSPFFT深入淺出詳細(xì)講解快速傅里葉變換144DSPFFT深入淺出詳細(xì)講解快速傅里葉變換145N/4點(diǎn)〔4點(diǎn)〕DFT-j-jN/4點(diǎn)-j-j146-j同理，用同樣方法可以畫(huà)出4點(diǎn)分裂基FFT算法L形運(yùn)算流