DIT―FFT快速傅立叶变换的改进
开篇：润墨网以专业的文秘视角，为您筛选了一篇DIT―FFT快速傅立叶变换的改进范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘 要：本文讨论的FFT算法是基于多数参考文献中所论述的时间抽样快速傅立叶变换（dit-fft）。我们知道，在FFT变换中的关键步骤为：码位倒置、蝶形运算，并且从实现的角度考虑方法也是多种多样的，但从DSP芯片性能及商业价值考虑，不能只注重算法得出的最终结果，而是要考虑该算法优越性，不同的实现方法其所需的乘法与加法次数也会明显不同。本文主要讨论基2（radix-2）的DIT-FFT的改进。
中图分类号：TN911 文献标识码：A 文章编号：1674-7712 （2013） 08-0000-01
一、Evans’法则
按时间抽取（DIT）的FFT算法通常将原始数据倒位序存储，最后按正常顺序输出结果X（0），X（1），...，X（k），...。该法则的原理是直接找出要交换的两个位置，然后将这两个位置上的数据进行交换，这样省去了很多中间交换与存储过程，提高了交换效率，其速度是其它算法的8倍左右。其中Evans’seed表的建立是关键，
二、DIT-FFT算法的基本思想分析
三、FFT蝶形运算的改进
由上面可以知道，根据W因子本身的性质，在进行FFT蝶形运算时，有很大的优化空间来减少运算中的乘法次数。
（一）无关要因子减少乘法
除了第一级中W因子全为1，在第二级到最后一级蝶形运算中都存在W因子为1和-j或j的两项，它们在计算时可以直接通过加减法来实现。而W为复数的形式时则只能乘法实现。
（二）每级中W因子的特性
（三）相邻两级间W因子的关系
（四）蝶形运算的优化与改进思想
在具体四项蝶形组计算中，按先后顺序建立，为一组的表格即可。在W因子为复数的情况下，上面的乘法实际上为实部虚部的乘加运算，而利用W因子的性质进行特殊组合比一般的蝶形运算会省去很多乘法运算，提高计算速率。
其实质：在完成无关要旋转因子对应的蝶形运算时，用类似的思想完成无关要旋转因子蝶形运算中其四项间距里对应的关要旋转因子蝶形运算。比如：项数{0，4，8，12}完成了无关要旋转因子的蝶形运算，则按类似的方法实现起始项在0到4内以1，2，3开始对应的四项组合蝶形运算，即分别完成以项数{1，5，9，13}；{2，6，10，14}；{3，7，11，15}为起始蝶形组的运算。
四、总结
以上利用了W因子本身的特性以及相邻两级间W的关系，然后进行特殊的组合与循环来实现蝶形运算，相对多数参考文献上给出的蝶形运算有以下不同之处：
1.在每级蝶形运算中，并不是所有输入项都参与本级运算，这直接减少了运算所需的乘法次数与中间结果的存储过程。
2.在蝶形运算时，以四项为一个蝶形组来计算输出，其中前面两项为本级运算的输入，而后面两项为前一级的两项输入，在计算时直接利用相邻两级间W因子间的关系进行特殊组合比一般的蝶形运算会省去很多乘法运算，提高计算速率。
3.在具体计算中，对于W因子为1或±j时可直接复加来实现，相对会减少乘法与内存空间。
参考文献：
[1]江胜文.快速傅里叶变换的硬件实现[J].通信技术，2012，8.
[2]夏胜平，郁文贤.快速傅立叶变换算法概述季.长沙国防科技大学电子科学与工程
[3]陈媚媚，朱恩.一种高性能的基-4FFT蝶形运算单元[J].电子工程师，2008，12.