數(shù)字信號處理 - 北京理工大學(xué)

1、 2 / 30FFTN 22基? 2DFTN，如何快速計算(1)通過補零通過補零，使序列長度使序列長度=2 基基-2 FFT一、算法原理一、算法原理(2)N=ML（復(fù)合數(shù)）復(fù)合數(shù)） 統(tǒng)一的統(tǒng)一的FFT算法算法(3)NML（素數(shù)）素數(shù)） Chirp-Z 變換變換(CZT)處理方法：處理方法：（復(fù)合數(shù)）MLNNnnx , 10 ),(N-DFTN2如果如果N-DFTM個個L-DFTML2L個個M-DFTLM2減少了運算減少了運算 3 / 30為此，令為此，令n=Mn1+n0 , n0=0,1,M-1 列號列號 n1=0,1,L-1 行號行號) 1()1() 12() 1()() 1() 1 ()

2、0 (MLxLMxMxMxMxMxxx) 1, 1() 1 , 1() 0 , 1() 1, 1 () 1 , 1 () 0 , 1 () 1, 0 () 1 , 0 () 0 , 0 (MLxLxLxMxxxMxxxx(n)x( n1 , n0 ) 4 / 30同理，對同理，對DFT的輸出的輸出X(k)做類似的處理：做類似的處理：令令 k=Lk1+k0k0=0,1,L-1 n1k1=0,1,M-1 n0(0)( )(1) )(1)(1)(1)1)(1)(21)(1)XX LX MLXX LX MLX LXLX ML(0,0)(1,0)(1,0)(0,1)(1,1)(1,1)(0,1)(1,1

3、)(1,1)XXX MXXX MXLXLX MLX(k)X( k1 , k0 ) 5 / 30),()()(0101kkXkLkXkX10)(NnknNWnx1010)(21010101),(MnLnkLknMnNWnnx1010210100010111),(MnLnnkNnLkNkMnNnMLkNWWWWnnx10102101010010),(MnLnnkMnkNnkNWWWnnxx(Mn1+n0)=110nkLW01nkMW1000100100),(MnnkMnkNWWnkX10001001),(MnnkMWnkX)()(),(),(0101102kXkLkXkkXkkX10 , 1010

4、MkLk10Nk 6 / 301001001110),(),(LnnkLWnnxnkX0001, 10 ),(1nLknnxDFTnkMnWnkXnkXnkN, 10 ,),(),(00010010010001102001),(),(LnnkMWnkXnkX001001, 10 , 10 ),(0nLkMknkXDFTn一列一列一列一列求求DFT旋轉(zhuǎn)旋轉(zhuǎn)因子因子一行一行一行一行求求DFT式中式中 7 / 30二、運算步驟二、運算步驟0101),()( ) 1 (nmnnnnxnx列號行號1,.,1 , 01,.,1 , 001MnLn（真對每一列） 10 , )2(00Mnn),(),(010011nnxDFTnkXn1,.,1 , 0 ,),(01001110LkWnnxLnnkL1010),(),()3(0000100100MnLkWnkXnkXnkN（針對每一行） 10 , )4(00Lkk),(),(0011020nkXDFTkkXn1,.,1 , 0 ,),(010001001MkWnkXMnnkM 8 / 30譯序 )5(10)(),(),(01102NkkXkkXkkX,01kLkk101010M