数字信号处理_4 FFTDIT.pptVIP免费

15.2按时间抽选的基-2FFT算法5.2.1算法的基本原理两条规则：①对时间进行偶奇分解；②对频率进行前后分解。设序列x(n)长度为N=2M，M为整数。若不满足，则补零221grxrhrxr将序列x(n)按n的奇偶分成两组：0,1,...,/21rN偶数项奇数项2x(n)的DFT:10()[()]()NnkNnXkDFTxnxnW20,1,1212xrNxnrxrN/2DFTN/2DFTNDFT11222(21)00(2)(21),0,1,1NNrkrkNNrrxrWxrWkN11222200(2)()(21)()NNrkkrkNNNrrxrWWxrW3(2)(21)00/21/21221kNNrkrNNrrxrxkWrXW(2/21/2200)1221NNkNkrkrrNNrxrWWWxr(2)?krNW旋转因子的可约性:/2krNWmnkmNknNWW///21/2/20/210221NNkNkrkrNrrNXkxrWWWxr4g(r)=x(2r)h(r)=x(2r+1),0,1,,12Nr令()()()kNXkGkWHk12/0Nk/21/21/2/200kNNNkrkrNNrrXkWWrhrWgGkHk组合带来的附加计算量5()()()kNXkGkWHk12/0Nk?612/0Nk212NNkN12/0Nk2()()2)2(2NkNXkGkHNNNWk/21()/2/02()()2NkrrNNGkgrWN/21/20()NkrNrgrW/21/2//220()NNkrNNrrgrWW/2/21rNNW()Gk()()()kNXkGkWHk12/0Nk7221NNkkkNNNNWWWW(/2)()HkNHk同理,()()()2kNNXkGkWHk后半部分:()2XkN2()()NkNGkkWH12/0Nk2()()()22NkNNNWXkGkHk,8蝶形运算()()()()()()2kNkNXkGkWHkNXkGkWHk0/21kN蝶形运算构成了N点DFT的上半部分和下半部分偶数序号部分的N/2点DFT奇数序号部分的N/2点DFT()()()()()()2kNkNXkGkWHkNXkGkWHk12/0Nk)2/()()()(NkXkHkXkGrNWrNW)2/()()()(NkXkHkXkG－1rNW10蝶形运算流图组合的附加运算量:N/2次复数乘法,N次加法()()()()()()2kNkNXkGkWHkNXkGkWHk()()()(/2)GkXkHkXkN－1rNW蝶形运算流图11例：2点-FFTx[0]x[1]X[0]X[1]102WG[0]H[0]kNXkGkWHkk=0101012020202xxWWWWXX101111xx矩阵形式的DFT：(/2)()(),kNXkNGkWHkk=0？？124点基-2时间抽取FFT算法流图x[0]x[2]x[1]x[3]G[0]G[1]H[0]H[1]2点DFT2点DFT...