DSPFFT深入淺出詳細講解快速傅里葉變換.ppt
《DSPFFT深入淺出詳細講解快速傅里葉變換.ppt》由會員分享,可在線閱讀,更多相關(guān)《DSPFFT深入淺出詳細講解快速傅里葉變換.ppt(171頁珍藏版)》請在裝配圖網(wǎng)上搜索。
第四章快速付里葉變換(FFT)FastFourierTransforming,第一節(jié)引言,一、快速付里葉變換FFT,有限長序列通過離散傅里葉變換(DFT)將其頻域離散化成有限長序列.但其計算量太大(與N的平方成正比),很難實時地處理問題,因此引出了快速傅里葉變換(FFT).FFT并不是一種新的變換形式,它只是DFT的一種快速算法.并且根據(jù)對序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法.FFT在離散傅里葉反變換、線性卷積和線性相關(guān)等方面也有重要應用.。,二、FFT產(chǎn)生故事,當時加文(Garwin)在自已的研究中極需要一個計算付里葉變換的快速方法。他注意到圖基(J.W.Turkey)正在寫有關(guān)付里葉變換的文章,因此詳細詢問了圖基關(guān)于計算付里葉變換的技術(shù)知識。圖基概括地對加文介紹了一種方法,它實質(zhì)上就是后來的著名的庫利(CooleyJ.W)圖基算法。在加文的迫切要求下,庫利很快設(shè)計出一個計算機程序。1965年庫利--圖基在、MathematicofComputation雜志上發(fā)表了著名的“機器計算付里級數(shù)的一種算法”文章,提出一種快速計算DFT的方法和計算機程序--揭開了FFT發(fā)展史上的第一頁,促使FFT算法產(chǎn)生原因還有1967年至1968年間FFT的數(shù)字硬件制成,電子數(shù)字計算機的條件,使DFT的運算大簡化了。,三、本章主要內(nèi)容,1.直接計算DFT算法存在的問題及改進途徑。2.多種DFT算法(時間抽取算法DIT算法,頻率抽取算法DIF算法,線性調(diào)頻Z變換即CZT法)3.FFT的應用,第二節(jié)直接計算DFT算法存在的問題及改進途徑,一、直接計算DFT計算量,問題提出:設(shè)有限長序列x(n),非零值長度為N,計算對x(n)進行一次DFT運算,共需多大的運算工作量?,1.比較DFT與IDFT之間的運算量,其中x(n)為復數(shù),也為復數(shù)所以DFT與IDFT二者計算量相同。,2.以DFT為例,計算DFT復數(shù)運算量,計算一個X(k)(一個頻率成分)值,運算量為例k=1則要進行N次復數(shù)乘法+(N-1)次復數(shù)加法所以,要完成整個DFT運算,其計算量為:N*N次復數(shù)相乘和N*(N-1)次復數(shù)加法,3.一次復數(shù)乘法換算成實數(shù)運算量,復數(shù)運算要比加法運算復雜,需要的運算時間長。一個復數(shù)乘法包括4個實數(shù)乘法和2個實數(shù)相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad),,,,,4次實數(shù)乘法,,,2次實數(shù)加法,4.計算DFT需要的實數(shù)運算量,每運算一個X(k)的值,需要進行4N次實數(shù)相乘和2N+2(N-1)=2(2N-1)次實數(shù)相加.整個DFT運算量為:4N2次實數(shù)相乘和2N(2N-1)次實數(shù)相加.由此看出:直接計算DFT時,乘法次數(shù)與加法次數(shù)都是和N2成比例的。當N很大時,所需工作量非常可觀。,,,,例子,例1:當N=1024點時,直接計算DFT需要:N2=220=1048576次,即一百多萬次的復乘運算這對實時性很強的信號處理(如雷達信號處理)來講,它對計算速度有十分苛刻的要求-->迫切需要改進DFT的計算方法,以減少總的運算次數(shù)。例2:石油勘探,24道記錄,每道波形記錄長度5秒,若每秒抽樣500點/秒,每道總抽樣點數(shù)=500*5=2500點24道總抽樣點數(shù)=24*2500=6萬點DFT運算時間=N2=(60000)2=36*108次,作業(yè),二、改善DFT運算效率的基本途徑,利用DFT運算的系數(shù)的固有對稱性和周期性,改善DFT的運算效率。1.合并法:合并DFT運算中的某些項。3.分解法:將長序列DFT利用對稱性和周期性,分解為短序列DFT。,利用DFT運算的系數(shù)的固有對稱性和周期性,改善DFT的運算效率,的對稱性:,的周期性:,因為:,由此可得出:,例子,例:,利用以上特性,得到改進DFT直接算法的方法.,(1)合并法:步驟1分解成虛實部,合并DFT運算中的有些項對虛實部而言所以帶入DFT中:,(1)合并法:步驟2代入DFT中,展開:,(1)合并法:步驟3合并有些項,根據(jù):,有:,(1)合并法:步驟4結(jié)論,由此找出其它各項的類似歸并方法:乘法次數(shù)可以減少一半。例:,2、將長序列DFT利用對稱性和周期性分解為短序列DFT--思路,因為DFT的運算量與N2成正比的如果一個大點數(shù)N的DFT能分解為若干小點數(shù)DFT的組合,則顯然可以達到減少運算工作量的效果。,2、將長序列DFT利用對稱性和周期性分解為短序列DFT--方法,,,,把N點數(shù)據(jù)分成二半:,其運算量為:,再分二半:,,,+,=,+,+,+,=,這樣一直分下去,剩下兩點的變換。,2、將長序列DFT利用對稱性和周期性分解為短序列DFT--結(jié)論,快速付里時變換(FFT)就是在此特性基礎(chǔ)上發(fā)展起來的,并產(chǎn)生了多種FFT算法,其基本上可分成兩大類:按抽取方法分:時間抽取法(DIT);頻率抽取法(DIF)按“基數(shù)”分:基-2FFT算法;基-4FFT算法;混合基FFT算法;分裂基FFT算法其它方法:線性調(diào)頻Z變換(CZT法),第三節(jié)基--2按時間抽取的FFT算法Decimation-in-Time(DIT)(Coolkey-Tukey),一、算法原理,設(shè)輸入序列長度為N=2M(M為正整數(shù),將該序列按時間順序的奇偶分解為越來越短的子序列,稱為基2按時間抽取的FFT算法。也稱為Coolkey-Tukey算法。其中基數(shù)2----N=2M,M為整數(shù).若不滿足這個條件,可以人為地加上若干零值(加零補長)使其達到N=2M,例子,設(shè)一序列x(n)的長度為L=9,應加零補長為N=24=16應補7個零值。,,,,,,,,,,0123456789101112131415n,,,,,,,,x(n),,,二、算法步驟1.分組,變量置換,DFT變換:,先將x(n)按n的奇偶分為兩組,作變量置換:當n=偶數(shù)時,令n=2r;當n=奇數(shù)時,令n=2r+1;得到:x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;則可得其DFT為兩部分:前半部分:后半部分:,2.代入DFT中,,,生成兩個子序列,x(0),x(2)…x(2r)偶數(shù)點x(1),x(3)…x(2r+1)奇數(shù)點,代入DFT變換式:,3.求出子序列的DFT,上式得:,4.結(jié)論1,一個N點的DFT被分解為兩個N/2點DFT。X1(k),X2(k)這兩個N/2點的DFT按照:,再應用W系數(shù)的周期性,求出用X1(k),X2(k)表達的后半部的X(k+N/2)的值。,5.求出后半部的表示式,看出:后半部的k值所對應的X1(k),X2(k)則完全重復了前半部分的k值所對應的X1(k),X2(k)的值。,6.結(jié)論2,頻域中的N個點頻率成分為:,結(jié)論:只要求出(0~N/2-1)區(qū)間內(nèi)的各個整數(shù)k值所對應的X1(k),X2(k)值,即可以求出(0~N-1)整個區(qū)間內(nèi)全部X(k)值,這就是FFT能大量節(jié)省計算的關(guān)鍵。,7.結(jié)論3,由于N=2M,因此N/2仍為偶數(shù),可以依照上面方法進一步把每個N/2點子序列,再按輸入n的奇偶分解為兩個N/4點的子序列,按這種方法不斷劃分下去,直到最后剩下的是2點DFT,兩點DFT實際上只是加減運算。,三、蝶形結(jié),即蝶式計算結(jié)構(gòu)也即為蝶式信號流圖上面頻域中前/后半部分表示式可以用蝶形信號流圖表示。,,,,X1(k),X2(k),作圖要素:(1)左邊兩路為輸入(2)右邊兩路為輸出(3)中間以一個小圓表示加、減運算(右上路為相加輸出、右下路為相減輸出),(4)如果在某一支路上信號需要進行相乘運算,則在該支路上標以箭頭,將相乘的系數(shù)標在箭頭旁。,(5)當支路上沒有箭頭及系數(shù)時,則該支路的傳輸比為1。,,,例子:求N=23=8點FFT變換(1)先按N=8-->N/2=4,做4點的DFT:,先將N=8DFT分解成2個4點DFT:可知:時域上: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點直接DFT與分解2個4點DFT的FFT運算量,N=8點的直接DFT的計算量為:N2次(64次)復數(shù)相乘,N(N-1)次(8*(8-1)=56次)復數(shù)相加.共計120次。,(b)求一個蝶形結(jié)需要的運算量,要運算一個蝶形結(jié),需要一次乘法,兩次加法。,,,,(c)分解為兩個N/2=4點的DFT的運算量,分解2個N/2點(4點)的DFT:,,,偶數(shù)其復數(shù)相乘為復數(shù)相加為,,,奇數(shù)其復數(shù)相乘為復數(shù)相加為,,(d)用2個4點來求N=8點的FFT所需的運算量,再將N/2點(4點)合成N點(8點)DFT時,需要進行N/2個蝶形運算,還需N/2次(4次)乘法及次(8次)加法運算。,(e)將N=8點分解成2個4點的DFT的信號流圖,4點DFT,,,,,x(0)x(2)x(4)x(6),4點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)同學們自已寫,x1(r),x2(r),(2)N/2(4點)-->N/4(2點)FFT(a)先將4點分解成2點的DFT:,因為4點DFT還是比較麻煩,所以再繼續(xù)分解。若將N/2(4點)子序列按奇/偶分解成兩個N/4點(2點)子序列。即對將x1(r)和x2(r)分解成奇、偶兩個N/4點(2點)點的子序列。,(b)求2點的DFT,(c)一個2點的DFT蝶形流圖,2點DFT,,,,,2點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)另一個2點的DFT蝶形流圖,2點DFT,,,,,2點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點)DFT再分解成2個1點的DFT(a)求2個一點的DFT,最后剩下兩點DFT,它可分解成兩個一點DFT,但一點DFT就等于輸入信號本身,所以兩點DFT可用一個蝶形結(jié)表示。取x(0)、x(4)為例。,(b)2個1點的DFT蝶形流圖,1點DFT,,,x(0),1點DFT,,,x(4),,,,X3(0)X3(1),,,進一步簡化為蝶形流圖:,,,,,,X3(0)X3(1),x(0),x(4),(4)一個完整N=8的按時間抽取FFT的運算流圖,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)“級”概念,將N點DFT先分成兩個N/2點DFT,再是四個N/4點DFT…直至N/2個兩點DFT.每分一次稱為“一”級運算。因為N=2M所以N點DFT可分成M級如上圖所示依次m=0,m=1….M-1共M級,(2)“組”概念,每一級都有N/2個蝶形單元,例如:N=8,則每級都有4個蝶形單元。每一級的N/2個蝶形單元可以分成若干組,每一組具有相同的結(jié)構(gòu),相同的因子分布,第m級的組數(shù)為:,例:N=8=23,分3級。m=0級,分成四組,每組系數(shù)為m=1級,分成二組,每組系數(shù)為m=2級,分成一組,每組系數(shù)為,(3)因子的分布,結(jié)論:每由后向前(m由M-1-->0級)推進一級,則此系數(shù)為后級系數(shù)中偶數(shù)序號的那一半。,(4)按時間抽取法,2點DFT,2點DFT,2點DFT,2點DFT,2點DFT,2點DFT,2點DFT,2點DFT,兩個2點DFT,兩個2點DFT,兩個2點DFT,兩個2點DFT,,,,,,,,,兩個4點DFT,兩個4點DFT,兩個N/2點DFT,,,,,,,,,,,,,,,,,,,,,,,X1(k),…...,X2(k),,X(k),由于每一步分解都是基于在每級按輸入時間序列的次序是屬于偶數(shù)還是奇數(shù)來分解為兩個更短的序列,所以稱為“按時間抽取法”.,x(n),五、按時間抽取的FFT算法與直接計算DFT運算量的比較,由前面介紹的按時間抽取的FFT運算流圖可見:每級都由N/2個蝶形單元構(gòu)成,因此每一級運算都需要N/2次復乘和N次復加(每個結(jié)加減各一次)。這樣(N=2M)M級運算共需要:復乘次數(shù):復加次數(shù):可以得出如下結(jié)論:按時間抽取法所需的復乘數(shù)和復加數(shù)都是與成正比。而直接計算DFT時所需的復乘數(shù)與復加數(shù)則都是與N2成正比.(復乘數(shù)md=N2,復加數(shù)ad=N(N-1)≈N2),例子,看N=8點和N=1024點時直接計算DFT與用基2-按時間抽取法FFT的運算量。,看出:當N較大時,按時間抽取法將比直接法快一、二個數(shù)量級之多。,作業(yè),,六、按時間抽取FFT算法的特點,根據(jù)DIT基2-FFT算法原理,能得出任何N=2m點的FFT信號流圖,并進而得出FFT計算程序流程圖。最后總結(jié)出按時間抽取法解過程的規(guī)律。1.原位運算(in-place)2.碼位倒讀規(guī)則,1.原位運算(in-place),原位運算的結(jié)構(gòu),可以節(jié)省存儲單元,降低設(shè)備成本。定義:當數(shù)據(jù)輸入到存儲器以后,每一組運算的結(jié)果,仍然存放在這同一組存儲器中直到最后輸出。,,,,,,x(0),x(4),X3(0)X3(1),例子,例:N=8FFT運算,輸入:,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,,,,,,,,,,,,,,,,,看出:用原位運算結(jié)構(gòu)運算后,A(0)…A(7)正好順序存放X(0)…X(7),可以直接順序輸出。,2.碼位倒讀規(guī)則,我們從輸入序列的序號及整序規(guī)律得到碼位倒讀規(guī)則。由N=8蝶形圖看出:原位計算時,F(xiàn)FT輸出的X(k)的次序正好是順序排列的,即X(0)…X(7),但輸入x(n)都不能按自然順序存入到存儲單元中,而是按x(0),x(4),x(2),x(6)….的順序存入存儲單元即為亂序輸入,順序輸出。這種順序看起來相當雜亂,然而它是有規(guī)律的。即碼位倒讀規(guī)則。,例子,以N=8為例:,01234567,000001010011100101110111,自然順序,二進制碼表示,碼位倒讀,碼位倒置順序,000100010110001101011111,04261537,看出:碼位倒讀后的順序剛好是數(shù)據(jù)送入計算機內(nèi)的順序。,整序重排子程序,具體執(zhí)行時,只須將1與4對調(diào)送入,3與6對調(diào)送入,而0,2,5,7不變,僅需要一個中間存儲單元。,n01234567,n’04261537,,,,,,,,,在實際運算時,先按自然順序?qū)⑤斎胄蛄写嫒氪鎯卧?,再通過變址運算將自然順序變換成按時間抽取的FFT算法要求的順序。變址的過程可以用程序安排加以實現(xiàn)--稱為“整序”或“重排”(采用碼位倒讀)且注意:(1)當n=n’時,數(shù)據(jù)不必調(diào)換;(2)當n≠n時,必須將原來存放數(shù)據(jù)x(n)送入暫存器R,再將x(n’)送入x(n),R中內(nèi)容送x(n’).進行數(shù)據(jù)對調(diào)。(3)為了避免再次考慮前面已調(diào)換過的數(shù)據(jù),保證調(diào)換只進行一次,否則又變回原狀。n’>n時,調(diào)換。,作業(yè),編寫N=128點的基2--按時間抽取的FFT算法。要求用C語言編寫,并將輸入數(shù)據(jù)放在文件inputdata.dat中,輸出數(shù)據(jù)放在outputdata.dat文件中。,七、按時間抽取的FFT算法的若干變體1.思路,對于任何流圖,只要保持各節(jié)點所連續(xù)的支路及其傳輸系數(shù)不變,則不論節(jié)點位置怎么排列所得流圖總是等效的,最后所得結(jié)果都是x(n)的離散付里葉變換的正確結(jié)果。只是數(shù)據(jù)的提取和存放的次序不同而已。,(2)輸入是自然順序而輸出是亂序,將原先中與x(4)水平相鄰的所有節(jié)點跟x(1)水平相鄰的所有節(jié)點位置對調(diào);將原先中與x(6)水平相鄰的所有節(jié)點跟x(3)水平相鄰的所有節(jié)點位置對調(diào),其余諸節(jié)點保持不變,則可得:,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),它與輸入是亂序,輸出順序比較,看出:相同點:運算量一樣;不同點:第一是數(shù)據(jù)存入方式不同;第二是取用系數(shù)的順序不同。,(2)輸入和輸出都是自然順序,對輸入自然順序,輸出亂序的第二級,第三級節(jié)點作調(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)它失掉了“原位運算”的性質(zhì)。(2)為了變換N點數(shù)據(jù),至少需要2N個復數(shù)單元。在內(nèi)存比較緊張時,而對輸入數(shù)據(jù)整序并不困難時一般不用。為了爭取速度,才采取這種變體。,,,,,,,,,第四節(jié)基--2按頻率抽取的FFT算法Decimation-in-Frequency(DIF)(Sander-Tukey),一、算法原理,設(shè)輸入序列長度為N=2M(M為正整數(shù),將該序列的頻域的輸出序列X(k)(也是M點序列,按其頻域順序的奇偶分解為越來越短的子序列,稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。,二、算法步驟1.分組,DFT變換:,已證明頻域上X(k)按k的奇偶分為兩組,在時域上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時,前半序列為: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,一個N點的DFT被分解為兩個N/2點DFT。X1(k),X2(k)這兩個N/2點的DFT按照:,可見:如此分解,直至分到2點的DFT為止。,4.結(jié)論2,三、蝶形流圖表示,蝶形單元:時域中,前后半部表示式用蝶形結(jié)表示。,,,,x(n),x(n+N/2),,,,與時間抽取法的推演過程一樣,由于N=2L,N/2仍為偶數(shù),所以可以將N/2點DFT的輸出X(k)再分為偶數(shù)組和奇數(shù)組,這樣就將一個N/2點的DFT分成兩個N/4點DFT的輸入,也是將N/2點的DFT的輸入上、下對半分后通過蝶形運算而形成,直至最后為2點DFT。,例子:求N=23=8點DIF(1)先按N=8-->N/2=4,做4點的DIF:,先將N=8DFT分解成2個4點DFT:可知:時域上: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點分解成2個4點的DIF的信號流圖,4點DFT,,,,,x(0)x(1)x(2)x(3),4點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點)-->N/4(2點)FFT(a)先將4點分解成2點的DIF:,因為4點DIF還是比較麻煩,所以再繼續(xù)分解。,(b)一個2點的DIF蝶形流圖,2點DFT,,,,,2點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)另一個2點的DIF蝶形流圖,2點DFT,,,,,2點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點)DFT再分解成2個1點的DFT(a)求2個一點的DFT,最后剩下兩點DFT,它可分解成兩個一點DFT,但一點DFT就等于輸入信號本身,所以兩點DFT可用一個蝶形結(jié)表示。取x3(0)、x3(1)為例。,(b)2個1點的DFT蝶形流圖,1點DFT,,,x3(0),1點DFT,,,x3(1),,,,X(0)X(4),進一步簡化為蝶形流圖:,,,,X(0)X(4),x3(0),x3(1),,,,,(4)一個完整N=8的按頻率抽取FFT的運算流圖,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的特點,(a)輸入自然順序,輸出亂序且滿足碼位倒置規(guī)則。(b)根據(jù)時域、頻域互換,可知:輸入亂序,輸出自然順序。,(6)DIF與DIT比較1,相同之處:(1)DIF與DIT兩種算法均為原位運算。(2)DIF與DIT運算量相同。它們都需要,(6)DIF與DIT比較2,不同之處:(1)DIF與DIT兩種算法結(jié)構(gòu)倒過來。DIF為輸入順序,輸出亂序。運算完畢再運行“二進制倒讀”程序。DIT為輸入亂序,輸出順序。先運行“二進制倒讀”程序,再進行求DFT。(2)DIF與DIT根本區(qū)別:在于蝶形結(jié)不同。DIT的復數(shù)相乘出現(xiàn)在減法之前。DIF的復數(shù)相乘出現(xiàn)在減法之后。,作業(yè),第五節(jié)IFFT運算方法,以上所討論的FFT的運算方法同樣可用于IDFT的運算,簡稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā),可以導出下列二種利用FFT來計算FFT的方法。,一、利用FFT計算IFFT的思路1,將下列兩式進行比較,二、利用FFT計算IFFT的思路2,利用FFT計算IFFT時在命名上應注意:(1)把FFT的時間抽取法,用于IDFT運算時,由于輸入變量由時間序列x(n)改成頻率序列X(k),原來按x(n)的奇、偶次序分組的時間抽取法FFT,現(xiàn)在就變成了按X(k)的奇偶次序抽取了。(2)同樣,頻率抽取的FFT運算用于IDFT運算時,也應改變?yōu)闀r間抽取的IFFT。,三、改變FFT流圖系數(shù)的方法1.思路,在IFFT的運算中,常常把1/N分解為(1/2)m,并且在M級運算中每一級運算都分別乘以1/2因子,就可得到IFFT的兩種基本蝶形運算結(jié)構(gòu)。(并不常用此方法),2.IFFT的基本蝶形運算,,,,,,A,B,,,,,,A,B,(a)頻率抽取IFFT的蝶形運算,(b)時間抽取IFFT的蝶形運算,四.直接利用FFT流圖的方法1.思路,前面的兩種IFFT算法,排程序很方便,但要改變FFT的程序和參數(shù)才能實現(xiàn)?,F(xiàn)介紹第三種IFFT算法,則可以完全不必改動FFT程序。,2.直接利用FFT流圖方法的推導,可知:只須將頻域成份一個求共軛變換,即(1)將X(k)的虛部乘以-1,即先取X(k)的共軛,得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對運算結(jié)果取一次共軛變換,并乘以常數(shù)1/N,即可以求出IFFT變換的x(n)的值。,,此為DFT可用FFT程序,3.直接利用FFT流圖方法的注意點,(1)FFT與IFFT連接應用時,注意輸入輸出序列的排列順序,即應注意是自然順序還是倒序。(2)FFT和IFFT共用同一個程序時,也應注意利用FFT算法輸入輸出的排列順序,即應注意自然順序還是例位序(3)當把頻率抽取FFT流圖用于IDFT時,應改稱時間抽取IFFT流圖。(4)當把時間抽取FFT流圖用于IDFT時,應改稱頻率抽取IFFT流圖。,作業(yè),用C語言完成N=1024點的IDIT,IDIF。,第六節(jié)線性調(diào)頻Z變換,一、引入,以上提出FFT算法,可以很快地求出全部DFT值。即求出有限長序列x(n)的z變換X(z)在單位園上N個等間隔抽樣點zk處的抽樣值。它要求N為高度復合數(shù)。即N可以分解成一些因子的乘積。例N=2L實際上:(1)也許對其它圍線上z變換取樣發(fā)生興趣。如語音處理中,常常需要知道某一圍線z變換的極點所處的復頻率。(2)只需要計算單位圓上某一段的頻譜。如窄帶信號,希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集,提高分辨率,帶外則不考慮。(3)若N是大素數(shù)時,不能加以分解,又如何有效計算這種序列DFT。例N=311,若用基2則須補N=28=512點,要補211個零點。,二、問題提出,由上面三個問題提出:為了提高DFT的靈活性,須用新的方法。線性調(diào)頻z變換(CZT)就是適用這種更為一般情況下,由x(n)求X(zk)的快速變換CZT:來自于雷達專業(yè)的專用詞匯。,三、算法原理1.定義,Z變換采用螺線抽樣,可適用于更一般情況下由x(n)求X(zk)的快速算法,這種變換稱為線性調(diào)頻Z變換(簡稱CZT).,2.CZT公式推導1,為適應z可以沿平面內(nèi)更一般的路徑取值,故:沿z平面上的一段螺線作等分角的抽樣,則z的取樣點Zk可表示為:,已知x(n),0≤n≤N-1,則它的z變換是:,其中M:表示欲分析的復頻譜的點數(shù)。M不一定等于N。A,都為任意復數(shù)。,2.CZT公式推導2,2.CZT公式推導3,3.用CZT求解DFT的流圖,,,,,,,,,,,4.CZT變換各點的值,5、圖形,6、說明1,(1)A為起始樣點位置,6、說明2,(2)zk是z平面一段螺線上的等分角上某一采樣點。,6、說明3,6、說明4,6、說明5,7、CZT的實現(xiàn)步驟1,7、CZT的實現(xiàn)步驟2,7、CZT的實現(xiàn)步驟3,7、CZT的實現(xiàn)步驟4,7、CZT的實現(xiàn)步驟5,7、CZT的實現(xiàn)步驟6,7、CZT的實現(xiàn)步驟7,8、CZT變換運算流程圖,9、CZT運算量的估算1,9、CZT運算量的估算2,10、CZT運算量與直接運算量比較,當M、N足夠小時,直接算法運算量少。但M、N值比較大時(大于50),CZT算法比直接算法的運算量少得多。例M=50,N=50,N*M=2500次而CZT<1600次。,11、CZT算法的特點,與標準FFT算法相比,CZT算法有以下特點:(1)輸入序列長N及輸出序列長M不需要相等。(2)N及M不必是高度合成數(shù),二者均可為素數(shù)。(3)Zk的角間隔是任意的,其頻率分辨率也是任意的。(4)周線不必是z平面上的圓,在語音分析中螺旋周線具有某些優(yōu)點。(5)起始點z0可任意選定,因此可以從任意頻率上開始對輸入數(shù)據(jù)進行窄帶高分辨率的分析。(6)若A=1,M=N,可用CZT來計算DFT,即使N為素數(shù)時,也可以??傊珻ZT算法具有很大的靈活性,在某種意義上說,它是一個一般化的DFT。,12、CZT變換的應用1,(1)利用CZT變換計算DFT。,12、CZT變換的應用2,(2)對信號的頻譜進行細化分析。其中對窄帶信號頻譜或?qū)Σ糠指信d趣的頻譜進行細化分析。,這樣CZT只對感興趣的頻率區(qū)段進行采樣。計算量小很多,有利于實時處理。或在保證實時處理的情況下,可大提高頻率分辨率。,12、CZT變換的應用3,(3)求解z變換X(z)的零、極點。用于語音信號處理過程中。具體方法:利用不同半徑同心圓,進行等間隔的采樣。,作業(yè),第七節(jié)分裂基FFT算法,一、發(fā)展史,自從基2快速算法出現(xiàn)以來,人們?nèi)栽诓粩鄬で蟾斓乃惴?。?FFT算法就比最初的基2FFT算法更快。從理論上講,用較大的基數(shù)還可以進一步減少運算次數(shù),但要以程序(或硬件)變得更為復雜為代價。甚至得不償失。1984年,法國的杜梅爾(P.Dohamel)和霍爾曼(H.Hollmann)將基2分解和基4分解糅合在一起,提出了分裂基FFT算法。其運算量比前幾種算法都有所減少,運算流圖卻與基2FFT很接近,運算程序也很短。它是目前一種實用的高效新算法。,二、分裂基FFT算法原理,結(jié)論1,N/2點DFT,N/4點DFT,,,,,,,,...,N/4點DFT,...,,,,,,,...,...,,,,,,,...,...,...,...,,,,,,,...,...,....,,,,....,....,....,-j,,,,,,,,,,,,結(jié)論2,結(jié)論3,例子,下面以N=16為例,說明完整的分裂基FFT運算流圖的畫法和排列形式。,N/2點(8點)DFT,N/4點(4點)DFT,,,,,,,,N/4點(4點)DFT,,,,,,,,,,,,,,,,,,-j,,,,,,,,,,,,,,,,,,,,,,-j,-j,-j,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,N/4點(4點)DFT,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-j,-j,,,,,,,,,,,,,,,,,,,-j,,,同理,用同樣方法可以畫出4點分裂基FFT算法L形運算流圖.,,,,,-j,,,,,,,,,,,,,,,,,,,,,,-j,-j,-j,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-j,-j,,,,,,,,,,,,,,,,,,,,,,,,,,,,,-j,,,,,-j,,,-j,結(jié)論,由圖可看出,分裂基FFT算法結(jié)構(gòu)同基2FFT算法結(jié)構(gòu)相似,適用于N=2M的場合,并由M級運算實現(xiàn)。運算流圖輸入為順序,輸出為倒序。,分裂基FFT算法的運算量,作業(yè),第八節(jié)FFT的應用,凡是利用付里葉變換來進行分析、綜合、變換的地方,都可以利用FFT算法來減少其計算量。FFT主要應用在(1)快速卷積(2)快速相關(guān)(3)頻譜分析,一、快速卷積,設(shè)x(n)的長度為N點,h(n)的長度為M點,則:y(n)的長度為N+M-1點。所以直接計算y(n)線性卷積運算量為NM。,1.利用圓周卷積代替線卷積,用圓周卷積(FFT)代替線卷積的必要條件:x(n)、h(n)補零加長至L=N+M-1.然后計算圓卷積。求出y(n)代表線卷積。,2、用FFT計算y(n)的步驟,(1)求H(k)=DFT[h(n)](L點)(2)求X(k)=DFT[x(n)](L點)(3)計算Y(k)=X(k)H(k)(L點)(4)求y(n)=IDFT[Y(k)](L點),2、用FFT計算y(n)與直接計算y(n)的運算量比較,3、分段卷積的方法,(1)重疊相加法(2)重疊保留法設(shè)x(n)的長度為長序列N,h(n)為短序列列M。,(1)重疊相加法1,(1)x(n)為分段,每段長為p點,p選擇與M數(shù)量組相同。用xi(n)表示x(n)的第i段.,(1)重疊相加法2,(1)重疊相加法例子,(2)重疊保留法1,(2)重疊保留法2,(2)重疊保留法例子,二、快速相關(guān)1.方法,2.步驟,三、頻譜分析,這里我們僅介紹FFT的儀器設(shè)備:快速付里葉分析儀。其功能為:(1)能分析確定性信號的頻譜。(2)估計隨機信號的功率譜(3)并對信號進行快速卷積濾波(4)計算相關(guān)函數(shù),1.頻譜分析儀的框圖,數(shù)據(jù)選擇器,A/D,保護濾波器,輸入電路,,輸入,數(shù)據(jù)存儲器,運算器,數(shù)據(jù)選擇器,控制器,變址單元,函數(shù)發(fā)生器,輸出緩沖器,D/A,,輸出,,,,,,,,,,,,,,,,,,,,,2.部件說明,(1)保護濾波器:對輸入信號進行模擬濾波,濾掉噪聲,提取感興趣的有用信號,以便分析頻譜。(2)運算器:完成時間抽取FFT或Chirp-Z變換所要求運算。(3)RAM:存儲輸入數(shù)據(jù)。(4)ROM(函數(shù)發(fā)生器)。以表格形式存放蝶形運算因子W.(5)變址單元:根據(jù)輸入數(shù)據(jù),進行碼位倒置排序。,總結(jié),直接用DFT計算運算量與用FFT計算的運算量比較,及減少運算量的改進途徑。2.多種DFT算法(時間抽取算法DIT算法,頻率抽取算法DIF算法,線性調(diào)頻Z變換即CZT法)3.FFT的應用,直接用DFT計算的運算量與用FFT計算的運算量比較,減少運算量的途徑,復習,DFT的運算量基2-按時間抽取算法基2-按頻域抽取算法基2-FFT的運算量CZT變換,- 1.請仔細閱讀文檔,確保文檔完整性,對于不預覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔,不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請點此認領(lǐng)!既往收益都歸您。
下載文檔到電腦,查找使用更方便
14.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- DSPFFT 深入淺出 詳細 講解 快速 傅里葉變換
鏈接地址:http://www.3dchina-expo.com/p-11495712.html