《北理工 数字信号处理 课件数字信号处理 第四章04预习》由会员分享，可在线阅读，更多相关《北理工 数字信号处理 课件数字信号处理 第四章04预习（19页珍藏版）》请在金锄头文库上搜索。
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 更快的更快的FFT算法算法DFTx(n) 更快的更快的FFT算法算法 设设 N=Pq, P=N/4, q=4q, q (=ML, M=N/4, L=4) 行号列号行号列号 L行M列，L x M 令令 n=Pn1+n0 , 0n13, 0n0(N/4)-1 n0 n1 k 4k +k0 k (N/4) 1 0 k3 4 / 30 k=4k1+k0, 0k
3、1(N/4)-1 , 0k03 )4()( 01 kkXkX),( 3 , 2 , 1 , 0 010 nnkkk 14 3NNN 14 0 4 ) 4 3 () 2 () 4 ()()4( n kn N W N nx N nx N nxnxkX 14 3NNN 14 24 3 k NNN 0 4 ) 4 3 () 2 () 4 ()() 14( n nkn N W N njx N nx N njxnxkX 0 24 ) 4 3 () 2 () 4 ()()24( n nkn N W N nx N nx N nxnxkX 14 34 ) 3 ()()()()34( nkn W N j NN j
4、kX 0 34 ) 4 () 2 () 4 ()()34( n nkn N WnjxnxnjxnxkX (4 43)10 N k 5 / 30 DIF (4-43)1 4 0 k 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
5、N nxnxkX 6 / 30 (4-44) 1 4 0 N k 1 2 0 ), 2 ()()( 2 N n N nxnxnx令 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次次 7 / 30 L形蝶形运算形蝶形运算： 2次次 5次次 则则(4-44)式变为式变为: )()()2( 2 1 2 2 2 nxDFTWnxkX N kn N 0n 1 4 N
6、)()() 14( 1 4 0 41 4 nxDFTWnxkX n kn N )()() 34( 2 4 1 4 42 4 nxDFTWnxkX N kn N 8 / 30 )()() 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-
7、21/P.146 N 可见：可见： N DFT N 4 DFT N 8 DFTN DFT N 2 DFT N 8 DFT N 8 DFTN DFT 4 DFT N DFT N 8 DFT N 4 DFT 16 DFT N 16 DFT N 8 N 10 / 30 DFT N 16 DFT N 1616 ) 1 2 ( 70)()( 21 N nnxnx 例：例：N=16分裂基第一次分解分裂基第一次分解L形流图：图形流图：图4-22 P.147 分解分解1： ) 1 4 ( 30)( ) 2 ()()( 1 4 21 N nnx ) 1 4 ( 30)( 4 2 4 N nnx 分解分解2：1
8、2 2 ) 1 4 ( 30)()( 22 N N nnynx 1 4 2 ) 1 8 ( 10)( 1 4 N N nny 11 / 30 1 4 2 ) 1 8 ( 10)( 2 4 N N nny 分解分解3： 10)()( 0)( 0)( 10)()( 2 1 4 22 nnz nnzny 4点分裂基点分裂基 L形运算流图形运算流图 图图4 24/P1480)( 2 4 nnz图图4-24/P.148 )( 1 nx )( )( 2 4 4 nx nx 图图4-24 图图4-23 图图4-22 图图4-25 P.148 12 / 30 16点分裂基点分裂基DIF-FFT算法流图算法流图
9、 x(0) x(1) 2 x (0) 2 x (1) X(0) X(2) N/2(8) 点 DFT ( ) x(2) x(3) x(4) 2 x (2) 2 x (3) 2 x (4) ( ) X(4) X(6) X(8) X(2k) 长偶 DFT x(5) x(6) x(7) 2 x (5) 2 x (6) 2 x (7) ( ) X(10) X(12) X(14) N/4=4 点 x(8) x(9) X(1) X(5) 1 4 x (0) 1 4 x (1) 1( ) 0 N W X(4k1)长奇之偶 点 DFT x(9) x(10) x(11) x(12) j j j j X(9) X(
10、13) X(3) 1 4 x (2) 1 4 x (3) 2 4 x (0) 1 N W 2 N W 3 N W 0 W X(4k1)长奇之偶 N/4=4 点 DFT x(12) x(13) x(14) x(15) j ( ) X(7) X(11) X(15) 2 4 x (1) 2 4 x (2) 2 4 x (3) 0 N W 1 N W 2 N W 3 N W 13 / 30 X(4k3)长奇之奇 0 2 4 0 4 8 12 0 8 16 24 6 8 10 12 14 16 18 12 16 20 24 28 2 4 20 12 28 LengthLengthLengthLength
11、- - - -32 split32 split32 split32 split- - - -radix FFTradix FFTradix FFTradix FFT 8 20 22 24 26 28 30 10 18 26 6 14 22 30 LengthLengthLengthLength 3232 split32 split32 splitsplit radixradix FFTradix FFTradix FFTFFT 1 5 9 13 17 21 25 1 9 17 25 5 21 25 29 3 7 11 15 21 13 29 3 11 19 27 14 / 30 84 6 5
12、15 19 23 27 31 7 23 15 31 6 5 三、运算量分析三、运算量分析 L形分解：共形分解：共M-1级级MN=2M N 每级每级L形碟形个数：形碟形个数： 4 1 N l 132 1 Mj l N l j 1,.,3 , 2, 24 1 Mjl j j 每个每个L形碟形：形碟形： 2次次 总的复数乘法次数总的复数乘法次数总的复数乘法次数总的复数乘法次数： 1 2 M jM lC 9 2 ) 1( 9 1 log 3 1 2 MN NN(4-48) 1j jM 993 2 相比，下降相比，下降33% N N 2 log 2 %100 2 1 ) 3 1 2 1 ( 15 / 3
13、0 2232 N N 2 log相同（相同（个数相同）个数相同） 4 4- -7 7 实序列的实序列的FFTFFT算法算法4 4- -7 7 实序列的实序列的FFTFFT算法算法 一、问题的提出一、问题的提出 FFTnxDFTnx)()( )()( 10 ),()( * Nnnxnx ? )(FFTnxDFT 可能的办法可能的办法：可能的办法可能的办法： FFTnyjnxnx)(0)()( 硬件专用算法/)()(nxDFTnx 16 / 30 能否有更好的方法吗？能否有更好的方法吗？ 二、算法一：用一个二、算法一：用一个N-FFT同时计算两个同时计算两个N点实序列点实序列 10 ),( 1 Nnnx 10)(N10 ),( 2 Nnnx )()()( )()()( kjXkXkX )()()( 21 njxnxnx X1(k), X2(k)都是复数序列（Matlab） ),()()( 21 kjXkXkX DFT的性质：的性质：P.91 1 )( )( )(njxnxnx ir )()( 2 1 )( * nxnxnxr 17 / 30 )()()(kXkXKX opep )()( 2 1 )( * nxnxnjxl 周期共轭对称分量周期共轭反对称分量周期共轭对称分量周期共轭反对称分量 即
