《DSPFFT深入淺出詳細(xì)講解快速傅里葉變換.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《DSPFFT深入淺出詳細(xì)講解快速傅里葉變換.ppt（171頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

第四章快速付里葉變換(FFT)FastFourierTransforming,第一節(jié)引言,一、快速付里葉變換FFT,有限長(zhǎng)序列通過離散傅里葉變換(DFT)將其頻域離散化成有限長(zhǎng)序列.但其計(jì)算量太大(與N的平方成正比）,很難實(shí)時(shí)地處理問題,因此引出了快速傅里葉變換(FFT).FFT并不是一種新的變換形式,它只是DFT的一種快速算法.并且根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法.FFT在離散傅里葉反變換、線性卷積和線性相關(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ì)上就是后來的著名的庫利(CooleyJ.W)圖基算法。在加文的迫切要求下，庫利很快設(shè)計(jì)出一個(gè)計(jì)算機(jī)程序。1965年庫利--圖基在、MathematicofComputation雜志上發(fā)表了著名的“機(jī)器計(jì)算付里級(jí)數(shù)的一種算法”文章，提出一種快速計(jì)算DFT的方法和計(jì)算機(jī)程序--揭開了FFT發(fā)展史上的第一頁，促使FFT算法產(chǎn)生原因還有1967年至1968年間FFT的數(shù)字硬件制成，電子數(shù)字計(jì)算機(jī)的條件，使DFT的運(yùn)算大簡(jiǎn)化了。,三、本章主要內(nèi)容,1.直接計(jì)算DFT算法存在的問題及改進(jìn)途徑。2.多種DFT算法(時(shí)間抽取算法DIT算法，頻率抽取算法DIF算法，線性調(diào)頻Z變換即CZT法)3.FFT的應(yīng)用,第二節(jié)直接計(jì)算DFT算法存在的問題及改進(jìn)途徑,一、直接計(jì)算DFT計(jì)算量,問題提出：設(shè)有限長(zhǎng)序列x(n),非零值長(zhǎng)度為N,計(jì)算對(duì)x(n)進(jìn)行一次DFT運(yùn)算，共需多大的運(yùn)算工作量?,1.比較DFT與IDFT之間的運(yùn)算量,其中x(n)為復(fù)數(shù)，也為復(fù)數(shù)所以DFT與IDFT二者計(jì)算量相同。,2.以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ù)加法,3.一次復(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ù)乘法和2個(gè)實(shí)數(shù)相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad),,,,,4次實(shí)數(shù)乘法,,,2次實(shí)數(shù)加法,4.計(jì)算DFT需要的實(shí)數(shù)運(yùn)算量,每運(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í)，所需工作量非?？捎^。,,,,例子,例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次,作業(yè),二、改善DFT運(yùn)算效率的基本途徑,利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率。1.合并法：合并DFT運(yùn)算中的某些項(xiàng)。3.分解法：將長(zhǎng)序列DFT利用對(duì)稱性和周期性，分解為短序列DFT。,利用DFT運(yùn)算的系數(shù)的固有對(duì)稱性和周期性，改善DFT的運(yùn)算效率,的對(duì)稱性：,的周期性：,因?yàn)椋?由此可得出：,例子,例:,利用以上特性,得到改進(jìn)DFT直接算法的方法.,(1)合并法：步驟1分解成虛實(shí)部,合并DFT運(yùn)算中的有些項(xiàng)對(duì)虛實(shí)部而言所以帶入DFT中：,(1)合并法：步驟2代入DFT中,展開：,(1)合并法：步驟3合并有些項(xiàng),根據(jù)：,有：,(1)合并法：步驟4結(jié)論,由此找出其它各項(xiàng)的類似歸并方法：乘法次數(shù)可以減少一半。例：,2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT--思路,因?yàn)镈FT的運(yùn)算量與N2成正比的如果一個(gè)大點(diǎn)數(shù)N的DFT能分解為若干小點(diǎn)數(shù)DFT的組合，則顯然可以達(dá)到減少運(yùn)算工作量的效果。,2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT--方法,,,,把N點(diǎn)數(shù)據(jù)分成二半：,其運(yùn)算量為：,再分二半：,,,+,=,+,+,+,=,這樣一直分下去，剩下兩點(diǎn)的變換。,2、將長(zhǎng)序列DFT利用對(duì)稱性和周期性分解為短序列DFT--結(jié)論,快速付里時(shí)變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來的，并產(chǎn)生了多種FFT算法，其基本上可分成兩大類：按抽取方法分：時(shí)間抽取法(DIT);頻率抽取法(DIF)按“基數(shù)”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：線性調(diào)頻Z變換(CZT法),第三節(jié)基--2按時(shí)間抽取的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è)一序列x(n)的長(zhǎng)度為L(zhǎng)=9,應(yīng)加零補(bǔ)長(zhǎng)為N=24=16應(yīng)補(bǔ)7個(gè)零值。,,,,,,,,,,0123456789101112131415n,,,,,,,,x(n),,,二、算法步驟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為兩部分：前半部分：后半部分：,2.代入DFT中,,,生成兩個(gè)子序列,x(0),x(2)…x(2r)偶數(shù)點(diǎn)x(1),x(3)…x(2r+1)奇數(shù)點(diǎn),代入DFT變換式：,3.求出子序列的DFT,上式得：,4.結(jié)論1,一個(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)的值。,5.求出后半部的表示式,看出：后半部的k值所對(duì)應(yīng)的X1(k),X2(k)則完全重復(fù)了前半部分的k值所對(duì)應(yīng)的X1(k),X2(k)的值。,6.結(jié)論2,頻域中的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)鍵。,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)算。,三、蝶形結(jié),即蝶式計(jì)算結(jié)構(gòu)也即為蝶式信號(hào)流圖上面頻域中前/后半部分表示式可以用蝶形信號(hào)流圖表示。,,,,X1(k),X2(k),作圖要素：(1)左邊兩路為輸入(2)右邊兩路為輸出(3)中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸出、右下路為相減輸出),(4)如果在某一支路上信號(hào)需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。,(5)當(dāng)支路上沒有箭頭及系數(shù)時(shí)，則該支路的傳輸比為1。,,,例子：求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)給出,(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é)，需要一次乘法，兩次加法。,,,,（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ù)相加為,,(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)算,還需N/2次（4次）乘法及次(8次）加法運(yùn)算。,(e)將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DFT的信號(hào)流圖,4點(diǎn)DFT,,,,,x(0)x(2)x(4)x(6),4點(diǎn)DFT,,,,,x(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é)們自已寫,x1(r),x2(r),(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)）子序列。即對(duì)將x1(r)和x2(r)分解成奇、偶兩個(gè)N/4點(diǎn)（2點(diǎn)）點(diǎn)的子序列。,(b)求2點(diǎn)的DFT,（c)一個(gè)2點(diǎn)的DFT蝶形流圖,2點(diǎn)DFT,,,,,2點(diǎn)DFT,,,,,x(0)x(4),x(2)x(6),,,,,,,X3(0),X3(1),X4(0),X4(1),X1(0)X1(1),X1(2)X1(3),,,,,（d)另一個(gè)2點(diǎn)的DFT蝶形流圖,2點(diǎn)DFT,,,,,2點(diǎn)DFT,,,,,x(1)x(5),x(3)x(7),,,,,,,X5(0),X5(1),X6(0),X6(1),X2(0)X2(1),X2(2)X2(3),,,,,同理：,(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)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x(0)、x(4)為例。,(b)2個(gè)1點(diǎn)的DFT蝶形流圖,1點(diǎn)DFT,,,x(0),1點(diǎn)DFT,,,x(4),,,,X3(0)X3(1),,,進(jìn)一步簡(jiǎn)化為蝶形流圖：,,,,,,X3(0)X3(1),x(0),x(4),(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=0,m=1,m=2,四、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.每分一次稱為“一”級(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ù)為：,例：N=8=23，分3級(jí)。m=0級(jí),分成四組,每組系數(shù)為m=1級(jí),分成二組,每組系數(shù)為m=2級(jí),分成一組,每組系數(shù)為,(3)因子的分布,結(jié)論：每由后向前（m由M-1-->0級(jí)）推進(jìn)一級(jí)，則此系數(shù)為后級(jí)系數(shù)中偶數(shù)序號(hào)的那一半。,（4）按時(shí)間抽取法,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(diǎn)DFT,2點(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)DFT,,,,,,,,,,,,,,,,,,,,,,,X1(k),…...,X2(k),,X(k),由于每一步分解都是基于在每級(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),例子,看N=8點(diǎn)和N=1024點(diǎn)時(shí)直接計(jì)算DFT與用基2-按時(shí)間抽取法FFT的運(yùn)算量。,看出：當(dāng)N較大時(shí)，按時(shí)間抽取法將比直接法快一、二個(gè)數(shù)量級(jí)之多。,作業(yè),,六、按時(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ǔ)器中直到最后輸出。,,,,,,x(0),x(4),X3(0)X3(1),例子,例：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),,,,,,,,,,,,,,,,,,,,,,R1,R1,R1,R1,R1,R2,R1,R1,R2,R2,R3,R4,,,,,,,,,,,,,,,,,看出：用原位運(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)雜亂，然而它是有規(guī)律的。即碼位倒讀規(guī)則。,例子,以N=8為例：,01234567,000001010011100101110111,自然順序,二進(jìn)制碼表示,碼位倒讀,碼位倒置順序,000100010110001101011111,04261537,看出：碼位倒讀后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。,整序重排子程序,具體執(zhí)行時(shí)，只須將1與4對(duì)調(diào)送入，3與6對(duì)調(diào)送入，而0，2，5，7不變，僅需要一個(gè)中間存儲(chǔ)單元。,n01234567,n’04261537,,,,,,,,,在實(shí)際運(yùn)算時(shí)，先按自然順序?qū)⑤斎胄蛄写嫒氪鎯?chǔ)單元，再通過變址運(yùn)算將自然順序變換成按時(shí)間抽取的FFT算法要求的順序。變址的過程可以用程序安排加以實(shí)現(xiàn)--稱為“整序”或“重排”（采用碼位倒讀）且注意：(1)當(dāng)n=n’時(shí)，數(shù)據(jù)不必調(diào)換；(2)當(dāng)n≠n時(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)行一次，否則又變回原狀。n’>n時(shí)，調(diào)換。,作業(yè),編寫N=128點(diǎn)的基2--按時(shí)間抽取的FFT算法。要求用C語言編寫，并將輸入數(shù)據(jù)放在文件inputdata.dat中，輸出數(shù)據(jù)放在outputdata.dat文件中。,七、按時(shí)間抽取的FFT算法的若干變體1.思路,對(duì)于任何流圖，只要保持各節(jié)點(diǎn)所連續(xù)的支路及其傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，最后所得結(jié)果都是x(n)的離散付里葉變換的正確結(jié)果。只是數(shù)據(jù)的提取和存放的次序不同而已。,(2)輸入是自然順序而輸出是亂序,將原先中與x(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)輸入和輸出都是自然順序,對(duì)輸入自然順序，輸出亂序的第二級(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）它失掉了“原位運(yùn)算”的性質(zhì)。（2）為了變換N點(diǎn)數(shù)據(jù)，至少需要2N個(gè)復(fù)數(shù)單元。在內(nèi)存比較緊張時(shí)，而對(duì)輸入數(shù)據(jù)整序并不困難時(shí)一般不用。為了爭(zhēng)取速度，才采取這種變體。,,,,,,,,,第四節(jié)基--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變換：,已證明頻域上X(k)按k的奇偶分為兩組，在時(shí)域上x(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）,2.代入DFT中,3.變量置換--1,3.變量置換--2,3.變量置換--3,3.變量置換--4,4.結(jié)論1,一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：,可見：如此分解，直至分到2點(diǎn)的DFT為止。,4.結(jié)論2,三、蝶形流圖表示,蝶形單元：時(shí)域中，前后半部表示式用蝶形結(jié)表示。,,,,x(n),x(n+N/2),,,,與時(shí)間抽取法的推演過程一樣，由于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ì)半分后通過蝶形運(yùn)算而形成，直至最后為2點(diǎn)DFT。,例子：求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=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖,4點(diǎn)DFT,,,,,x(0)x(1)x(2)x(3),4點(diǎn)DFT,,,,,x(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),(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還是比較麻煩，所以再繼續(xù)分解。,（b)一個(gè)2點(diǎn)的DIF蝶形流圖,2點(diǎn)DFT,,,,,2點(diǎn)DFT,,,,,x1(0)x1(1),x1(2)x1(3),,,,,,,x3(0),x3(1),x4(0),x4(1),X(0)X(4),X(2)X(6),,,,,(c)另一個(gè)2點(diǎn)的DIF蝶形流圖,2點(diǎn)DFT,,,,,2點(diǎn)DFT,,,,,x2(0)x2(1),x2(2)x2(3),,,,,,,x5(0),x5(1),x6(0),x6(1),X(1)X(5),X(3)X(7),,,,,(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)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x3(0)、x3(1)為例。,(b)2個(gè)1點(diǎn)的DFT蝶形流圖,1點(diǎn)DFT,,,x3(0),1點(diǎn)DFT,,,x3(1),,,,X(0)X(4),進(jìn)一步簡(jiǎn)化為蝶形流圖：,,,,X(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)x(6)x(7),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7),m=0,m=1,m=2,,,,,,,,,,,,,,,,,,,,,,,,,(5)DIF的特點(diǎn),(a)輸入自然順序，輸出亂序且滿足碼位倒置規(guī)則。(b)根據(jù)時(shí)域、頻域互換，可知：輸入亂序，輸出自然順序。,（6）DIF與DIT比較1,相同之處：（1）DIF與DIT兩種算法均為原位運(yùn)算。（2）DIF與DIT運(yùn)算量相同。它們都需要,（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)在減法之后。,作業(yè),第五節(jié)IFFT運(yùn)算方法,以上所討論的FFT的運(yùn)算方法同樣可用于IDFT的運(yùn)算，簡(jiǎn)稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導(dǎo)出下列二種利用FFT來計(jì)算FFT的方法。,一、利用FFT計(jì)算IFFT的思路1,將下列兩式進(jìn)行比較,二、利用FFT計(jì)算IFFT的思路2,利用FFT計(jì)算IFFT時(shí)在命名上應(yīng)注意：(1)把FFT的時(shí)間抽取法，用于IDFT運(yùn)算時(shí)，由于輸入變量由時(shí)間序列x(n)改成頻率序列X(k),原來按x(n)的奇、偶次序分組的時(shí)間抽取法FFT，現(xiàn)在就變成了按X(k)的奇偶次序抽取了。（2）同樣，頻率抽取的FFT運(yùn)算用于IDFT運(yùn)算時(shí)，也應(yīng)改變?yōu)闀r(shí)間抽取的IFFT。,三、改變FFT流圖系數(shù)的方法1.思路,在IFFT的運(yùn)算中，常常把1/N分解為(1/2)m，并且在M級(jí)運(yùn)算中每一級(jí)運(yùn)算都分別乘以1/2因子，就可得到IFFT的兩種基本蝶形運(yùn)算結(jié)構(gòu)。（并不常用此方法）,2.IFFT的基本蝶形運(yùn)算,,,,,,A,B,,,,,,A,B,(a)頻率抽取IFFT的蝶形運(yùn)算,(b)時(shí)間抽取IFFT的蝶形運(yùn)算,四.直接利用FFT流圖的方法1.思路,前面的兩種IFFT算法，排程序很方便，但要改變FFT的程序和參數(shù)才能實(shí)現(xiàn)?，F(xiàn)介紹第三種IFFT算法，則可以完全不必改動(dòng)FFT程序。,2.直接利用FFT流圖方法的推導(dǎo),可知：只須將頻域成份一個(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程序,3.直接利用FFT流圖方法的注意點(diǎn),（1）FFT與IFFT連接應(yīng)用時(shí)，注意輸入輸出序列的排列順序，即應(yīng)注意是自然順序還是倒序。（2）FFT和IFFT共用同一個(gè)程序時(shí)，也應(yīng)注意利用FFT算法輸入輸出的排列順序，即應(yīng)注意自然順序還是例位序（3）當(dāng)把頻率抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱時(shí)間抽取IFFT流圖。（4）當(dāng)把時(shí)間抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱頻率抽取IFFT流圖。,作業(yè),用C語言完成N=1024點(diǎn)的IDIT，IDIF。,第六節(jié)線性調(diào)頻Z變換,一、引入,以上提出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ā)生興趣。如語音處理中，常常需要知道某一圍線z變換的極點(diǎn)所處的復(fù)頻率。（2）只需要計(jì)算單位圓上某一段的頻譜。如窄帶信號(hào)，希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集，提高分辨率，帶外則不考慮。（3）若N是大素?cái)?shù)時(shí)，不能加以分解，又如何有效計(jì)算這種序列DFT。例N=311，若用基2則須補(bǔ)N=28=512點(diǎn)，要補(bǔ)211個(gè)零點(diǎn)。,二、問題提出,由上面三個(gè)問題提出：為了提高DFT的靈活性，須用新的方法。線性調(diào)頻z變換(CZT)就是適用這種更為一般情況下，由x(n)求X(zk)的快速變換CZT：來自于雷達(dá)專業(yè)的專用詞匯。,三、算法原理1.定義,Z變換采用螺線抽樣,可適用于更一般情況下由x(n)求X(zk)的快速算法,這種變換稱為線性調(diào)頻Z變換(簡(jiǎn)稱CZT).,2.CZT公式推導(dǎo)1,為適應(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ù)。,2.CZT公式推導(dǎo)2,2.CZT公式推導(dǎo)3,3.用CZT求解DFT的流圖,,,,,,,,,,,4.CZT變換各點(diǎn)的值,5、圖形,6、說明1,（1）A為起始樣點(diǎn)位置,6、說明2,（2）zk是z平面一段螺線上的等分角上某一采樣點(diǎn)。,6、說明3,6、說明4,6、說明5,7、CZT的實(shí)現(xiàn)步驟1,7、CZT的實(shí)現(xiàn)步驟2,7、CZT的實(shí)現(xiàn)步驟3,7、CZT的實(shí)現(xiàn)步驟4,7、CZT的實(shí)現(xiàn)步驟5,7、CZT的實(shí)現(xiàn)步驟6,7、CZT的實(shí)現(xiàn)步驟7,8、CZT變換運(yùn)算流程圖,9、CZT運(yùn)算量的估算1,9、CZT運(yùn)算量的估算2,10、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次。,11、CZT算法的特點(diǎn),與標(biāo)準(zhǔn)FFT算法相比，CZT算法有以下特點(diǎn)：（1）輸入序列長(zhǎng)N及輸出序列長(zhǎng)M不需要相等。（2）N及M不必是高度合成數(shù)，二者均可為素?cái)?shù)。（3）Zk的角間隔是任意的，其頻率分辨率也是任意的。（4）周線不必是z平面上的圓，在語音分析中螺旋周線具有某些優(yōu)點(diǎn)。（5）起始點(diǎn)z0可任意選定，因此可以從任意頻率上開始對(duì)輸入數(shù)據(jù)進(jìn)行窄帶高分辨率的分析。（6）若A=1,M=N,可用CZT來計(jì)算DFT，即使N為素?cái)?shù)時(shí)，也可以。總之，CZT算法具有很大的靈活性，在某種意義上說，它是一個(gè)一般化的DFT。,12、CZT變換的應(yīng)用1,（1）利用CZT變換計(jì)算DFT。,12、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í)處理的情況下，可大提高頻率分辨率。,12、CZT變換的應(yīng)用3,（3）求解z變換X(z)的零、極點(diǎn)。用于語音信號(hào)處理過程中。具體方法：利用不同半徑同心圓，進(jìn)行等間隔的采樣。,作業(yè),第七節(jié)分裂基FFT算法,一、發(fā)展史,自從基2快速算法出現(xiàn)以來，人們?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í)用的高效新算法。,二、分裂基FFT算法原理,結(jié)論1,N/2點(diǎn)DFT,N/4點(diǎn)DFT,,,,,,,,...,N/4點(diǎn)DFT,...,,,,,,,...,...,,,,,,,...,...,...,...,,,,,,,...,...,....,,,,....,....,....,-j,,,,,,,,,,,,結(jié)論2,結(jié)論3,例子,下面以N=16為例，說明完整的分裂基FFT運(yùn)算流圖的畫法和排列形式。,N/2點(diǎn)（8點(diǎn)）DFT,N/4點(diǎn)（4點(diǎn)）DFT,,,,,,,,N/4點(diǎn)（4點(diǎn)）DFT,,,,,,,,,,,,,,,,,,-j,,,,,,,,,,,,,,,,,,,,,,-j,-j,-j,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,N/4點(diǎn)（4點(diǎn)）DFT,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-j,-j,,,,,,,,,,,,,,,,,,,-j,,,同理，用同樣方法可以畫出4點(diǎn)分裂基FFT算法L形運(yùn)算流圖.,,,,,-j,,,,,,,,,,,,,,,,,,,,,,-j,-j,-j,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-j,-j,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-j,,,,,-j,,,-j,結(jié)論,由圖可看出，分裂基FFT算法結(jié)構(gòu)同基2FFT算法結(jié)構(gòu)相似，適用于N=2M的場(chǎng)合，并由M級(jí)運(yùn)算實(shí)現(xiàn)。運(yùn)算流圖輸入為順序，輸出為倒序。,分裂基FFT算法的運(yùn)算量,作業(yè),第八節(jié)FFT的應(yīng)用,凡是利用付里葉變換來進(jìn)行分析、綜合、變換的地方，都可以利用FFT算法來減少其計(jì)算量。FFT主要應(yīng)用在（1）快速卷積（2）快速相關(guān)（3）頻譜分析,一、快速卷積,設(shè)x(n)的長(zhǎng)度為N點(diǎn)，h(n)的長(zhǎng)度為M點(diǎn)，則：y(n)的長(zhǎng)度為N+M-1點(diǎn)。所以直接計(jì)算y(n)線性卷積運(yùn)算量為NM。,1.利用圓周卷積代替線卷積,用圓周卷積（FFT）代替線卷積的必要條件：x(n)、h(n)補(bǔ)零加長(zhǎng)至L=N+M-1.然后計(jì)算圓卷積。求出y(n)代表線卷積。,2、用FFT計(jì)算y(n)的步驟,(1)求H(k)=DFT[h(n)](L點(diǎn)）(2)求X(k)=DFT[x(n)](L點(diǎn)）(3)計(jì)算Y(k)=X(k)H(k)(L點(diǎn)）(4)求y(n)=IDFT[Y(k)](L點(diǎn)）,2、用FFT計(jì)算y(n)與直接計(jì)算y(n)的運(yùn)算量比較,3、分段卷積的方法,（1）重疊相加法（2）重疊保留法設(shè)x(n)的長(zhǎng)度為長(zhǎng)序列N，h(n)為短序列列M。,（1）重疊相加法1,（1）x(n)為分段，每段長(zhǎng)為p點(diǎn)，p選擇與M數(shù)量組相同。用xi(n)表示x(n)的第i段.,（1）重疊相加法2,（1）重疊相加法例子,（2）重疊保留法1,（2）重疊保留法2,（2）重疊保留法例子,二、快速相關(guān)1.方法,2.步驟,三、頻譜分析,這里我們僅介紹FFT的儀器設(shè)備：快速付里葉分析儀。其功能為：（1）能分析確定性信號(hào)的頻譜。（2）估計(jì)隨機(jī)信號(hào)的功率譜（3）并對(duì)信號(hào)進(jìn)行快速卷積濾波（4）計(jì)算相關(guān)函數(shù),1.頻譜分析儀的框圖,數(shù)據(jù)選擇器,A/D,保護(hù)濾波器,輸入電路,,輸入,數(shù)據(jù)存儲(chǔ)器,運(yùn)算器,數(shù)據(jù)選擇器,控制器,變址單元,函數(shù)發(fā)生器,輸出緩沖器,D/A,,輸出,,,,,,,,,,,,,,,,,,,,,2.部件說明,（1）保護(hù)濾波器：對(duì)輸入信號(hào)進(jìn)行模擬濾波，濾掉噪聲，提取感興趣的有用信號(hào)，以便分析頻譜。（2）運(yùn)算器：完成時(shí)間抽取FFT或Chirp-Z變換所要求運(yùn)算。（3）RAM:存儲(chǔ)輸入數(shù)據(jù)。（4）ROM(函數(shù)發(fā)生器）。以表格形式存放蝶形運(yùn)算因子W.(5)變址單元：根據(jù)輸入數(shù)據(jù)，進(jìn)行碼位倒置排序。,總結(jié),直接用DFT計(jì)算運(yùn)算量與用FFT計(jì)算的運(yùn)算量比較，及減少運(yùn)算量的改進(jìn)途徑。2.多種DFT算法(時(shí)間抽取算法DIT算法，頻率抽取算法DIF算法，線性調(diào)頻Z變換即CZT法)3.FFT的應(yīng)用,直接用DFT計(jì)算的運(yùn)算量與用FFT計(jì)算的運(yùn)算量比較，減少運(yùn)算量的途徑,復(fù)習(xí),DFT的運(yùn)算量基2-按時(shí)間抽取算法基2-按頻域抽取算法基2-FFT的運(yùn)算量CZT變換,