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

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

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點(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) 04W 14W 2點(diǎn) DFT 2點(diǎn) 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點(diǎn) DFT的 FFT的運(yùn)算流圖 時(shí)間抽取基 2FFT流圖繪制 N個(gè)輸入， N個(gè)輸出； 輸入為倒序碼，輸出為順序碼； N 2M，表示運(yùn)算共 M級(jí)數(shù)，取值為 0 M 1； 蝶形運(yùn)算兩節(jié)點(diǎn)的距離 : 2m，其中 m表示第 m級(jí) 每一級(jí)都有 N/2個(gè)蝶形單元，可以分成若干組 ； 第 m級(jí)的組數(shù)為： 每一組具有相同的結(jié)構(gòu)，相同的 因子分布 ； 12 m N rNW 121,0,12 mk kWm m 級(jí)的系數(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 ，級(jí)， ，級(jí)， 級(jí)， 即： 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è)輸入序

6、列長(zhǎng)度為 N=2M(M為正整數(shù)，將該序 列的頻域的輸出序列 X(k)（也是 M點(diǎn)序列）按 其 頻域 順序的 奇偶分解 為越來越短的子序列， 稱為基 2按頻率抽取的 FFT算法。也稱為 Sander-Tukey算法。 二、算法步驟 1.分組 已經(jīng)證明頻域上 X(k)按 k的奇偶分為兩組，在時(shí)域上 x(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.

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í) 偶數(shù)時(shí) 即： 3.N點(diǎn) DFT按

8、 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) 可分為兩部分： 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ù)時(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ù)時(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 三、蝶形流圖表示 蝶形單元： 時(shí)域 中，前后半部表示式用蝶形結(jié) 表示。 x(n) x(n+N/2) nNW )()2/()( 1 nxNnxnx )()2/()( 2 nxWNnxnx nN 與時(shí)間抽取法的推演過程一樣，由于 N=2M,N/2 仍為

10、偶數(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 。 蝶形流圖的另一種形式 -1 )2()( Nnxnx 1,1,0 2 Nn n NW Nnxnx ) 2()( 進(jìn)行如下蝶形運(yùn)算：和 ) 2 ()( Nnxnx nNW )2( Nnx )(nx 例子：求 N=23=8點(diǎn) DIF （ 1）先按 N=8-N/2=4，做 4點(diǎn)的 DIF： n N W N nxnxnx N nxnxnx ) 2

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

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點(diǎn)分解成 2個(gè) 4點(diǎn)的 DIF的信號(hào)流圖 N=8點(diǎn)分解成 2個(gè) 4點(diǎn)的 另一種形式 -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 點(diǎn) 2 DFT N 點(diǎn) 2 (2)N/2(4點(diǎn) )-N/4(2點(diǎn) )FFT (a)先將 4點(diǎn)分解成 2點(diǎn)的 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）一個(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) 08W 28W )3()1()1(,)2()0()0( 113113 xxxxxx 其中 (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) x

15、6(1) X(1) X(5) X(3) X(7) 08W 28W (3)將 N/4（ 2點(diǎn)） DFT再分解成 2 個(gè) 1點(diǎn)的 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 ，其中，則 這里用到對(duì)稱性 這是一蝶形結(jié) 代入上面流圖可知： 最后剩下兩點(diǎn) DFT,它可分解成兩個(gè)一點(diǎn) DFT，但一點(diǎn) DFT就等于輸入信號(hào)本身，所

16、以兩點(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) 02W 進(jìn)一步簡(jiǎn)化為蝶形流圖： 02W 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) 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時(shí) DIF FFT流圖的另一種形式： (5)DIF與 DIT比較 1.相同點(diǎn) (1)進(jìn)行原位運(yùn)算； (2)運(yùn)算量相同 ,均為（ N/2) Log2N次復(fù)乘 ,N Log2N 次復(fù)加

18、。 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來計(jì)算 FFT的方法。 一、利用 FFT計(jì)算 IFFT的思路 1 將下列兩式進(jìn)行比較 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 算法都可以拿來運(yùn)算抽取 抽取或頻率）那么以上討論的時(shí)間（ 將運(yùn)算結(jié)果都除以 改成運(yùn)算中的每個(gè)系數(shù)只要把 3 )2( )1( )()()( )( 1 )()( 1 0 1 0 二、利用 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í)間抽取的 IF

20、FT。 三、改變 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)算 21 nNW21 BWA nN21 BWA nN21 A B 21 nNW21 BA21 nNWBA 21 A B (a)頻率抽取 IFFT的蝶形運(yùn)算 (b)時(shí)間抽 取 IFFT的蝶形運(yùn)算 四 .不改 (FFT)的 程序 直接實(shí)現(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程序計(jì)算 DFT； 然后 再取一次共軛；最后再乘 1/N,即得 (n)。所 以 FFT,IFFT可用一個(gè)子程序 。 x 五、 FFT的應(yīng)用 凡是利用付里葉變換來進(jìn)行分析、綜合、 變換的地方，都可以利用 FFT算法來減少 其計(jì)算量。 FFT主要應(yīng)用在 （ 1） 快速卷積 （ 2）快速相關(guān) （ 3）頻譜分析 1、線性卷積的 FFT算法 一 .線性卷積的長(zhǎng)度 設(shè)一離散線性移不變系統(tǒng)的沖激響 應(yīng)為 ,

22、其輸入信號(hào)為 .其輸出 為 .并且 的長(zhǎng)度為 L點(diǎn) , 的 長(zhǎng)度為 M點(diǎn) ,則： )(nx )(nx)(nh )(nh )(ny)(nx )(nh 1 0 )()()()()( L m mnhmxnhnxny )(ny 二、利用圓周卷積代替線卷積 用圓周卷積（ FFT） 代替線卷積的必要條 件： x(n)、 h(n)補(bǔ)零加長(zhǎng)至 L=N+M-1. 然后計(jì)算圓卷積。求出 y(n)代表線卷積。 10 10)( )( 10 10)( )( LnN Nnnh nh LnN Nnnx nx 三、用 FFT算 的步驟 )(ny ;1)(),(.1 點(diǎn)補(bǔ)零點(diǎn)，至少為將 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點(diǎn)的基 -2按時(shí)間抽取的 FFT流圖 （ DIT）。 試畫出 N=16點(diǎn)的基 -2按頻率抽取的 FFT流圖 （ DIF）。