第四章 快速付里葉變換,FFT: Fast Fourier Transform,復(fù)習(xí),什么是FFT？ 直接計(jì)算DFT的工作量有多大？ 的性質(zhì)和特殊點(diǎn)？ 周期性、對(duì)稱性、可約性。 時(shí)域抽取法基2FFT基本原理？ 時(shí)間抽取法基2FFT具體的運(yùn)算步驟？,基2FFT具體的運(yùn)算步驟,實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算,X1(k):偶中偶,X2(k):偶中奇,進(jìn)行N/4點(diǎn)的DFT,得到,X3(k):偶中偶,X4(k):偶中奇,X5(k):奇中偶,X6(k):奇中奇,因此,8點(diǎn)DFT的FFT的運(yùn)算流圖,時(shí)間抽取基2FFT流圖繪制,N個(gè)輸入，N個(gè)輸出； 輸入為倒序碼，輸出為順序碼； N2M，表示運(yùn)算共M級(jí)數(shù)，取值為0M1； 蝶形運(yùn)算兩節(jié)點(diǎn)的距離: 2m，其中m表示第m級(jí) 每一級(jí)都有N/2個(gè)蝶形單元，可以分成若干組； 第m級(jí)的組數(shù)為： 每一組具有相同的結(jié)構(gòu)，相同的 因子分布；,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7,自然順序n 二進(jìn)制n n n 倒位序二進(jìn)制n n n 倒位順序n,2 1 0 0 1 2,4.2.5 頻域抽取法FFT(DIF-FFT),一、算法原理,設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列的頻域的輸出序列X(k)（也是M點(diǎn)序列）按其頻域順序的奇偶分解為越來(lái)越短的子序列，稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。,二、算法步驟,1.分組,已經(jīng)證明頻域上X(k)按k的奇偶分為兩組，在時(shí)域上x(chóng)(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);,2.代入DFT中,由于,因此 X(k)可表為,即：,3.N點(diǎn)DFT按k的奇偶分組可分為兩個(gè)N/2的DFT 當(dāng)k為偶數(shù),即 k=2r時(shí),(-1)k =1； 當(dāng)k為奇數(shù),即 k=2r+1 時(shí) (-1)k =-1 。 這時(shí) X(k) 可分為兩部分：,k為偶數(shù)時(shí)：,可見(jiàn),上面兩式均為N/2的DFT。,k為奇數(shù)時(shí)：,4.結(jié)論,三、蝶形流圖表示,蝶形單元：時(shí)域中，前后半部表示式用蝶形結(jié)表示。,x(n),x(n+N/2),與時(shí)間抽取法的推演過(guò)程一樣，由于N=2M,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 。,蝶形流圖的另一種形式,-1,例子：求 N=23=8點(diǎn)DIF （1）先按N=8N/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)給出,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),將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖,N=8點(diǎn)分解成2個(gè)4點(diǎn)的另一種形式,-1,-1,-1,-1,(2)N/2(4點(diǎn))N/4(2點(diǎn))FFT (a)先將4點(diǎn)分解成2點(diǎn)的DIF：,（b）一個(gè)2點(diǎn)的DIF蝶形流圖,(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,最后剩下兩點(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),進(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,N=8時(shí)DIFFFT流圖的另一種形式：,(5)DIF與DIT比較,1.相同點(diǎn) (1)進(jìn)行原位運(yùn)算； (2)運(yùn)算量相同,均為（N/2) Log2N次復(fù)乘,N Log2N次復(fù)加。 2.不同點(diǎn) (1)DIT輸入為倒位序,輸出為自然順序； DIF正好與此相反。 (2)DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。 DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。 DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。,4.2.6 IDFT的高效算法,以上所討論的FFT的運(yùn)算方法同樣可用于IDFT的運(yùn)算，簡(jiǎn)稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導(dǎo)出下列二種利用FFT來(lái)計(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),原來(lái)按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)算,四.不改(FFT)的程序直接實(shí)現(xiàn)IFFT,這就是說(shuō),先將X(k)取共軛,即將X(k)的 虛部乘-1，直接利用FFT程序計(jì)算DFT；然后 再取一次共軛；最后再乘1/N,即得 (n)。所 以FFT,IFFT可用一個(gè)子程序。,五、FFT的應(yīng)用,凡是利用付里葉變換來(lái)進(jìn)行分析、綜合、變換的地方，都可以利用FFT算法來(lái)減少其計(jì)算量。 FFT主要應(yīng)用在 （1）快速卷積 （2）快速相關(guān) （3）頻譜分析,1、線性卷積的FFT算法,一.線性卷積的長(zhǎng)度 設(shè)一離散線性移不變系統(tǒng)的沖激響 應(yīng)為 ,其輸入信號(hào)為 .其輸出 為 .并且 的長(zhǎng)度為L(zhǎng)點(diǎn), 的 長(zhǎng)度為M點(diǎn),則：,二、利用圓周卷積代替線卷積,用圓周卷積（FFT）代替線卷積的必要條件：x(n)、h(n)補(bǔ)零加長(zhǎng)至L=N+M