《北理工 数字信号处理 课件数字信号处理 第四章04补充校正》由会员分享，可在线阅读，更多相关《北理工 数字信号处理 课件数字信号处理 第四章04补充校正（41页珍藏版）》请在金锄头文库上搜索。
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 0 3 ( )( )()()() NNN W ( ) ( )xn 1 0 N W 0 0( ) ( )()()() 42
8、4 N x nx nx nx nx nW 1 3 ( )( )()()() 424 n N NNN x nx njx nx njx nW ( ) () x n N 0( ) xn 1 1 1 1 1 -1 N 2n N W 2 2 3 ( )( )()()() 424 n N NNN x nx nx nx nx nW 424 () 4 x n N 2( ) xn 1 1 -j j n N W 3 3 3 ( )( )()()() 424 n N NNN x nx njx nx njx nW 蝶形运算蝶形运算3次次 () 2 N x n 1( ) x n 1 -1 -1 j -1 N 3n W蝶
9、形运算蝶形运算： 3次次 ?次次 3 () 4 N x n 3( ) xn -j 3n N W 基基4 4- -DIF FFTDIF FFT算法算法基基4 4- -DIF FFTDIF FFT算法算法 0 3 ( )( )()()() NNN W 更正：课堂蝶形运算更正：课堂蝶形运算 次数讲解有误，应该次数讲解有误，应该 为为8 8次。因为次。因为一一个最个最 0 0( ) ( )()()() 424 N x nx nx nx nx nW 1 3 ( )( )()()() 244 n N NNN x nx nx nj x nx nW 为为8 8次。因为次。因为个最个最 小小X X蝶形是蝶形是2
10、 2次复加，次复加， 一个基一个基4 4蝶形含有蝶形含有4 4个个 最小最小X X蝶形蝶形 2 2 3 ( )( )()()() 424 n N NNN x nx nx nx nx nW 244 蝶形运算：蝶形运算： 3次次 8次次 最小最小X X蝶形。蝶形。 3 3 3 ( )( )()()() 244 n N NNN x nx nx nj x nx nW 8次次 ( )x n ( )( ) ( )xn 1 0 N W ( ) () x n N x n 0( ) xn 0 N W 2 1 1 1 1 11jj ( ) () x n N 0( ) xn 1 1 1 1 1 -1 N 2n N
11、W () 4 () x n N 2( ) xn 2n N W n N W jj 1 111 () 4 x n N 2( ) xn 1 1 -j j n N W () 2 3 N x n N 1( ) x n 3n N W 11jj () 2 N x n 1( ) x n 1 -1 -1 j -1 N 3n W3 () 4 N x n 3( ) xn jj 3 () 4 N x n 3( ) xn -j 3n N W 基基4 4- -DIF FFTDIF FFT算法算法基基4 4- -DIF FFTDIF FFT算法算法 0 3 ( )( )()()() NNN W 更正：课堂蝶形运算更正：课堂
12、蝶形运算 次数讲解有误，应该次数讲解有误，应该 为为8 8次。因为次。因为一一个最个最 0 0( ) ( )()()() 244 N x nx nx nx nx nW 1 3 ( )( )()()() 244 n N NNN x nx nx nj x nx nW 为为8 8次。因为次。因为个最个最 小小X X蝶形是蝶形是2 2次复加，次复加， 一个基一个基4 4蝶形含有蝶形含有4 4个个 最小最小X X蝶形蝶形 2 2 3 ( )( )()()() 244 n N NNN x nx nx nx nx nW 244 蝶形运算：蝶形运算： 3次次 8次次 最小最小X X蝶形。蝶形。 ( )x n
13、0( ) xn 3 3 3 ( )( )()()() 244 n N NNN x nx nx nj x nx nW 0 N W 8次次 ( ) ( )xn 1 0 N W ( ) () x n N x n 0( ) ( )xn N 2n N W ( ) () x n N 0( ) xn 1 1 1 1 1 -1 N 2n N W () 4 () x n N 2( ) xn () 4 x n N 2( ) xn 1 1 -j j n N W () 2 3 N x n N 1( ) x n -j n N W 3n N W () 2 N x n 1( ) x n 1 -1 -1 j -1 N 3n W3 () 4 N x n 3( ) xn 3 () 4 N x n 3( ) xn -j 3n N W 基基 4基基-4 按时间按时间按时间按时间 Or抽取抽取 FFT算法流图算法流图？Or 抽取抽取 FFT算法流图算法流图？ 按频率按频率按频率按频率 N=16 基基-4 按频率抽取按频率抽取FFT流图流图 回忆：回忆：N=12 组合数 基组合数 基-3x4 FFT流图流图 ( )x n N 0( ) x n 1 1 1 1 1 0 N W 2n N
