多路并行FFT算法实现（一）：按时域抽取的FFT和按频域抽取的FFT

DFT：

●定义：

    ★DFT

    

     ★IDFT

    

●DFT计算复杂度：

    ★和N^2成正比

FFT

●FFT是算DFT的快速方法，可以把计算复杂度降到跟N*log(N)成正比

按时间抽取FFT：

注意：G[k]并不是x[2r]的FFT，H[k]也不是x[2r+1]的FFT，原因：k有可能大于等于N/2

当k = 0,1,……，N/2 - 1 的时候，X₁[k]就等于前面的G[k]，而X₂[k]就等于前面的H[k]。

●两点的FFT运算蝶形图：

当要做FFT运算的序列为{a,b}时，

其对应蝶形图表示如下：

●8点的FFT运算蝶形图[1]

●更多点的FFT

    按照8点FFT类推就行。

●变址：

    ★如上面“8点FFT运算蝶形图”所示，输入序列顺序会变化[1]。

    

按频率抽取

●表达式

先看DFT的表达式：

把得到的X[k]分为奇偶点来分析：

当k为偶数时：

同理当k为奇数时：

●蝶形图

   当N = 2时[1]：

    当N = 8时：

    

当 N = 其它值时，参照N = 8的情况即可~

小结：按时间抽取的FFT就是在时域上面分奇偶，按频率抽取的FFT就是在频域上面分奇偶

参考资料

[1] https://wenku.baidu.com/view/4c93ea3010661ed9ad51f3c1.html