《《快速付里葉變換》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《快速付里葉變換》PPT課件.ppt（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第四章 快速付里葉變換 FFT: Fast Fourier Transform 復(fù)習(xí) 什么是 FFT？ 直接計算 DFT的工作量有多大？ 的性質(zhì)和特殊點？ 周期性、對稱性、可約性。 時域抽取法基 2FFT基本原理？ 時間抽取法基 2FFT具體的運算步驟？ knNW 基 2FFT具體的運算步驟 X1(k) X2(k) kNW )()( 21 kXWkX kN )()( 21 kXWkX kN 實現(xiàn)上式運算的流圖稱作 蝶形運算 1 2 ,.,1,0),()()4( )()()( 21 21 N kkXWkXkX kXWkXkX k N k N X1(k):偶中偶 X2(k):偶中奇 進行 N/4點

2、的 DFT,得到 )()()( 431 2 kXWkXkX kN 1,1,0 4 Nk )()()4( 431 2 kXWkXkNX kN X3(k):偶中偶 X4(k):偶中奇 )()()( 652 2 kXWkXkX kN 1,1,0 4 Nk )()()4( 652 2 kXWkXkNX kN X5(k):奇中偶 X6(k):奇中奇 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) 04W 14W 2點 DFT 2點 DFT x(1) x(5) x(3) x(7) X5(0)

3、 X5(1) X6(0) X6(1) X2(0) X2(1) X2(2) X2(3) 04W 14W (0) (4) (2) (6) (1) (5) (3) (7) W N 0 W N 0 W N 0 W 0 N -1 -1 -1 -1 X (0) X (1) X (0) X (1) X (0) X (1) X (0) X (1) 3 3 4 4 5 5 6 6 W N 0 W N 2 W N 0 W N 2 -1 -1 -1 -1 X (0) X (1) X (2) X (3) X (0) X (1) X (2) X (3) 1 1 1 2 1 2 2 2 W W W W N 0 N 1 N

4、 2 N 3 -1 -1 -1 -1 X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) x x x x x x x x x 因此 ,8點 DFT的 FFT的運算流圖 時間抽取基 2FFT流圖繪制 N個輸入， N個輸出； 輸入為倒序碼，輸出為順序碼； N 2M，表示運算共 M級數(shù)，取值為 0 M 1； 蝶形運算兩節(jié)點的距離 : 2m，其中 m表示第 m級 每一級都有 N/2個蝶形單元，可以分成若干組 ； 第 m級的組數(shù)為： 每一組具有相同的結(jié)構(gòu)，相同的 因子分布 ； 12 m N rNW 121,0,12 mk kWm m 級的系數(shù)為第 3 8 2 8 1 8 0

5、88 2 8 0 8 1 4 0 44 0 8 0 22 ,3,2,102 101 00 WWWWkWm WWWWkWm WWkWm k k k ，級， ，級， 級， 即： 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 二進制 n n n 倒位序二進制 n n n 倒位順序 n 2 1 0 0 1 2 4.2.5 頻域抽取法 FFT(DIF-FFT) 一、算法原理 設(shè)輸入序

6、列長度為 N=2M(M為正整數(shù)，將該序 列的頻域的輸出序列 X(k)（也是 M點序列）按 其 頻域 順序的 奇偶分解 為越來越短的子序列， 稱為基 2按頻率抽取的 FFT算法。也稱為 Sander-Tukey算法。 二、算法步驟 1.分組 已經(jīng)證明頻域上 X(k)按 k的奇偶分為兩組，在時域上 x(n)按 n的順序分前后兩部分。 現(xiàn)將輸入 x(n)按 n的順序分前后兩部分 : 前半子序列 x(n),0nN/2-1; 后半子序列 x(n+N/2),0nN/2-1; 例： N=8時，前半序列為： x(0),x(1),x(2),x(3); 后半序列為： x(4),x(5),x(6),x(7); 2.

7、代入 DFT中 1 0 )()( N n nk NWnxkX 1 0 )( 1 0 1 2/ 1 0 2 2 2 2 ) 2 ()( )()( N N N N n kn N n nk N N Nn nk N n nk N W N nxWnx WnxWnx nk N n k N WW N nxnx N N 1 0 2 2) 2 ()( , 12 jN eW N kkNNW )1(2 nk N n k WNnxnxkX N 1 0 2 ) 2 ()1()()( 1,1,0 Nk 由于 因此 X(k)可表為 1 1 2 2 k N N k N N Wk Wk 奇數(shù)時 偶數(shù)時 即： 3.N點 DFT按

8、 k的奇偶分組可分為兩個 N/2的 DFT 當(dāng) k為偶數(shù) ,即 k=2r時 ,(-1)k =1； 當(dāng) k為奇數(shù) ,即 k=2r+1 時 (-1)k =-1 。 這時 X(k) 可分為兩部分： nr n nr N n N N N W N nxnx W N nxnx 2 2 2 1 0 2 1 0 ) 2 ()( ) 2 ()( )2( rX 1,1,0 2 Nr k為偶數(shù)時： 可見 ,上面兩式均為 N/2的 DFT。 nr n n N rn N n N N N WW N nxnx W N nxnxrX 2 2 2 1 0 )12( 1 0 ) 2 ()( ) 2 ()()12( k為奇數(shù)時： 1

9、,1,0 2 Nr 4.結(jié)論 1 2 ,1,0) 2 ()( )()( 1 2 ,1,0) 2 ()( )()( 2/ 12/ 0 2/ 12/ 0 22 2/ 12/ 0 2/ 12/ 0 11 N kWW N nxnx WnxkX N kW N nxnx WnxkX nk N N n n N nk N N n nk N N n nk N N n 三、蝶形流圖表示 蝶形單元： 時域 中，前后半部表示式用蝶形結(jié) 表示。 x(n) x(n+N/2) nNW )()2/()( 1 nxNnxnx )()2/()( 2 nxWNnxnx nN 與時間抽取法的推演過程一樣，由于 N=2M,N/2 仍為

10、偶數(shù)，所以 可以將 N/2 點 DFT 的輸出 X(k) 再分為偶數(shù)組和奇數(shù)組，這樣就 將一個 N/2 點的 DFT 分成兩個 N/4 點 DFT 的輸入，也是將 N/2 點 的 DFT 的輸入上、下對半分后通過蝶形運算而形成，直至最后 為 2 點 DFT 。 蝶形流圖的另一種形式 -1 )2()( Nnxnx 1,1,0 2 Nn n NW Nnxnx ) 2()( 進行如下蝶形運算：和 ) 2 ()( Nnxnx nNW )2( Nnx )(nx 例子：求 N=23=8點 DIF （ 1）先按 N=8-N/2=4，做 4點的 DIF： n N W N nxnxnx N nxnxnx ) 2

11、 ()()( ) 2 ()()( 2 1 先將 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)給出 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) 前 半 部 分 序 列

12、 后 半 部 分 序 列 n N n N n N n N WxxxWxxx WxxxWxxx xxxxxxxxxxxx )7()3(3,)6()2(2 ,)5()1(1,)4()0(0 )7()3(3),6()2(2),5()1(1),4()0(0 22 22 1111 ）（）（ ）（）（ ）（）（）（）（如： 08W 18W 28W 38W x1(n) x2(n) X2(k) 將 N=8點分解成 2個 4點的 DIF的信號流圖 N=8點分解成 2個 4點的 另一種形式 -1 -1 -1 -1 W W W W N N N N 0 1 2 3 )0(x )1(x )5(x )4(x )3(x )

13、2(x )7(x )6(x )0(X )2(X )6(X )1(X )3(X )5(X )7(X )4(XDFT N 點 2 DFT N 點 2 (2)N/2(4點 )-N/4(2點 )FFT (a)先將 4點分解成 2點的 DIF： 后半部分序列、 前半部分序列、 )3()2( )1()0(:)( 11 11 1 xx xxnx 101 4 0 ) 2 ()( )() 2 ()( 411 311 ，），在此（ ）（ 若設(shè)： L N L LxW N nxnx Lx N nxnx n N 后半部分序列、 前半部分序列、同理： )3()2( )1()0(:)( 22 22 2 xx xxnx 10

14、1 4 0 ) 2 ()( )() 2 ()( 622 522 ，），在此（ ）（ 同理： L N L LxW N nxnx Lx N nxnx n N （ 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) 08W 28W )3()1()1(,)2()0()0( 113113 xxxxxx 其中 (c)另 一個 2點的 DIF蝶形流圖 2點 DFT 2點 DFT x2(0) x2(1) x2(2) x2(3) x5(0) x5(1) x6(0) x

15、6(1) X(1) X(5) X(3) X(7) 08W 28W (3)將 N/4（ 2點） DFT再分解成 2 個 1點的 DFT 0 2 10 2 2 1 2 0 2 0 2 1 2 0 23 0 2 0 2 0 2 0 23 1 0 2 1,0;1,0 )4()0()4()0()1( )4()0()4()0()0( )()( 2 WW knWWWW WxWxWxWxX WxWxWxWxX WnxkX nknknk N nk N n nk N ，其中，則 這里用到對稱性 這是一蝶形結(jié) 代入上面流圖可知： 最后剩下兩點 DFT,它可分解成兩個一點 DFT，但一點 DFT就等于輸入信號本身，所

16、以兩點 DFT可用一個蝶形結(jié) 表示。取 x3(0)、 x3(1)為例。 (b)2個 1點的 DFT蝶形流圖 1點 DFT x3(0) 1點 DFT x3(1) 02W 進一步簡化為蝶形流圖： 02W 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) 38W 28W 18W 08W 08W 08W 08W 08W 08W 08W 28W 28W X(0) X(4) X(2) X(6) X(1) X(5) X(3) X(7) 12/0 NNN WW 其中旋轉(zhuǎn)因子，共有 m

17、=0 m=1 m=2 (0) X(0) (1) X(4) (2) X(2) (3) X(6) (4) X(1) (5) X(5) (6) X(3) (7) X(7) -1 -1 -1 -1 W W W W N N N N 0 1 2 3 -1 -1 -1 -1 W W W W N N N N 0 2 0 2 -1 -1 -1 -1 W W W W N N N N 0 0 0 0 x x x x x x x x N=8時 DIF FFT流圖的另一種形式： (5)DIF與 DIT比較 1.相同點 (1)進行原位運算； (2)運算量相同 ,均為（ N/2) Log2N次復(fù)乘 ,N Log2N 次復(fù)加

18、。 2.不同點 (1)DIT輸入為倒位序 ,輸出為自然順序； DIF正 好與此相反。 (2)DIF與 DIT根本區(qū)別：在于蝶形結(jié)不同。 DIT的復(fù)數(shù)相乘出現(xiàn)在 減法之前 。 DIF的復(fù)數(shù)相乘出現(xiàn)在 減法之后 。 4.2.6 IDFT的高效算法 以上所討論的 FFT的運算方法同樣可用于 IDFT的運算，簡稱為 IFFT。即快速付里 葉反變換。從 IDFT的定義出發(fā)，可以導(dǎo) 出下列二種利用 FFT來計算 FFT的方法。 一、利用 FFT計算 IFFT的思路 1 將下列兩式進行比較 I D F TFFT N WWD F T WnxnxD F TkX WkX N kXI D F Tnx nk N nk

19、 N N k nk N N k nk N 算法都可以拿來運算抽取 抽取或頻率）那么以上討論的時間（ 將運算結(jié)果都除以 改成運算中的每個系數(shù)只要把 3 )2( )1( )()()( )( 1 )()( 1 0 1 0 二、利用 FFT計算 IFFT的思路 2 利用 FFT計算 IFFT時在命名上應(yīng)注意： (1)把 FFT的時間抽取法，用于 IDFT運算時， 由于輸入變量由時間序列 x(n)改成頻率序列 X(k),原來按 x(n)的奇、偶次序分組的時間抽 取法 FFT，現(xiàn)在就變成了按 X(k)的奇偶次序 抽取了。 (2)同樣，頻率抽取的 FFT運算用于 IDFT運算 時，也應(yīng)改變?yōu)闀r間抽取的 IF

20、FT。 三、改變 FFT流圖系數(shù)的方法 1.思路 在 IFFT的運算中，常常把 1/N分解為 (1/2)m，并且在 M級運算中每一級運 算都分別乘以 1/2因子，就可得到 IFFT的兩種基本蝶形運算結(jié)構(gòu) 。 2.IFFT的基本蝶形運算 21 nNW21 BWA nN21 BWA nN21 A B 21 nNW21 BA21 nNWBA 21 A B (a)頻率抽取 IFFT的蝶形運算 (b)時間抽 取 IFFT的蝶形運算 四 .不改 (FFT)的 程序 直接實現(xiàn) IFFT nk N N k N k nk N WkX N WkX N nx 1 0 1 0 * )( 1 )( 1 )( )( 1

21、)( 1 1 0 kXD F T N WkX N nk N N k )( nx因此， BABAWW nkNnkN , 這就是說 ,先將 X(k)取共軛 ,即將 X(k)的 虛部乘 -1， 直接利用 FFT程序計算 DFT； 然后 再取一次共軛；最后再乘 1/N,即得 (n)。所 以 FFT,IFFT可用一個子程序 。 x 五、 FFT的應(yīng)用 凡是利用付里葉變換來進行分析、綜合、 變換的地方，都可以利用 FFT算法來減少 其計算量。 FFT主要應(yīng)用在 （ 1） 快速卷積 （ 2）快速相關(guān) （ 3）頻譜分析 1、線性卷積的 FFT算法 一 .線性卷積的長度 設(shè)一離散線性移不變系統(tǒng)的沖激響 應(yīng)為 ,

22、其輸入信號為 .其輸出 為 .并且 的長度為 L點 , 的 長度為 M點 ,則： )(nx )(nx)(nh )(nh )(ny)(nx )(nh 1 0 )()()()()( L m mnhmxnhnxny )(ny 二、利用圓周卷積代替線卷積 用圓周卷積（ FFT） 代替線卷積的必要條 件： x(n)、 h(n)補零加長至 L=N+M-1. 然后計算圓卷積。求出 y(n)代表線卷積。 10 10)( )( 10 10)( )( LnN Nnnh nh LnN Nnnx nx 三、用 FFT算 的步驟 )(ny ;1)(),(.1 點補零點，至少為將 LMNnhnx ；求 )()(.2 nhFFTkH ；求 )()(.3 nxF F TkX ；求 )()()(.4 kHkXkY 。求 )()(.5 kYI F F Tny FFT FFT IFFT x x(n) h(n) y(n) X(k) H(k) Y(k) 流程圖 作業(yè) 課后習(xí)題 1。 試畫出 N=16點的基 -2按時間抽取的 FFT流圖 （ DIT）。 試畫出 N=16點的基 -2按頻率抽取的 FFT流圖 （ DIF）。