《北理工 数字信号处理 课件数字信号处理 第四章04》由会员分享，可在线阅读，更多相关《北理工 数字信号处理 课件数字信号处理 第四章04（22页珍藏版）》请在金锄头文库上搜索。
1、数字信号处理数字信号处理数字信号处理数字信号处理 周治国周治国 2010.03 第四章第四章第四章第四章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换第四章第四章第四章第四章 快速傅里叶变换快速傅里叶变换快速傅里叶变换快速傅里叶变换 4 4- -6 6 分裂基分裂基FFTFFT算法算法4 4- -6 6 分裂基分裂基FFTFFT算法算法 一、背景一、背景 对更快速算法的需求对更快速算法的需求 N N N FFT 2 log 2 2基 1984年，杜梅尔（年，杜梅尔（P.Douhamel） 霍尔曼（霍尔曼（H.Hollman） 基基-2 FFT N N 分裂基 3 / 30 基基 2
2、 FFT 基基-4 FFT N N FFT 2 log 3 分裂基 3 / 30 4 4- -6 6 分裂基分裂基FFTFFT算法算法4 4- -6 6 分裂基分裂基FFTFFT算法算法 二、算法原理二、算法原理 2, 10 ),( NNnnx DFTx(n) 更快的更快的FFT算法 设 算法 设 N=Pq, P=N/4, q=4q, q 令令 n=Pn1+n0 = N/4 n1+n0; 0n13, 0n0(N/4)-1 k=4k1+k0; 0k1(N/4)-1 , 0k03 10 ; 1( ), 0 1 ( )( ) N kn N X kx n W 10 0 4 13 () 4 10 ()
3、4 n NN knn N N xnn W 4 / 30 01 0 00 4 1 023 04040404 4 3 ()()()() 424 nn N knkkk N NNN x n Wx nWx nWx nWW 0 0 424 n 101010100 10 4 1 (4)2(4)3(4)4(4) ( )(4) 3 ()()()() N kkkkkkkkn X kXkk NNN WWWW ),( 3 , 2 , 1 , 0 010 nnkkk 101010100 0 000100 ()()3()() 0040404 0 4 1 234(4) ()()()() 424 3 ()()()() kkk
4、kkkkkn N n N kkkkkn x nx nWx nWx nWW NNN x nx nWx nWx nWW 16 Im m W 11 12 16 W 13 0 0040404 0 ()()()() 424 N n x nx nWx nWx nWW 010 0,1,2,3kkknn在时，用 表示 ， 表示 14 16 W 15 16 W 16 Re m W 0 16 W 1 16 W 7 16 W 8 16 W 9 16 W 10 16 W 11 16 W 16 W 13 16 W 17 W 1 16 W 18 32 W 4 1 4 0 3 (4 )( )()()() 424 N kn
5、N n NNN Xkx nx nx nx nW 2 16 W 3 16 W 4 16 W 5 16 W 6 16 W 16 W 3 8 W 4 1 4 0 3 (41)( )()()() 424 N kn n N n NNN Xkx njx nx njx nW 4 1 42 0 3 (42)( )()()() 424 N knn N n NNN Xkx nx nx nx nW 4 1N 4 1 43 0 3 (43)( )()()() 424 N knn N n NNN Xkx njx nx njx nW N 4-DIF基 (4-43)1 4 0 N k 16 Im m W 14 16 W 1
6、0 16 W 11 16 W 12 16 W 13 16 W 16 15 16 W R m W 9 16 W 16 W 1 16 W 18 32 W 16 Re m W 0 16 W 8 16 W 1 16 W 2 16 W 6 16 W 7 16 W 17 16 W 16 3 16 W 4 16 W 5 16 W 16 W 3 8 W 参考P96 图3-21 基基4 4- -DIF FFTDIF FFT算法算法基基4 4- -DIF FFTDIF FFT算法算法 4 1 0 3 (4 )( )()()() N kn NNN XkW W N 0 /4 0 (4 )( )()()() 424 k
7、n NN n Xkx nx nx nx nW W 4 1 /4 0 3 (41)( )()()() 424 N nkn NN NNN Xkx njx nx njx nW W 4 1 2 /4 0 3 (42)( )()()() 424 N nkn NN n NNN Xkx nx nx nx nW W 4 1N 1 4 0 N k 0 424 n 4 1 3 /4 0 3 (43)( )()()() 424 N nkn NN n NNN Xkx njx nx njx nW W ( ) ( )xn 10 3 ( )( )()()() NNN W 0 N W ( ) () x n N 0( ) xn
8、 1 1 1 1 -j -j 0 0( ) ( )()()() 424 N x nx nx nx nx nW 1 3 ( )( )()()() 424 n N NNN x nx njx nx njx nW N n N W () 4 x n N 1( ) x n 1 j 2 2 3 ( )( )()()() 424 n N NNN x nx nx nx nx nW 424 -1 -1 j 2n N W () 2 N x n 2( ) xn 1 3 3 3 ( )( )()()() 424 n N NNN x nx njx nx njx nW j 1 -1 -1 N 3n W蝶形运算蝶形运算 3次
9、次 3 () 4 N x n 3( ) xn -j 3n N W蝶形运算蝶形运算： 3次次 ?次次 基基4 4- -DIF FFTDIF FFT算法算法基基4 4- -DIF FFTDIF FFT算法算法 0 3 ( )( )()()() NNN W 0 0( ) ( )()()() 424 N x nx nx nx nx nW 1 3 ( )( )()()() 244 n N NNN x nx nx nj x nx nW 2 2 3 ( )( )()()() 424 n N NNN x nx nx nx nx nW 244 蝶形运算：蝶形运算： 3次次 10次次 ( ) ( )xn 1 3
10、3 3 ( )( )()()() 244 n N NNN x nx nx nj x nx nW 0 N W ( )x n ( )( ) () x n N 0( ) xn 1 1 1 1 -j -j N n N W ( ) () x n N x n 0( ) xn 0 N W 1 1 1 1 11jj () 4 x n N 1( ) x n 1 j -1 -1 j 2n N W () 4 () x n N 1( ) x n n N W 2n N W jj 11 11 () 2 N x n 2( ) xn 1 j 1 -1 -1 N 3n W () 2 3 N x n N 2( ) xn 3n N
11、 W 11jj 3 () 4 N x n 3( ) xn -j 3n N W3 () 4 N x n 3( ) xn jj 1 2 NN N : )24()4(kXkX与合并 1 2 0 ,) 2 ()()2( 2 0 2 N kW N nxnxkX n kn N 1 4 4 ) 4 3 () 4 () 2 ()() 14( N kn N n N WW N nx N nxj N nxnxkX 0 442 n 1 4 3 N NNN 0 43 ) 4 3 () 4 () 2 ()()34( n kn N n N WW N nx N nxj N nxnxkX (4-44) 1 4 0 N k 2(
12、 ) ( )(), 01 22 NN x nx nx nn 令 n N W N nx N nxj N nxnxnx ) 4 3 () 4 () 2 ()()( 1 4 NNN 32 3 442 n N W N nx N nxj N nxnxnx 32 4 ) 4 3 () 4 () 2 ()()( N 1 4 0 N n L形蝶形运算形蝶形运算2次次L形蝶形运算形蝶形运算： 2次次 5次次 则则(4-44)式变为式变为: )()()2( 2 1 2 2 2 nxDFTWnxkX N kn N 0n 1 4 N )()() 14( 1 4 0 41 4 nxDFTWnxkX n kn N )()
13、() 34( 2 4 1 4 42 4 nxDFTWnxkX N kn N )()() 34( 4 0 4 nxDFTWnxkX n N 1 2 2 2 (2 )( ) N kn N Xkx n W 2 0 2 ()( ) ( ) N n DFT x n 1 4 N 4 14 4 0 1 (41)( ) kn N n Xkx n W 1 4 ( )DFT x n 1 4 24 4 (43)( ) N kn N Xkxn W 0 2 4 ( ) n DFT xn L形蝶形形蝶形(流图流图) 图图4-21/P.146 N 可见：可见： N DFT N 4 DFT N 8 DFTN DFT N 2 DFT N 8 DFT N 8 DFTN DFT 4
