VC++的FFT编程设计+文献综述(5)
至此，一个N点DFT被分解为两个N/2点的DFT。
上面是否将全部N点的 求解出来了？
分析： 和 只有N/2个点（ ），则由 只能求出 的前N/2个点的DFT，要求出全部N点的 ，需要找出 、 和 的关系，其中 。由式子 可得
化简得
＝ ，
这样N点DFT可全部由下式确定出来：
（＊）
上式可用一个专用的碟形符号来表示，这个符号对应一次复乘和两次复加运算。
图 蝶形运算符号
通过这样的分解以后，每一个N／2点的DFT只需要 次复数乘法，两个N/2点的DFT需要 次复乘，再加上将两个N／2点DFT合并成为N点DFT时有N／2次与W因子相乘，一共需要 次复乘。可见，通过这样的分解，运算量节省了近一半。
因为 ，N/2仍然是偶数，因此可以对两个N/2点的DFT再分别作进一步的分解，将两个N/2点的DFT分解成两个N/4点的DFT。
例如对 ，可以在按其偶数部分及奇数部分进行分解：
则的运算可相应分为两组：
将系数统一为以Ｎ为周期，即 ，可得
同样，对 也可进行类似的分解。一直分解下去，最后是２点的DFT，２点DFT的运算也可用碟形符号来表示。这样，对于一个 的DFT运算，其按时间抽取的分解过程及完整流图如下图所示。
这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，故称为“时间抽取法”。
分析上面的流图， ，一共要进行M次分解，构成了从x(n)到X(k)的M级运算过程。每一级运算都是由N/2个蝶形运算构成，因此每一级运算都需要N/2次复乘和N次复加，则按时间抽取的M级运算后总共需要
复数乘法次数：
复数加法次数：
根据上面的流图，分析ＦＦＴ算法的两个特点，它们对ＦＦＴ的软硬件构成产生很大的影响。
原位运算
也称为同址运算，当数据输入到存储器中以后，每一级运算的结果仍然存储在原来的存储器中，直到最后输出，中间无需其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的结构可以节省存储单元，降低设备成本。
上一篇：留守儿童文献综述和参考文献