FFT其框图实现

FFT 及其框图实现

基2时域抽取
基2频域抽取

FFT的完整名称为快速傅里叶变换，然而严格意义上，它并非一种独立的变换方法，而是用于高效完成DFT运算的一种算法。在面对较大的N值时，借助FFT能够显著降低执行DFT所需的计算资源。

对于长度为N的序列进行DFT运算所需的操作次数如下：
表达式为：
X[k]=\sum_{n=0}^{N-1}x[n]W_N^{kn}
其中涉及的乘法次数达到 N^2 次，而加法操作则需要 N(N-1) 次。当输入数据量 N 增加一倍时，整体计算复杂度将按照四倍的比例上升。

基2时域抽取

假定存在一个长度为2N的有限序列x[n]，对其进行DFT变换时，存在一种算法能够将原本需计算2N点的DFT转换为仅需计算N点的DFT，具体过程如下：
定义序列g[n]为x[n]中下标为偶数位置的元素构成的子序列，即有表达式为：g[n]=x[2n], 0\leq n \leq N-1 ；同时定义序列v[n]为x[n]中下标为奇数位置的元素构成的子序列，即有表达式： v[n]=x[2n+1], 0\leq n \leq N-1 。由此可得：

\begin{aligned} X[k] &= \sum_{n