数字信号处理-0518二十

4.3按频率抽取（DIF）的基2FFT算法基2FFT的DIT算法是：每一级的处理都是建立在时域里将输入序列依次地按奇、偶一分为二，分成较小的序列，直到分成两点序列的DFT为止。基2FFT的DIF算法是：每一级的处理都是在频域里把序列分解为奇与偶的形式来进行计算。是将输入序列按n的序号分为上、下（前、后）两部分。DIF算法中蝶形运算基本关系为：其复数乘法出现于减法运算之后，这是与DIT算法的不同之处。由于这种算法是将按序号k的奇、偶分开，所以这种算法称为FFT的DIF算法。x(n)奇偶分组N/2点DFTx(2r+1)x(2r)B(k)A(k)蝶形运算DIT第一次分解DIF第一次分解x(n)前后分段分别N/2点DFTx(n+N/2)x(n)h(n)g(n)蝶形运算N/2点序列奇偶分开请画出N=8时的一次分解蝶形图3NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4点DFTX[0]X[6]X[2]X[4]4点DFTX[1]X[3]X[5]X[7]若N=8，则分成了两点DFTX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2点DFT-1-12NW0NW-1-12点DFT2点DFT2点DFT0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1请大家根据DIT-基2FFT算法的规律总结DIF-基2FFT算法的规律（参考N=8和N=16流图）1、级数2、每级的蝶形个数、节点距离、每个蝶形的运算次数3、每级组数4、每组W因子分布5、输入输出顺序同址运算（原位运算）运算次数每个蝶形需要一次复数乘法、两次复数加法每一级有N/2个蝶形单元，共M=log2N级所以完成M级运算共需次数：DITDIF级数每级蝶形个数第m级节点距第m级组数输入输出顺序输入倒位序输出自然顺序输入自然顺序输出倒位序运算量一样请按照规律画出N=8、16的DIF-基2FFT流图4.4.3实输入数据时的FFT算法实际工作中，输入数据x(n)一般都是实序列，通常将其视为虚部为零的复序列，这样会增加运算时间如何提高效率？方法一：用一个N点FFT同时计算两个N点实序列的DFT，一个作为实部，另一个作为虚部，计算完成后再把输出按照奇、偶、虚、实特性加以分离方法二：用一个N/2点FFT计算一个N点序列的DFT，将该序列的偶序号置为实部，奇序号置为虚部，同样在最后将其分离分析：属于上面的情况二方法步骤：1、设x(n)的偶序号组成序列u(n),奇序号组成序列v(n),均为N点实序列3、设x(n)的2N点DFT为X(k),u(n)的N点DFT为U(k)，v(n)的N点DFT为V(k)，通过U(k)、V(k)求X(k)(需要知道X(k)与U(k)、V(k)关系)2、需要求出U(k)、V(k)

方法：由u(n)和v(n)组成复序列y(n)=u(n)+iv(n);

求出Y(k),从而得出U(k)和V(k)1、设x(n)的偶序号组成序列u(n),奇序号组成序列v(n),均为N点实序列2、求U(k)、V(k)

方法：由u(n)和v(n)组成复序列y(n)=u(n)+iv(n);

求出Y(k),从而得出U(k)和V(k)利用奇偶对称性分离出YRe(k)等从而可由分离出的YRe(k)等求得U(k)和V(k)3、设x(n)的2N点DFT为X(k),u(n)的N点DFT为U(k)，v(n)的N点DFT为V(k)，通过U(k)、V(k)求X(k)(需要知道X(k)与U(k)、V(k)关系)只要将求出的U(k)和V(k)带入上式即可求得X(k)1、设x(n)的偶序号组成序列u(n),奇序号组成序列v(n),均为N点实序列2、求复序列y(n)=u(n)+iv(n)的DFTY(k)3、由Y(k)