1、按时间抽取的基 2FFT 算法分析及 MATLAB 实现一、DIT-FFT 算法的基本原理基 2FFT 算法的基本思想是把原始的 N 点序列依次分解成一系列短序列，充分利用旋转因子的周期性和对称性，分别求出这些短序列对应的 DFT，再进行适当的组合，得到原 N 点序列的 DFT，最终达到减少运算次数，提高运算速度的目的。按时间抽取的基 2FFT 算法，先是将 N 点输入序列 x(n)在时域按奇偶次序分解成 2 个 N/2 点序列 x1(n)和 x2(n)，再分别进行 DFT 运算，求出与之对应的 X1(k)和 X2(k)，然后利用图 1 所示的运算流程进行蝶形运算，得到原 N 点序列的 DFT
2、。只要 N 是 2 的整数次幂，这种分解就可一直进行下去，直到其 DFT 就是本身的 1 点时域序列。图 1 DIT-FFT 蝶形运算流图2、DIT-FFT 算法的运算规律及编程思想1.原位计算 对 N= 点的 FFT 共进行 M 级运算，每级由 N/2 个蝶形运算组成。在同一级中，每个蝶的M2输入数据只对本蝶有用，且输出节点与输入节点在同一水平线上，这就意味着每算完一个蝶后，所得数据可立即存入原输入数据所占用的数组元素(存储单元) ，经过 M 级运算后，原来存放输入序列数据的 N 个存储单元中可依次存放 X(k)的 N 个值，这种原位(址) 计算的方法可节省大量内存。2.旋转因子的变化规律N
3、 点 DITFFT 运算流图中，每个蝶形都要乘以旋转因子 ，p 称为旋转因子的指数。例WN如 N8 时各级的旋转因子：32第一级：L=1， 有 1 个旋转因子： = = J=0pNJ/4J2L第二级：L=2，有 2 个旋转因子： = = J=0,1pWNJ/2JL第三级：L=3，有 4 个旋转因子： = = J=0,1,2,3pJ2L对于 N 的一般情况，第 L 级共有 个不同的旋转因子：M21-L= J=0,1,2, , 1 pWJ2L-2= = NM-M-L故： 按照上面两式可以确定第 L 级运算的旋转因子3、同一级中，同一旋转因子对应蝶形数目第 L 级 FFT 运算中，同一旋转因子用在
4、个蝶形中；L-M24、 同一级中，蝶形运算使用相同旋转因子之间相隔的“ 距离”第 L 级中，蝶距：D= ；L25、同一蝶形运算两输入数据的距离 在输入倒序，输出原序的 FFT 变换中，第 L 级的每一个蝶形的 2 个输入数据相距：B=。 1-L26、码位颠倒输入序列 x(n)经过 M 级时域奇、偶抽选后，输出序列 X(k)的顺序和输入序列的顺序关系为倒位关系。将十进制顺序数用 I 表示，与之对应的二进制是用 IB 表示，十进制倒序数用 J 表示，与之对应的二进制是用 JB 表示。十进制顺序数 I 增加 1，相当于 IB 最低位加 1 且逢 2 向高位进1，即相当于 JB 最高位加 1 且逢 2
5、 向低位进 1。JB 的变化规律反映到 J 的变化分为两种情况，若 JB 的最高位是 0（J=K; J=J-K;K=K/2; endJ=J+K;end disp(倒序后各存储单元的数据:),disp(xn); % 分级按序依次进行蝶形运算 for L=1:M;%分级计算 disp(运算级次: ),disp(L); B=2(L-1); for R=0:B-1;%各级按序蝶算 P=2(M-L)*R; for K=R:2L:N-2;%每序依次计算 T=xn(K+1)+xn(K+B+1)*WN(P+1); xn(K+B+1)=xn(K+1)-xn(K+B+1)*WN(P+1);xn(K+1)=T;en
6、denddisp(本级运算后各存储单元的数据:),disp(xn);end在主函数中调用 myDitFFT(xn)函数实现 DIT-FFT 并和直接 DFT 运算结果做对比：xn=0,1,2,3,4,5,6,7;myDitFFT(xn);调用 fft 函数运算的结果:1 至 7 列28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 0.0000i -4.0000 - 1.6569i -4.0000 - 4.0000i8 列-4.0000 - 9.6569i调用 myDitFFT(xn
7、)函数运行的结果：输入到各存储单元的数据:0 1 2 3 4 5 6 7倒序后各存储单元的数据:0 4 2 6 1 5 3 7运算级次:1本级运算后各存储单元的数据:4 -4 8 -4 6 -4 10 -4运算级次:2本级运算后各存储单元的数据:1 至 7 列12.0000 + 0.0000i -4.0000 + 4.0000i -4.0000 + 0.0000i -4.0000 - 4.0000i 16.0000 + 0.0000i -4.0000 + 4.0000i -4.0000 + 0.0000i8 列-4.0000 - 4.0000i运算级次:3本级运算后各存储单元的数据:1 至 7
8、 列28.0000 + 0.0000i -4.0000 + 9.6569i -4.0000 + 4.0000i -4.0000 + 1.6569i -4.0000 + 0.0000i -4.0000 - 1.6569i -4.0000 - 4.0000i8 列-4.0000 - 9.6569i经对比可知 DIT-FFT 与直接 DFT 的运行结果完全相同。4、总结经过验证可发现 DIT-FFT 较直接 DFT 运算有着明显的优势，我们可以将这个函数运用在多个领域以简化运算，例如计算离散时间序列的卷积或计算 IDFT 时都可以应用到 DIT-FFT 算法，我感受到数字信号处理中科学思想的魅力。由
9、于对设计思路的缺乏，我在设计程序时，在网络上查找了很多有关 DIT-FFT 的资料，经过学习他人的解决思路最后才整理出 DIT-FFT的程序，在有些地方我自己理解的还不是很透彻，比如在实现数据倒序的程序我认为比较困难；当然即使自己想不到能学习一下别人的思路也是很好的，这个程序的代码量并不大，我自身的能力还很低，要在以后的学习中不断进步才能完成更加复杂的任务。这次课程设计让我对快速傅里叶变换有了更多的了解，也认识到了科学计算方法的重要性，我感到很充实。参考文献百度百科；按时间抽取的基 2FFT 算法分析及 MATLAB 实现J.电子技术，2011（2）数字信号处理 （第四版）西安电子科技大学出版社 高希全 丁玉美 编
