资源描述：
《基--2按频率抽取的fft算法decimation-in-frequency(dif)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四节 基--2按频率抽取的FFT算法Decimation-in-Frequency(DIF) (Sander-Tukey)一、算法原理设输入序列长度为N=2M(M为正整数），将该序列的频域的输出序列X(k)(也是M点序列），按其频域顺序的奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。二、算法步骤1.分组DFT变换：已证明频域上X(k)按k的奇偶分为两组，在时域上x(n)按n的顺序分前后两部分，现将输入x(n)按n的顺序分前后两部分:前半子序列x(n),0≤n≤N/2-1;后半子序列
2、x(n+N/2),0≤n≤N/2-1;例：N=8时，前半序列为：x(0),x(1),x(2),x(3);后半序列为：x(4),x(5),x(6),x(7);则由定义输出（求DFT）2.代入DFT中3.变量置换--13.变量置换--23.变量置换--33.变量置换--44.结论1一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：可见：如此分解，直至分到2点的DFT为止。4.结论2三、蝶形流图表示蝶形单元：时域中，前后半部表示式用蝶形结表示。x(n)x(n+N/2)与时间抽取法的推演过程一样，
3、由于N=2L,N/2仍为偶数，所以可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。例子：求N=23=8点DIF（1）先按N=8-->N/2=4，做4点的DIF：先将N=8点DFT分解成2个4点DFT：可知：时域上：x(0),x(1),x(2),x(3)为前半序列x(4),x(5),x(6),x(7)为后半序列产生新的子序列：x1(n)、x2(n)频域上：X(0),X(2),X(4),X
4、(6)由x1(n)给出X(1),X(3),X(5),X(7),由x2(n)给出将N=8点分解成2个4点的DIF的信号流图4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列x1(n)x2(n)X2(k)(2)N/2(4点)-->N/4(2点)FFT(a)先将4点分解成2点的DIF：因为4点DIF还是比较麻烦，所以再继续分解。（b)一个2点的DIF蝶形流图2点DFT2点DFTx1(0)x1(1)x1(2)x
5、1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)(c)另一个2点的DIF蝶形流图2点DFT2点DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。(b)2个1点的DFT蝶形流图1点DFTx3(0)1点DFTx3(1)X(0
6、)X(4)进一步简化为蝶形流图：X(0)X(4)x3(0)x3(1)(4)一个完整N=8的按频率抽取FFT的运算流图x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)m=0m=1m=2(5)DIF的特点(a)输入自然顺序，输出乱序且满足码位倒置规则。(b)根据时域、频域互换，可知：输入乱序，输出自然顺序。（6）DIF与DIT比较1相同之处：（1）DIF与DIT两种算法均为原位运算。（2）DIF与DIT运算量相同。它们都需要（6）DIF与DIT比较2不同之处
7、：（1）DIF与DIT两种算法结构倒过来。DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。（2）DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前。DIF的复数相乘出现在减法之后。作业P200，3题。试画出N=16点的基-2按频率抽取的FFT流图（DIF）。第五节IFFT运算方法以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算IFFT的
8、方法。一、利用FFT计算IFFT的思路1将下列两式进行比较二、利用FFT计算IFFT的思路2利用FFT计算IFFT时在命名上应注意：(1)把FFT的时间抽取法，用于IDFT运算时，由于输入变量由时间序列x(n)改成频率序列X(k),原
